Atcoder
H - Generalized Insertion Sort 解法 まず制約に注目すると、$25000 \geq n \log n$ にしか見えないので、そのような計算回数を実現するアルゴリズムを考えたい気持ちになります。木に関するアルゴリズムであって、計算量に $\log$ が現れるものは僕は現時…
D - 辺彩色 解法 まず辺に色を塗っていく操作を、逆順から見ていきます。この発想は以下のような問題でも使えます。B - Splatter Paintingそうすると、一回塗った辺はもう変更することができないという操作に変えることができます。すると、各辺は条件を満た…
Atcoder Regular Contest 063 E. 木と整数 / Integers on a Tree E - 木と整数 / Integers on a Tree 感想 ふつうに木の上で計算しました。 解法 まず頂点 $0$ を根として考えることにします。明らかな性質として、深さが同じような頂点に書かれた値すべての…
Atcoder Regular Contest 088 F. Christmas Tree F - Christmas Tree 感想 木をいくつかのパスで被覆する、よくありそうな問題です。CSA Flip the Edgesに似ています。 解法 まずパスの両端の次数は奇数でそれ以外は偶数である（それはそう）という性質から…
Atcoder Grand Contest 013 F. Two Faced Cards F - Two Faced Cards 解法 解法がかなりきれいで、よい問題だと思いました。editorialの英語版がわかりやすかったので、そこに書かれているように実装しました。まず定石ですが、$c$ はソートして座圧し、$c$ …
Atcoder Grand Contest 009 E. Eternal Average E: Eternal Average - AtCoder Grand Contest 009 | AtCoder 感想 実装軽いのに考察が重すぎる...。 解法 最終的に残る数を$\ x\ $とする。$\ x\ $は連分数で書かれるような数になるが、このまま考えるとわか…
Atcoder Grand Contest 008 D. K-th K D: K-th K - AtCoder Grand Contest 008 | AtCoder 解法 位置が確定しているものを左から順に確定させ、その数の左側に置かなければいけない個数を空いている場所に左詰めで書いていく。これができない場合は不可能。位…
Atcoder Grand Contest 013 E. Placing Squares(追記) E: Placing Squares - AtCoder Grand Contest 013 | AtCoder 感想 愚直$\ DP\ $の高速化に失敗したので、解説放送を見て想定解を実装した。 解法 $\ 0\ $から$\ n\ $までの任意の位置に柵をおいて、その…
Atcoder Grand Contest 013 E. Placing Squares E: Placing Squares - AtCoder Grand Contest 013 | AtCoder 感想 $\ O(n)\ $を高速化したかったけどできてない..... 想定解はまた今度考える。 解法 まず愚直に$\ DP\ $を書くと$\ O(n^2)\ $になる。この記事…
Atcoder Regular Contest 084 F. XorShift F: XorShift - AtCoder Regular Contest 084 | AtCoder 解法 基底とする数は与えられる$\ n\ $個の数だけとして考えて良い。これらを任意の個数使って、シフトさせたり$\ xor\ $をとったりして数を作る。ここで$\ x…
Atcoder Grand Contest 007 F. Shik and Copying String F: Shik and Copying String - AtCoder Grand Contest 007 | AtCoder 感想 考えることはシンプルなんだけど条件が難しい 解法 $\ T\ $の連続する文字の先頭文字と、それに対応する$\ S\ $の文字を決定…
Atcoder Grand Contest 010 E. Rearranging E: Rearranging - AtCoder Grand Contest 010 | AtCoder 感想 とにかく自力でACできて喜んでいたが、うさぎさんのコードを見ると圧倒的に簡潔でわかりやすかったので、大幅に真似て改良した。 AtCoder Grand Conte…
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個以下のレピュニ…
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つの木を重ね合せて考える。そのグラフ上…
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であるような頂点がそれ以降…
Atcoder Grand Contest 002 F. Leftmost Ball F: Leftmost Ball - AtCoder Grand Contest 002 | AtCoder 感想 前半の考察はできたが、あとはなにも手を動かせなかった。 順序制限のある組み合わせの問題であることから、各数を頂点と見たグラフに落とし込み…
Atcoder Grand Contest 012 D. Colorful Balls 感想 前半の考察はできたのに、ほとんど同じの後半の発想がなぜかできなかった。 解法 まずすべての色が等しければ、答えは$\ 1\ $となる。以下は2種類以上の色があるものとする。操作1では色の配置を変えるこ…
Atcoder Grand Contest 008 F. Black Radius F: Black Radius - AtCoder Grand Contest 008 | AtCoder 感想 こちらのei1333さんの記事†全方位木DP†について - ei1333の日記で全方位木dpの概念を学んだところだったので、そこまで苦労しなかった。わかりやす…
Atcoder Grand Contest 017 E. Jigsaw E: Jigsaw - AtCoder Grand Contest 017 | AtCoder 感想 新しい感じのdfsをした。 解法 まずある右（左）の形状に対して、対応する左（右）の形状が一意に定まることに注意する。このうまくフィットする形状同士を同一…
Atcoder Beginner Contest 057 D. Maximum Average Sets D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder 感想 なぜかWAのまま放置していた。 解法 なんかやるだけ。 ただし$\ {}_n C _r \ $を求めるためにはパスカルの三角形による計算…
Atcoder Grand Contest 019 D. Shift and Flip 感想 結局やるだけだったけど、ひたすら補題の実装ができなかった。解説は自明なパートだけだらだらと書いていて最も知りたい部分が省略されていた。 解法 まず最終的に$\ a\ $のどの部分が$\ b\ $のどの部分に…
