AtCoder Beginner Contest 265

　Eまで五完だが、Eは嘘でした。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 265 EまでACしたけどEは嘘解法。
A Y円払う回数全探索
B,C シミュレーション
D 二分探索
E https://t.co/GyNtjNzmsIと同じようにやったら通った。自分のコードでは(i,j,k)で障害物にぶつかるものを列挙しているので、300^6の計算量のはず。（簡単に落ちるケースを作れた）

— titia (@titia_til) August 21, 2022

E - Warp

　解法ツイートを見て改めてACした。

　（A, B）をi回、(C, D)をj回、(E, F)をk回使ったときは何通り？　という非常に自然なDPで良かった。

　最初見たとき包除原理に見えてしまい、そこから方針転換できなかったのは反省。

F - Manhattan Cafe

　解説放送を見てAC。

　単純なDPを累積和で高速化する問題だが、単純なDPすら思いつかなかった。

　というか、そもそも誤読していた。（格子点の数も二つだけと思ってなかったし、制約ももっと大きいものと思っていた）

　N次元空間などと言われると、苦手意識があるためまともに考えられなくなる気がする。空間把握などが必要な問題が解けないのは仕方ない部分もあるが、今回の問題は、定義に従ってDPを組むだけなので、空間把握などは不要な問題だった。

　苦手意識があると、つい考えることをやめてしまいたくなるが、ちゃんと問題を読み、定義に従って考えよう。

G - 012 Inversion

　解説放送を見てAC。

　セグ木を使いそう、というのは一目で分かった。セグ木の各要素として何を持てば良いか、というところで詰まってしまったが、これも自然に考えれば分かるものだった。落ち着いて考えれば自力で思いつけたと思う。

　ただ、実装には苦戦した。遅延セグ木を使うのだが、可換性が成り立たない演算があるため、自分のライブラリ（これ自体あまり整備されていないのだが）を修正しないといけない部分が多かった。この辺は慣れておきたい（遅延セグ木の整備もすべきか……）。

　難しくはないのだが、実際に通すのは結構大変。

yukicoder contest 356

　眠くなってしまいA一完だったが、いくら眠くてももっと解けなくちゃいけなかったような……。

コンテストへのリンク

No.2035 Tunnel

　自力AC。

　各マスが取り除かれるとき、一つ前取り除かれたマスより二個以上離れていることを使えばOK。

No.2036 Max Middle

　一応自力ACだが、最初、大きい数からシミュレーションしてTLEを出してしまった。

　A[i]とA[i+1]の大小関係だけ分かれば良いと気付くのが重要。

　一番左のものから操作を行うとすると、A[x-k]<A[x-k+1]<...<A[x]>A[x+1]のA[x]に操作したら、A[x-1], A[x-2], ..., A[x-k+1]に順番に操作でき、さらに、その操作後、操作した部分は単調増加になると分かる。これを使うと回数が計算できる。

　どんな操作を行っても回数は同じというのは、解説のように、<>が><になると考えれば確かに、という感じです（証明せずACしてしまった）。

No.2037 NAND Pyramid

　自力AC。

　実験したら、2x回やった結果が元の形と一致していると気付いた。最初だけ（1が一個のブロックがある場合？）違うことがあるようなので、何回かシミュレーションした後、前後を削っていけば良い。

No.2038 Strange Arrange

　自力AC。これは結構すぐ分かった。

　1, 3, 5,...番目を1にすると、偶数番目を全て2以上にしなくてはいけなくなる。次に、同じことを偶数番目について考えれば良い。2, 6, 10, ... を2にする。そうやって再帰的に構成していける。

yukicoder contest 358

　A一完。Rustで出ようとしたら、Rustと関係なくBが分からずに終了。

コンテストへのリンク

No.2057 Ising Model

　解説AC。

　まあ、全部-1か、1と-1の交互だよね、と提出してみたらWA。

　それ以外に、ただの「1 -1 1 -1 1 -1……」という交互ではなく、最初の1を-1にしたもの、という可能性があった。気付かなかった。

No.2058 Binary String

　自力AC。といっても、実験したら答えが分かっただけ。

　解説の証明は鮮やかですね。

No.2059 Odd Move Nim

　自力AC。

　これは、ちょっと考え付いて思いついた解法がそのまま答えでした。（証明もできたつもり）

No.2060 AND Sequence

　解説AC。

　bitcountに注目するとは思ったが、その後が分からず。

　解説を見たら、各bitごと独立と。言われてみたら当たり前のはずなのだが、見てもしばらく理解できなかったのはまずい。こういう問題では、bitごとに独立か考えるのは定石のはずなのに……。

　その後の桁DPパートはできました。

yukicoder contest 357

 　A、C二完。

コンテストへのリンク

No.2042 RGB Caps

