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であるような頂点がそれ以降…
CS Academy 050 Div.2 E. Min Swaps CS Academy 感想 見掛け倒しな感じがある。 解法 まず値が大きいものと小さいものが順に現れるように順列を作れば、なんとなく条件を満たしそうなことから、そのように並べてみる。その数列が小さいものからスタートする…
CS Academy 050 Div.2 Check Square CS Academy 感想 色々やり方がありそうだけど、頂点を見る順番で全探索した。 解法 4点の位置関係がわからないので、その関係を全探索する。順番に点をずらしながら辺を4本とって、その長さがすべて等しくなるような場合…
Codeforces Testing Round 1 C. Circular RMQ Problem - C - Codeforces 感想 区間加算、区間最小値を処理する遅延セグメント木をライブラリに追加したので、貼るだけの問題で試しておいた。 解法 貼るだけ。ただし入力が親切じゃないので、getlineで入力を…
CS Academy 048 D. Dominant Free Sets CS Academy 感想 アルゴリズムの正当性を証明していたにも$\ AC\ $できず......。結局FenwickTreeのクエリ処理時にMODをとっていなかっただけだった。 解法 まず$\ x\ $に関してソートしておき、その列の上で順に$\ y\…
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では色の配置を変えるこ…
CS Academy 46 Div. 1.5 C. Set Subtraction CS Academy 感想 ちょっと応用できそう。 解法 まず数列はソートしておく。そして$\ X\ $について全探索する。全探索といっても$\ X \leq A_{n - 1}\ $ですべて試していると間に合わないので、$\ X\ $の候補とし…
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\ $のどの部分に…
Atcoder Regular Contest 054 B. ムーアの法則 B: ムーアの法則 - AtCoder Regular Contest 054 | AtCoder 感想 はじめて三分探索を書いた。凸関数の解を求めるときに使えるやつ。零点が手で計算できるときはそっちの方が良いんだと思う。 解法 三分探索で、…
Atcoder Regular Contest 076 E. Connected? E: Connected? - AtCoder Regular Contest 076 | AtCoder 感想 だいぶ前に線分の交差判定などで解こうとしたけどダメだったので放置していた。条件をもう少し本質的にとらえることと、周を1次元に落とし込むこと…
Atcoder Regular Contest 079 F. Namori Grundy F: Namori Grundy - AtCoder Regular Contest 079 | AtCoder 感想 こういうグラフをNamoriグラフというらしい。 解法 まずグラフの形状が常に閉路を一つ含み、そこから木が外側に向かって生えたようなグラフに…
Atcoder Regular Contest 080 F. Prime Flip F: Prime Flip - AtCoder Regular Contest 080 | AtCoder 感想 解説を見た。簡単な方法に落とし込むまでの流れが好きな問題。 解法 まず区間をひっくり返すときのテクを使う。列においてある位置とその一つ前の位…
Atcoder AGC 005 E. Sugigma: The Showdown E: Sugigma: The Showdown - AtCoder Grand Contest 005 | AtCoder 感想 後半の考察に1時間以上かかったが、自力で一発ACしたので嬉しかった。木とゲームに関する問題はやっぱり得意だ。 解法 以下、先手を$\ N\ $…
Atcoder AGC 003 D. Anticube D: Anticube - AtCoder Grand Contest 003 | AtCoder 感想 素因数分解したときに出てくる3乗は消しても良いことには割とすぐに気づき、共存できない数同士のペアが一意に定まるところまでは落とし込めた。が、実装方法と計算量…
Atcoder ARC 061 D. すぬけ君の塗り絵 / Snuke's Coloring D: すぬけ君の塗り絵 / Snuke's Coloring - AtCoder Regular Contest 061 | AtCoder 解法 最も愚直な方法は、$\ H * W\ $の配列を用意し、そこにクエリに従って色をつけていき、最後に$\ 3 * 3\ $の…
Atcoder AGC 017 B. Moderate Differences B: Moderate Differences - AtCoder Grand Contest 017 | AtCoder 解法 数列において減少する回数を固定して、差分($\ B - A\ $)のとりうる最小最大を決めて条件を満たすものがあるかを判定する。例えば下限を考え…
Atcoder AGC 006 C. Rabbit Exercise C: Rabbit Exercise - AtCoder Grand Contest 006 | AtCoder 解法 まず、各ステップにおいて、期待値を決定していけることに注目する。うさぎ$\ a\ $について、そのジャンプ後の位置の期待値は、左右のジャンプが両方確…
