ABC349

5完。今日は、先週のABCの復習にようやく着手できた（は？）。

A - Zero Sum Game

Aとは思えない考察難度。持ち点の総和が0のまま変化しないことに注目する。

B - Commencement

まあ文字をカウントして、その（正の）個数をカウントして、2以外があるか調べる。コード自体はこんな感じで楽に書けるんだろうなと最初からわかってはいる。しかし問題文が何を言っているのかイメージが全くできない。大体の予想はできても、実装に入れるほどのくっきりしたイメージはできない。なんかコンテスト開始前に気づいたら2分前でおしっこに行きそびれたんだけど、ここで行った。そのくらい難しい。戻ってきてじっくり読み直して実装。

C - Airport Code

かなり怖い見た目だが、よく読むと素直な書き方。どちらかの条件を満たすかという問題なので一つずつ判定していけばいい。部分列になってるかの関数を書いておく（この貪欲はDPとかでおなじみ）。TがSの部分列ならYesで、そうでないときTの最初の2文字を取り出した文字列がSの部分列でかつTの末尾が'X'ならYes、そうでないときNo。

サンプル通らず。for (auto &c : t) と書いてTを小文字に変換したつもりがcではなくtに操作していた（コンパイル通るのが怖いところ）。また、Tを小文字に変換したのを忘れて大文字の'X'で判定していた。

D - Divide Interval

セグ木じゃんと思い、自分のセグ木からコードを持ってくる。そのままでACできるわけではないので、正面から考えるか、このコードをいじってなんとかするかで迷う。できそうなので後者を選択。セグ木のノードを観察すると、1段毎にオフセットと倍率が2倍ずつ変化していく。サイズ2^60のセグ木として、普通に処理していく。

E - Weighted Tic-Tac-Toe

9!なら間に合う。普通にネガマックス法で書いていく。手番と得点差と残り手数を持って再帰。得点差は高橋君目線なので、手番が違えば符号反転させて使う。手番から見たスコアを返すことに注意。スコアの最大値求めるのに初期値が0でやばかった（-INFにする）。まあいつものやつ。最初、9手打ってから判定してて危なかった。コード量の半分は三目並べの判定。計算量は問題ないが、一応探索ノード数を出力させて変なことになってないか確認してから提出。

F - Subsequence LCM

アルゴ式の高度合成数を見ると、10^16以下の制約だと4万個以上の約数がありえて間に合わなそう。とりあえず素朴なDPを書く。よくわからないので提出してみたら、TLEじゃなくてWAでびっくりした。Aをintで受け取ってる。書き直したときにintになってしまったのだ。嘘っぽいものを投げ続けていたが、安定のTLE。

10^16で素因数分解させてくるというのは発想になかった。まあ間に合うのはわかるので、あまりよくない思い込みだけど。

（追記）各素因数がMと同じ個数あるかだけが重要で、だからビットで持てるんだね（約数の個数ぶん必要になると思ってた）。このことにコンテスト終了時点で気づいていなかったのは酷い。素因数分解しない前提で考えてたから抜けやすくはあったろうけど。（素因数の種類数をKとして）2^K種類に分類できたらそれぞれの個数だけわかればいいというのも見えにくい。ここまでわかれば、あとは普通にDP。2重ループで自分にはやや見えにくかったが、特に難しいところはない。高速ゼータ変換を使った方法も、各ビットパターンに含まれる個数の和を高速ゼータ変換で求めて、選び方を2のそれ乗で求めて、逆変換でそれぞれの通り数が求まるという自然な流れだった。

