2完。Bを通したあと37.1。いいAGCだったけど、結果として平凡な順位なのがね。まあ結果はいいか悪いか普通かなので、普通のときまで落ち込んでたらやってられんけど。
A - 01 Matrix
各行で少ないほうが0であるような個数をXとして、同様に各列についてY、方程式を作り様子をうかがう（W*Aとか出てきてWAは嫌だなあと思う（縁起が悪いとかじゃなくて単純に精神ダメージがあるから困る））。とりあえずNoのケースを持ってこようと思い少し試すが見つからない。サンプルを見るが、ない！これはあからさまに怪しい。ただ、そんな都合よく作れるかなあという感覚があり、Noが存在しないと決めつけはしない。10分くらいして順位表を見ると青の人もけっこう通している。少しして、何も考えず構成しにいったら作れた。これがAGCだ！最近のAGCのAは変化球が多かったので、いいストレートが来ても打てなかった。悔しいけど、仕方ないところでもある。さて、書いて出したらWAになった。AとBが逆。入力が「H W A B」なのに、Hに対応するのがBっていう。まあ、サンプル2の出力をちゃんと視界に捉えながら何も考えず提出したのが悪いけど。でも、問題も悪いと思う。
小さいほうって条件がまるっきりわかってなかったね。最大公約数とか考えてかなりうまい数になってないと無理って感覚だった。一見同じように見えて実は全然違う世界に放り込まれてる。気づけないにしても、同じだと確信できないなら疑いたい。
B - Sorting a Segment
ある区間が昇順かは累積和でわかる。K=1がなくてK=Nはあるのか。操作はN-K+1通りしかない。K=4で124356みたいなケースを考え、昇順にした結果が同じになるなと気づく。そうなる条件を探って、隣の区間と同じになる条件を考えることに思い至り、それは（長さK+1の区間の中で）先頭が最小値で末尾が最大値になることだ。とりあえずセグ木でそれを実装してサンプルを試してみるが、さすがにこれだけでは通らない。そもそも順列が変化しない操作があり、それが2個以上あったらそれだけ種類数は減る。最初に考えたようにそれは累積和で検出できる。改めて考えを整理する。N-K+1個の操作を隣と結果が同じものをつなげて区間とし、違う区間同士が同じであるケースについては、変化しない操作の数を区間の末尾だけカウントすればいい（全体を数えて各区間の長さ-1を引く）。元から昇順の区間は連続して現れるか被らず離れて現れる、1243576みたいに断絶したら再び123457が現れることはない、そういうところも一応全部詰めて大丈夫そうなので実装（雑ではあるんだけど）。けっこう複雑だったんで、一発ACは嬉しい。
C - LCMs
まあ100万なので1000までの素数168個を列挙して素因数分解したい。単純に行くと各A_iに注目して他のAたちとの和をO(N)かけずに何とか求める、その際に最大公約数で求めてもよさそう、みたいな。ただ、これ「和」なんだよね。掛け算した結果の和。積ならまだ希望がありそうだけど。だから他の方針を考えようとするが、わからない。和。これは無理だ。
D - Unique Path
3頂点を選んで0 0 0ならOKみたいな。全体をグラフにしちゃうのありそうだよね。しかし、1 1 0で多重辺はダメだから他の頂点を経由する必要があるし、とんでもなく複雑。これは時間内には無理だ。