　解説AC。コンテスト中はちょっと見て分からなくて飛ばしたとはいえ、ちょっと見た段階で分からなかったのはダメ。

　3個ずつ、Rが1個、Gが1個、Bが1個となるように並べていけば全ての場合を作れる。

No.2044 Infinite Nim

　解説AC。

　コンテスト中、

・-1以外のもののxor

・（-1の個数）% 2

　が答えに影響しそうなことが分かって、サンプルを元に適当に投げたらWA。解説を見て、-1の個数が奇数のときは常に先手が勝ちというのを見て、「あれ、それは一回考えたはずなのに？」となった。

　頭が働いていないと、一回考えたことも答えに反映させることを忘れてしまう……。

No.2046 Ans Mod? Mod Ans!

　解説AC。

　式変形すると、x<yであるようなy%xの総和を求めなくてはいけない、というところで詰まった。

　ここでさらに、

・y%x=y-x*(y//x)

　と式変形するのがポイント（だが、難しい）。

　y//xの総和ならBITを用いると、調和級数の計算量で求めることができる。

RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）

　pretest 66位、最終順位49位でした。ほぼツイッターのコピペですが、一応まとめておきます。ツイッターだと重くてAnimation GIFが貼れなかったので、こっちではそれを。Web版ビジュアライザの機能を使ったのですが、容量が結構大きくいですね。

コンテストへのリンク

・解法

　ある数字をEの字型で全てを繋げる。それが上手くいきそう（5000点くらい取れそう）なら二つの数字で、Eと∃を作る。

　Eと∃両方をちゃんと作れたのはほぼなく、K=5でNが大きいとき7000点くらい。
　Eは概ね作れたけど、Nが小さいときは無理で、そのときのフォロー方法はできませんでした（時々2000点とかになっている）。

・seed 1でScore = 5192

　二色結ぶのが上手くいかなかず、一色のみ結んだときはこんな感じ。

　Eと書いたけどEにはしてなくて、

　その数字が多い行いくつか決め打ち、そこにその数字を集める→行同士を繋ぐ。そのとき、どの列でつなげば一番コストが低いか、列を全探索

　としています。

・seed 7、Score = 1737。

　密集しているため、あまり集めたい行に集められずに移動は終了しています。

　その後は、1--x--1みたいに、ペナルティ一つで二つの連結成分を繋ぐことも使って頑張っています。

・seed 11、Score = 7402。

　Eと∃が両方そこそこ作れたパターン。上手くいってもこのくらいです。Eと∃を作ると書いたけど、縦と横を入れ替えたやつも試しました。

Codeforces Round #813 (Div. 2)

　Dが解けなかった。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #813 (Div. 2) ABCとE1。Dは誤読してWAを出した上誤読に気付いた後も解けてない。
B 後ろから二つずつswap
C 二分探索
D 隣接要素かmin(A)*2が直径になるとは気付いたが……。
E1 kを全探索。条件を満たさないのはlcm(i,j,k)がkか2kのとき。つまり、i,jが2*kの約数のときに絞られる。

— titia (@titia_til) August 13, 2022

D. Empty Graph

　重みがmin(A[l:r+1])でなく、min(A[l],A[r])だと誤読してWAを量産したけど、本来の問題も難しかった。

　解説ツイートを読んでAC。

　答えがx以上になるためには、

・全てx/2以上

・隣接要素の両方がx以上となる箇所がある

　が必要（と、考察するのが難しい）。

　判定問題が解けたので二分探索すればOK。

AtCoder Grand Contest 058

　Bまで二完。Bはここなどで既出だったらしい。

コンテストへのリンク

コンテスト後のツイート

C 「1と4」を「2と3」に繋ぐという方針が浮かんだが、その後の考察が進まず。
D、E　実験したが良い方針が出ず。DはA,Bを固定したら多項式になるっぽいのは分かった。

— titia (@titia_til) August 14, 2022

C - Planar Tree

　解説AC。

　「1と4」と「2と3」で分けて、「1と4」を「2と3」に繋げて消していき、全部消せたら（「2と3」のみ残ったら）OK、と考える方針は合っていたので、考え続けていれば解けた可能性はあるが、解法Stepを考えると1/4あたりまでしか辿り着けていなかったと思うので、ACまでは遠かったか。

　特に、同じ数字をつぶして良いということに気付いていなかったのが厳しい。

　まず、

・同じ数字をつぶす

・1と2が隣接→2だけ残す、3と4が隣接→3だけ残す

　として良いと気付くことが重要。

　そうすると、その後の操作では、

・...4 2 3...の4と3を結び、3だけ残す。（4 2を消す）

　というような操作しかなく、その操作で2と3のみが残れば良いので、2と4の個数、および、1と3の個数を比較すれば良いと分かる。