（追記2）ユーザー解説で素因数分解しない解法があったのでやった。Mの約数であるようなA_iに対して、各素因数をMと同じ個数持っていなかったら0個に潰してしまう。そういう半端な素因数はA_iとM/A_iの両方に含まれるので、gcdを上手く使うとできる。これをビットで持つために素因数毎に分解したいが、変換後のAで違うもの同士をぶつければgcdで分解していけそうだ。ここは少し考えたが、結局解説の方法が良いということに。分解したリストを持っておいて（最初は空）、リストにあるもので割れるだけ割って残ったものを今度はgcdで調べて、共通部分があったらそれをリストに追加して元の要素はそれ割る（2個に分ける）（A_iを割り切らないものしかないので1が追加されることはない）。リストが完成したとき、素因数毎にバラバラになっている保証はないが問題ない。提出前に解説を読み直して気づいたが、リストの総積がMに足りなければ答えは0通り（あぶなかった）。あとはそのリストを使ってビットに変換して高速ゼータ変換に合流する。まあコンテスト中にできる分量ではないかもしれないが、実際のコンテスト中にはこういうのを思いつきたくて考えていたのだ。解説を書いた人ありがとう。

ABC348

ABCEFの5完。

A - Penalty Kick

ちゃんと問題文読むのあきらめて、サンプルとかも見てそれっぽいのを書いて提出したなあ。

B - Farthest Point

距離の2乗は整数なのでそれで比較する。番号が小さい順にやればよい。

C - Colorful Beans

mapを使って色毎においしさの最小値を求めその最大値が答え。高速化したくなるのをぐっとこらえる。

D - Medicines on Grid

サンプル1の説明を見て、薬を使わないことも可能だと確認。スタート地点に薬がないと詰み。薬は持ち運びできない。これで問題を把握できた。実装が重くなる予感がするが、そもそも難しい。薬がある場所からBFSして、その場で薬を使ったあとに別の薬やゴールへ行けるかは判定できる。てことはO(N)頂点の有向グラフが作れて、そこでDFSしてスタートからゴールへ行けるか判定すればよさそう。たぶん解けたので、飛ばした（21:18）。

EFを通して戻ってくる。頑張って実装スピード重視で書き、15分くらいでとりあえず書き上がって提出してWA。添え字のi,jが2種類あったのと、有向辺の行き先かの判定が普通に間違ってたのと、4方向のループの添え字がhで高さのhと被ってたので、コンテスト終了後も含め3WA。

E - Minimize Sum of Distances

C_iが頂点数のようなものだとすぐ気づけてよかった。Cの合計とD（距離）の合計を管理すればよさそう。1つの辺を使うとCのぶんだけDが増える。これオーバーフローしないか？と思って計算すると、ギリギリlong longに収まる。なるほどNが微妙に小さいのはそのためか。まず、DFSして自分と自分より下のぶんを計算する。もっかいDFSして、自分より上のぶんを足す（けっこう大変）。最後に最小値を求めるところでは、初期値に頂点1の値を使う。サンプルが合わず、原因はCの合計の変数をC_iの変数に間違って書いてたことだったが、デバッグに15分くらいかかった。

（追記）全方位木DPで解き直した。確かに準備しておけばコーディング量自体はかなり少ない。

F - Oddly Similar

AtCoderで400万個の数値の入力はかなり多い。入力だけでTLEする人も出そうな。さすがに、2000*2000*999は4*10^9くらいなのでダメそう（書き方によってはいけるらしい）。2000*2000の配列を用意して、一致する個数をある程度高速に書き込めれば（あるいは書き込んだことにできれば）よさそうだが、それができるか。数列の位置毎に考えていいことに気づく。一つの位置に最大で999種類の数があり、同じ数毎にその個数の2乗の個数の場所に1を足したい。種類数が多いぶんには（計算量的に）困らなそう？問題文を読み直すと個数の偶奇だけわかればいいから足すんじゃなくてxorでいい。かなり難しそうに思ってそれでもかじりついて考えていたが、bitsetを思いついて確信はないが実装に入った。999種類の数毎にxorしたい位置を1にして、N個の数列から見て実際にxorする。一つの位置につきN^2/64程度の計算回数でそれをM回なので間に合う。実装で、数列の番号をi、数列内の位置をjとしていたので、問題文のi,jが両方数列の番号であることを忘れてNとMを間違えて最初サンプルが合わなかった。

