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にありそうな設定。大体の答えは簡単に求まりそうだが、厳密にとなるとどういう話になるんだろうね。いやフローは全く考えなかった。どうやるのかわからんけど。

ARC175

2完。コンテスト時間が短すぎる。前菜食べたら終わってる。まあシンプルに頭が悪い。ABにこのくらい時間かかるのは仕方ないと思うけどCはなあ。Aもダメか。しかしいくら頭が悪いからって、Dを考えることもなく終わるって酷すぎる仕打ち。悲しい。

（追記）コンテスト終盤、考えようとしても集中できなかったな。もう新規ACが不可能に近い時間になると、（ACできない焦りとは別に）むしろホッとしていた。考えなくて済むので。夜中で大声出せなくてつらい。なんでこんなこともできないんだ。

A - Spoon Taking Problem

人P_1が行動した時点で「全員がスプーンを取るなら、全員についてどちら側を取るかが決まっている」と気づくのに時間がかかった。そこから、全員が同じ側のを取ると気づくのにも時間がかかった。あとは、初手を左と右に固定してそれぞれを解く。N個のスプーンそれぞれが残っているかを管理しておく。両方残っているとき違う側に置くしかないなら0倍に、そうでないときは片方だけ残っていて（同じ側を取っているので常に1個は残っている）'?'であればどっちでもいいので2倍にする。最初の人の行動は場合分けしなくていい（書き上がってからわかった）。

左右を0,1にするか-1,1にするかでかなり迷った（実装を2回書き換えた）。左右のスプーンの位置を、現在の人の位置を基準として-1,+1としていたが、正しくは0,+1だった（mod Nとるので差が1なら何でもいい）。

B - Parenthesis Arrangement

個数が合っていて、累積和が負にならなければよい。できるだけ外側から置き換えれば、そこより内側全部の累積和が+2されるので得。「'('が足りない場合、できるだけ左の')'を置換して損しないように思う」ところまで行ってから、')'が足りないとき右の'('からやっていいと気づくまでにもタイムラグがある。入れ替え操作は、置き換え操作と組み合わせても意味がなさそう（同じ文字を入れ替えるのは意味がなくて、どちらかを置き換えた場合そうなる）。ということで、まず個数が合わない分を外側から貪欲に置き換え、次に累積和の最小値が負である間（外側からやれば1回の入れ替え操作で常に+2されるはず）置き換え2回か入れ替え1回の安いほう（個数を合わせたあとで奇数回の置き換え操作が必要になることはなさそう）で操作することを外側から繰り返す。

昨日のABCのFでバグらせた経験から、assertみたいなの（if (ないはずの状態) throw;）をたくさん置いた。これがたくさん引っかかって大変だった。文字を-1,1に置き換える操作を2回していて破滅していた（都度置き換えるのではなく最初にやっておこうとコピペしたときに消し忘れた）。操作1回で累積和が1しか変化しないように書いていた（実際は2）。累積和の最小値は偶数と限らないことに気づいていなかった。

C - Jumping Through Intervals

難しいのでとりあえず辞書順の条件は外して考える。横に直進できるだけして、できなくなったら上下に動く。スタートを決めるのが難しいので、ゴールからやってみる（今考えると辞書順の条件がないなら対称なんだよな）。直進できるだけして上に行くか下に行くかで場合分け。辞書順も考慮して、一番下から始めてあとから必要なら引っ張り上げる感じ。上に行くのは簡単で、しかし実装が終わったとき簡単な側だったことに絶望した。下に行くのは、仮に一番下へ行くとしてmaxをとって下に張り付きながら（ゴール方向へ）戻る。しかし、上に行ってコストが増加しないケースとそうでないケースがあると気づき、前回が上に行ったか下に行ったかも記録して場合分けが必要。また、最後まで直進できたときの調整も難しい。いつの間にか非常に複雑な実装をしていたことに気づかなかった。気づいたときには残り時間がない。

（追記）自力で未証明ACした。0を初期値とし、LRでstd::clampしながら暫定解を作る。これにより真の解の末尾がわかることを期待している。今度はその末尾から逆向きに同じことをやる。これにより真の解の先頭がわかることを期待している。あとは、先頭からLRではなくLと暫定解（末尾が合っていることが重要）でclampしていき（値を大きくするのをできるだけ後回しにしている）、これが真の解になっていることを期待する。

D - LIS on Tree 2

（追記）1時間くらいでAC。作れる最小と最大は簡単にわかる。その間は全部できそう。部分木で稼げるぶんを引けるだけ引いて部分木の問題に帰着させる方針を考えていたが、ちょっと違いそう。LISについての理解の浅さが気になるが、とりあえず根以外の各頂点のオンオフを決めることに。部分木のサイズを求めておき、その頂点をオンにすることでそのサイズぶんだけ稼げるとする。サイズが大きい順にオンオフを決めれば確実だが、DFSの順に決めても大丈夫そうだ（部分木のサイズのぶんだけ子孫がいるのでわりと何でも作れる）。KがN未満のときはNo、全部引いても残っていたらNo。根の寄与Nは先に引いておいてDFSの中では処理しない（サンプルが合わなかった）。あとは、オンオフを具体的な順序に変える。深さdを持ち、根を基準の0としてオンならd、オフなら-dとして、これでLISの長さは根からのパス上のオンの個数以上になり、またオンの個数より大きくはならないだろう。これで順序が決まった。これを順列に変換するのが難しいと思っていたが、少し考えると単にこの順序を保てばいいだけなので、インデックス付きでソートしてソートされた順に1から割り当てるだけでよかった。順序が重要なのは根からのパス上でだけなので兄弟とかは気にしなくていい。

