srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

2016-09-20から1日間の記事一覧

yukicoder No.124 門松列(3)

問題 問題概要 省略 解法 bfsで解いた。進める方向は、進もうとするマスと、現在のマスと過去のマスの3つが門松列をなしているとき。注意しなければならないのは、基本的な最短経路問題で使うbfsのように、座標のみを状態として最短距離をメモしていくと、解…

yukicoder No.123 カードシャッフル

問題 問題概要 省略 解法 がんばって実装しよう。 ミス なし。 コード #include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) int n, m; int main(void){ cin >> n >> m;</algorithm></vector></set></cstdio></iostream>…

ABC 022 D - Big Bang

問題 問題概要 相似比を求める問題 解法 Aの座標に対して行われた操作は平行移動と回転なので、AとBは相似である。よって、相似比を求めれば、よいことなる。どこを見て相似比をみるかは多くの解法があるみたい。 一番簡単なのは、重心からの距離が最大の点…

ABC 022 C - Blue Bird

問題 問題概要 省略 解法 ダイクストラでやろうと思うと、閉路の最短距離を出すのは普通にやったらできない。求めるのは0から初めて、0に戻るような閉路で最短距離。そのような経路は、0 -> u -> v -> 0 ものである。同じ道を2度通ることはできないので、u…

ABC 021 C - 正直者の高橋くん

問題 問題概要 省略 解法 bfsで解いた。よくある最短距離を求めるときにやる、bfsは一度、到達したところは2回目以降むしをするが、今回は、初めて到達したあとも、その位置に最短距離として、ほかの経路から到達して来る可能性があるので、bfsで初めに到達…

abc 020 C - 壁抜け

問題 問題概要 省略 解法 2分探索and最短経路問題。 xを小さくしていけば、かならず、ゴールにたどり着け、無限に大きくしていけば、どこかで、たどり着けなくなる。このような場合、求めるxを2分探索で効率よく絞り込んでいける。あとは、そのxに対して、ダ…

abc 019 D - 高橋くんと木の直径

問題 問題概要 木の直径を求める問題。 解法 木の直径を求めるアルゴリズムは、 1.任意の頂点sから最も遠い頂点をxを求める 2.頂点xから、最も遠い頂点yを求める 3.頂点xからyの距離が木の直径となる これを実装すればいい。 ミス なし。 コード #include <iostream> #</iostream>…

abc 019 C - 高橋くんと魔法の箱

abc

問題 問題概要 省略 解法 2倍したものは同じものとしてみなせるため、まずすべての数字を2で割れるだけ割る。そのあと、数字の種類が答えとなる。 ミス なし。 コード #include <iostream> #include <cstdio> #include <vector> #include <set> #include <algorithm> using namespace std; typedef long</algorithm></set></vector></cstdio></iostream>…