AGC066

Bのみ1完。AGCだった。Aを読んで少し考えて難しいのでBも読んで、「AGCだ～」とにやけた（困りながら）。

A - Adjacent Difference

コストの制約は、マスあたりd/2以下ということ。ということは何か簡単な方法がありそうだが。AB両方読んでどちらもわからず、面白そうなBに集中した。

Bを通して戻ってきた。思ったより難しい。

3 10
0 5 10
0 5 10
0 5 10

このケースが手で解くのも難しい。頑張ったら解けたけど、これができるプログラムを書ける気はしない。左上隅のマスを4にしたらダメそうだけど5から10は大丈夫で、そこから何かを感じとるべきだったのかもしれないが。

どうやっても解けない。最初から解ける見た目だったけど、思ってたのと違う難しさだと気づいたときには残り15分。残り10分になったら体が完全にあきらめていて、その状態でやってもしょうがないのでCやEを読むなどしていた。

（追記）色々な解法ツイートなどを見ていたが、なかなか具体的なものが見えずやる気が出なかった。公式のヒントを頭に入れて布団に入ったらあっさり解けた気がした（ここで初めて腰を入れて考えた）。mod d*2で考えて0とdを市松模様に配置すればいいが、0とdにするコストの和はdなので全部入れ替えれば片方は平均d/2以下になる（すごい）。今実装して実際に書けて、ACした。終わってみれば、最初に感じたイメージのままの解法だった。市松模様は早い段階で見えていたし、そこそこの自由度があるというのも観察からわかっていた。何より、コストがマスあたりd/2になるというのが。わざとらしくそういう設定の問題にしてあるのにそれが見えなかった。本当にAGCの解法って当たり前のことばかりなんだけど、俺はそんなことすら知らないのだ（だからAGCは面白いんだけど）。

B - Decreasing Digit Sums

2倍すると桁和が減っていくものを見つける。とりあえず実験コードを書く。ただし、xを全探索するようなことはしない。入力のNによらずN=50の答えを出力するだけの問題だから、小さいNの答えから類推する感じではないと思った。10^12を2で割っていき桁和を観察する。だんだん増えていくが、減ることもある。2倍して減るやつではなく2で割ってして増えるやつを探すのは、方針としてはよさそう。ここで、1000030000のようにくっつければ10000の桁和と30000の桁和の和が得られると気づく。また、10の冪を2で割っていくと0でない桁が増えていくから、桁和が単調増加でないにせよ増えていく傾向は確実にありそうだと気づく。これで可能性が見えた（同じ傾向のものをたくさん足せば単調増加になりそう）。ただ、「こんな泥臭い実験しないと解けないようなものをAGCで出すか？」というのが気になった。が、他に何も見えないのでこれをやる。10000桁以内という制約があるのでその範囲で（最初10000/50が20くらいだと勘違いしていた）。10^50に何かの整数を掛けたものをいくつか使う。2倍だとすぐ合流してしまうと思ったけど、ずれてるのはそれはそれでいいとあとになって気づいた。20まで試して10以上は2桁に分ける処理が必要だとあとで気づいたり。60桁（10^50に99を掛けると52桁）を100個なら6000桁でOKなので、その範囲でできてくれと思いながら1から99までの99個で試すと最初だけダメ。そこで、1を2回入れることにすると、嬉しいことに狭義単調増加となった。あとはこれを構築して50回2で割ればいい。この部分および検算にGMPを使ったが、あとから考えたら2で割る処理は既に書いてあったので不要ではあった。出力させて、0が思ったより多く連続していて理由がしばらくわからなかったが、何回も2で割って小さくなったので頭に大量の0が付くのだった。GMPの整数をintにキャストする方法がわからず、10で割ったあまりが知りたいので0から9までのintをmpz_classにキャストして等しいか調べる力技を使った（こういうのひねり出すのわりと好き）。結果的にGMPを使ったのは時間の無駄だったが、まあ構築ミスやそもそもの考察ミスなどの可能性は高かったと思うので、悪い立ち回りではなかったはず。