ABC346

5完。Fが通せずゴミのような気分に。

A - Adjacent Product

これ1分切ったのはえらい。

B - Piano

blockquoteになってる部分を読んで損した。

無限というのは難しい。条件を満たす部分文字列はW+B文字になる。2乗が間に合うので、開始地点を全探索すればいい。サンプルが通って見直しをしたら、開始地点をW+B通り試すようになっていて、"wbwbwwbwbwbw"の長さ通りに直した。あぶねー（2乗って何の2乗だよ）。12通り試せば、全部の状況をカバーできる。s[(i + j) % n] == 'w' みたいにしてwをカウントして12通りのうち一つでもWと一致すればYes。かなりの総合力がないと苦戦しそうな問題。

C - Σ

ちょっと待って今気づいたけど10^9じゃなくて2*10^9なの。最初2*10^5に空目してたのはそのせいかあ。気づいてからも、10^9だと思って解いていた。そっか、10^9だと愚直が通ってしまうのか。

2*10^5だと思って迷走していたけど、10^9となれば覚悟が決まる。Aをsortしてuniqueして、1からKまでの整数の和から引いていく。K以下のやつのみ引くのだと書き始めてから気づいて危ない。これで本当に正しいという証明もできない。いや、証明はできるけどその証明が正しいという実感を得る方法がわからないという感じか。

D - Gomamayo Sequence

手で例を作って観察すると、同じ2文字が2連続になる場所がどこかN-1通りとその同じ文字が0か1かの2通りで良い文字列は2*(N-1)通りだとわかる。少し考えると、左右からやるいつものになる。これもう飽きた。

DPでもできるらしいです。初期値の設定が面倒。遷移も難しくはない普通のDPだが、自分は実装するまで形が見えなかった。

問題名見てなかったけどゴママヨじゃん！

E - Paint

操作を逆から見るやつ。最初から全部色0になってるのは、逆から見て最後に全部色0で塗ればいい。今気づいたけど、色0で縦横両方塗り潰してたけど横だけでいい。行を塗るときは、その行を塗ったことがあれば何もしない、初めてなら、幅Wから列を塗った回数を引いたぶんだけその色が増える。塗ったかどうかと回数を管理するのだが、長さ2の配列で縦横まとめてやるべきだったかなあ。シンプルに書ける確信がなくてベタ書きしてしまった。なんで全部の色について出力させないんだろう。

F - SSttrriinngg in StringString

かなりいかつい見た目で苦労するが、問題の意味がわかってしまえば、二分探索で貪欲に部分列をとっていくだけ。各文字について文字数の累積和を前計算しておく。答えが0になるケース（Tの文字でSに含まれないものがある場合）は先に判定しておく。Sが長くてTが短いとき答えはNよりだいぶ大きくなることがあるので、二分探索の上限は10^18とかにしておく。あとは、何個目のSの何文字目まで使ったか管理しながら、割り算と累積和の二分探索で進めていく。

サンプルが全部0だったのは、a[h][i + 1] = a[h][i] + (s[i] == 'a' + h); の括弧が抜けていたからだった。直しても微妙に合わないのは、割り算であまりが0のとき、例えばSの3個分の文字を使うとき必ず3個分進むようになっていて実はその文字があるところだけ使えばいいから3個分丸々は進まなくていいというやつだった。サンプルが合って提出してWA。Sが3個と1文字というときSは4個使うのに3個としていた。あとからちゃんと詰めようと思っていたところを忘れている。負荷が高いので仕方ないというかいちいちメモするしかないのかな。直して提出してまたWA。10^18を何回も足したらオーバーフローするのでNを超えたらさっさとfalseを返すようにする。またWA。ていうかWAが提出のたびに減っているとはいえ大量にあり何か根本的に間違っていそう。結局わからないままコンテストが終わった。解説のコードを追加して手元で適当なテストケースを作り自分のコードと出力が異なるものを見つける（すぐに見つかった）。確かに間違っているので、どこでおかしくなっているか変数の中身を出力させながら絞り込んでいくと、a[h][l] - a[h][i] と2回書いてその2回の間にiを変更していた。2回書く（コピペする）ときに、変数に入れようかと検討はしたが余裕がなくてそのままにしてしまった。

G - Alone

Gまで読んで順位表を見て、しばらくFG交互に考えていたが、Gはわからず、Fが素直にできると気づいてFに専念。

（追記）3週間以上経ってしまったが、AC。まず、解説にあったLibrary Checkerの問題をやる。こちらは座標圧縮が必要。区間の最小値と最小値の個数を持って区間加算という、どうやって思いつくか全くわからないものを考えると確かに解けている。遅延セグ木の実装もわりと簡単だ。要素数を1増やしてそこに0個の0を入れておくことで常に全体の最小値を0にできる。元の問題に戻ると、LとしてありえるN通りを横に、RとしてありえるN通り（こちらは何通りでもいい）を縦にとって、条件を満たす(L, R)についてそれらが交わるマスを塗って、塗られたマスの面積を求める問題にする。A_iの値毎に位置を記録していくつかの長方形を追加して面積を求めればよい。