2017-10-01から1ヶ月間の記事一覧
Atcoder Grand Contest 010 D. Decrementing D: Decrementing - AtCoder Grand Contest 010 | AtCoder 感想 奇数の$\ gcd\ $で割ったときに偶奇の個数が変わらないことがポイントだった。 解法 明らかに愚直に考えると厳しいので、とりあえず偶奇によって場…
Atcoder Grand Contest 006 D. Median Pyramid Hard D: Median Pyramid Hard - AtCoder Grand Contest 006 | AtCoder 感想 いいところまでは考えられたような気がしたけど結局解説を読んで。 てきとうに書いて投げたら通った。 最近は二分探索をあまりバグら…
Atcoder Grand Contest 002 D. Stamp Rally D: Stamp Rally - AtCoder Grand Contest 002 | AtCoder 解法 二分探索をまとめてやる感じのやつ。各$\ mid\ $の値に関するソートをしておくことで左から順に見ていける。$\ O(m {\log}^2 m)\ $。 実装 #include "…
Atcoder Grand Contest 007 C. Pushing Balls C: Pushing Balls - AtCoder Grand Contest 007 | AtCoder 感想 難しいよ 解法 解説動画がわかりやすい。各ボールの距離に関する数列を書いて実験すると、その次のステップ（の期待値）の数列も同様に等差数列に…
Atcoder Grand Contest 019 C. Fountain Walk 感想 500点くらいの問題 解法 一般性を失わずに左上にスタート、右下にゴールがあると仮定して、それらを頂点とする長方形を考える。このとき、明らかにこの長方形の外に出て遠回りする方が経路長が短くなるよう…
Atcoder Regular Contest 013 C. 笑いをとれるかな？ C: 笑いをとれるかな？ - AtCoder Regular Contest 013 | AtCoder 感想 友人が問題文の内容がおもしろいと言っていたのでやったみた。確かにおもしろかった。 解法 各座標軸を基準にみて端点同士の点より…
Atcoder Grand Contest 011 E. Increasing Numbers E: Increasing Numbers - AtCoder Grand Contest 011 | AtCoder 感想 数論の問題などでたまに見かけるレピュニットの性質をうまく利用した問題で少しおもしろかった。 解法 増加的な数を9個以下のレピュニ…
AOJ Prime Caves 感想 実装がめんどくさい 解法 どう見てもDPするだけ。$\ m \leq 10^6\ $なので、$\ 1000 * 1000\ $の正方形のマスを用意して考えればよい。すごく面倒だが、各数を投げるとその配列上での位置を返す関数を作る。これは各正方形の左上の数が…
Atcoder Grand Contest 004 F. Namori F: Namori - AtCoder Grand Contest 004 | AtCoder 感想 解にたどり着くまでに考えることがたくさんある。ケースに応じて適切なアルゴリズムに落とし込んでいくのが、おもしろい。 解法 まず連続する同色の頂点を反転さ…
Atcoder Grand Contest 014 E. Blue and Red Tree E: Blue and Red Tree - AtCoder Grand Contest 014 | AtCoder 感想 難しいがおもしろい。解説を読んで、少し人のコードを参考にして書いた。 解法 辺の色が異なる2つの木を重ね合せて考える。そのグラフ上…
行列ライブラリ 競プロ用に行列ライブラリを作った。特別に綺麗だとか高速だとかそういうことはないけれど、もし利用したい人がいれば、勝手に利用していただいても構いません。多分動きます。Typeは、値が小数になる場合と、逆行列が必要なときにdoubleにし…
AOJ Graph Automata Player Graph Automata Player | Aizu Online Judge 感想 ICPCのチーム練習で解いた。好きな感じの問題なので、じーーっと考察していると解法がわかった。 解法 ある頂点に注目して考える。ある状態から次の状態に遷移するとき、その頂点…
CODE FESTIVAL 2017 qual B C. 3 Steps C: 3 Steps - CODE FESTIVAL 2017 qual B | AtCoder 感想 qual Aには出れなかったので、qual Bから参戦していた。40分で3完し、そのあとはひたすらDのバグをつぶそうとしていた。総合243位、日本人98位なので本戦には…
CODE FESTIVAL 2017 qual B D. 101 to 010 D: 101 to 010 - CODE FESTIVAL 2017 qual B | AtCoder 感想 コンテスト中はあやふやな実装でバグらせた。 DEGwerさんの提出コードを見ると、驚くほどわかりやすく実装されていたのでさすがだと思った。左右端の処…
第16回日本情報オリンピック予選 E. 尾根(Ridge) E: 尾根 (Ridge) - 第１６回日本情報オリンピック 予選（オンライン） | AtCoder 感想 典型的なdfsに落とし込む問題 解法 水が流れる方向に沿って、辺を張る。このとき、出次数が0であるような頂点がそれ以降…