（追記）GMPでint（正確にはlong）に変換するのはget_si()だったね。get_uiはどっかで見かけた記憶があるけど、uiがそういう意味とは思わなかった。

ABC347

5完。Eが面白かった。

A - Divisible

当てはまるものをvectorに突っ込んでいく。これは、簡単だけど実装だけで1分行ってしまうやつ。

あ、出力の「昇順に出力せよ」を読んでなかった（問題文のところはちゃんと読んだ）。

B - Substring

愚直に全列挙してstd::setに突っ込む。

C - Ideal Holidays

Dは周期A+Bで割ったあまりに置き換えてsort, uniqueしておく。休日をどこで始めるか全探索する。Dの先頭かどうかで場合分けして、先頭でないときは末尾が次の週なのでA+Bを足す（ここがオーバーフローしないか不安だったのでllにした）。典型ではあるけどけっこう重く10分以上かかった。

D - Popcount and XOR

パッと見めちゃくちゃ簡単だが、ちゃんと考えていくとなかなか大変。popcountを考えると、popcount(C)がa+bより大きかったら作れない。あとは（XとYでビットを重ねる毎にpopcountが2減るので）偶奇が一致していればいいかなと思ったら、なんとCが2^60未満なのにXYも2^60未満で不自由だ。となると、XとYで両方立ってるビット位置の個数としてどんなものがありえるか全部知る必要がある。個数が最も多いのは簡単、最も少ないのは、Xは左からYは右から1を配置してmax(a + b - 60, 0)個。作れるpopcountの範囲がわかるので、その範囲かつa+bとpopcount(C)のが差が偶数なら作れる、そうでないなら作れない。重なる個数は、(a + b - popcount(C)) / 2。a,bからこれを予め引いておく（これに気づかず出力がおかしかった）。あとは、Cの下位から見てその01によって処理を分けて、0だったら重なる個数、1だったらaかbが残っているなら1にする。サンプルと一致しないので、popcount(X)とpopcount(Y)とX^Yを出力して入力と合っているか目視で確認する（バグを発見）。これで解けてるのが不思議な見た目だが、合ってるはずなので提出（軽くは確認した）。

E - Set Add Query

数列の要素を横に並べて、対応するインデックスがSに含まれるかで印を付けて、そういう図を描いて全然わからなかったけど、図を縦に伸ばすことで解けた。加算する値がSと関係なく毎回与えられるとして考えると見えやすい。Sから削除されるたびに、（オンオフで考えて）オンだった区間の和を足す（最後までSに残っていたものは別途処理）。加算する値の累積和と、いつ（何番目のクエリで）オンになったか（現在オフであれば-1）を持っておく。

なんか違和感のある設定だったけど、原案ではSのサイズではなくその逆数を足していたらしい。なるほどそれなら自然だ。でも小数ジャッジになるから変更されたと。

F - Non-overlapping Squares

とりあえず2次元累積和と、各マスを左上隅にした正方形の和を求める。2個でさえできない。解ける見た目をしていない。最後の10分は座ってるだけになった。フローとか思ったけどできるわけないし。1次元ならDPできる。1個を固定しても、順番に配置しても、2個でさえ難しく、3個なんて関係性が増えすぎてできるわけがない。

いやあ3つの長方形そういえば聞いた覚えはあるが、今回のようなギッチリ詰まってないやつでも当然そうなるのかいやあ。

G - Grid Coloring 2

順位表見て、あまり考えてない。AHCにありそうな設定。大体の答えは簡単に求まりそうだが、厳密にとなるとどういう話になるんだろうね。いやフローは全く考えなかった。どうやるのかわからんけど。