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の値毎に位置を記録していくつかの長方形を追加して面積を求めればよい。

ARC174

4完。パフォーマンス2000ジャストは初。解説放送をDまで聞いて、その後はmomokenの配信を聞いていた。

A - A Multiply

0倍もあって怖い。累積和で、どの2点をとると一番増分が大きくなるかな、というので少し時間を使ってしまったが、前から見て最小値を更新しながら右側を全探索すればいい。最初は0倍が特異点かと思ってたけど、この内容だと1倍が基準なんだね。

今回は、同じことを2回書かないように、Cが1より小さいなら処理の前後で累積和の符号反転をしたけど、けっこう考えることが増えたので、どっちがよかったのか。ただ、1回で済ますメリットは大きい。2回書くとバグのありえる場所が2倍になるというのもあるけど、1回ならバグが顕在化する機会が2倍になるのがすごく大きい。

B - Bought Review

3を基準に貯金がいくつみたいなやつ。借金返済は、4か5でやるしかないが、当然安いほうを使う。ただし、5のほうは2個単位なので半端の1個を4に回すケースも考える（書き上がるくらいのタイミングで気づいた）。

C - Catastrophic Roulette

めちゃくちゃ簡単に見えたが、考えてみると自分にはけっこう大変だった。実際簡単なのだとは思うけど。

それまでに出た整数の個数がKからK+1に増えるまでに、そのときの手番側と反対側にどれだけ罰金が来るかというのを計算する。それとは独立に、それまでに出た整数の個数がKになったとき先攻の手番である確率も求める。これで解けるはず。手番は無限級数でまあ簡単。罰金がなんか難しくて、連立方程式にしたらまずその方程式で合ってるのか自信が持てないし、解こうとしたら二次方程式が出てきて一旦退く。よく考えるとKが増えるまでの手数がわかれば罰金もわかるのだった（最後以外全部罰金、これにここで初めて気づく）。これも無限級数だが、こちらはやや難しい（何も困難はないがΣA^iとΣi*A^iの違いでちょっと段階が増えるだけで負荷がかかってしまう）。かなり頑張って時間もかけて計算した。最初の手番と反対の期待値を求めて、手番の確率を使って答えの変数に足していく。

サンプルなかなか通らなくて、(1 - p) * (1 - p) と 1 - p * p を書き間違えるのを2箇所やってた。先攻の手番になってる確率を出力させたら2になっていた。modintとdoubleを切り替える仕組み用意しといたほうがいいかな。

気にせず割り算してたら673msもかかってごめんなさい。分母がmod 998244353で0になるかを全然意識してなかったの解説見て初めて気づいて、よくない（気づかないほうがタイムはよくなるというのが嫌だね）。

D - Digit vs Square Root

実験してそれを実装するだけ。実装でけっこう時間使ってしまった。[1, N+1)と指定した区間の共通部分の長さを返す関数を作って、条件を満たすO(log(N))個の区間を調べる。実験コードを使って答え合わせするが、普通に間違っている（サンプルは通る）。100倍していくのかと思ったけど、10倍していって (t - 2) * t で 998000 を作ったりするんだ。

完全に実験だけで、あとは順位表でペナがそこまで多くないのを見て提出。Nが大きいときにこの規則性が崩れるのではないかと不安だった（残り時間が減ってくると、その不安よりもとにかくACの可能性があるコードを提出しようになってくる）。解説放送を見ると、なるほど10の冪に近そうだとは思えた。

E - Existence Counting

まず2乗を書く。「tが含まれない」を求めて全体から引く方針。combとpermを間違えていた。next_permutationに0と1を入れてcombにするイメージだったけど普通に間違っていた。それでサンプル1は合ったけどサンプル2が合わずに終了。

（追記）どこが間違っているか、どうしてもわからなかったので、手元でN=8のランダムケースを作り愚直と比較していく。K=2で答えが1だけ違うとかになったのでそこを狙う。そもそもどういう方法でやっているかというと、まずt関係なくP未満の個数を求めておき、そこからtを含まないP未満の個数を引く。辞書順でP未満のものを求めているので、P以下にするためtがPに含まれるなら1を足す。で、どこでずれてるのか条件に合うものを全列挙させたりして見ていくが、なんかもう1ずれる場所が感覚と反対で何をしていいのか全くガイドがない状態でつらかった。結局、Pの各要素について自分より左で自分より小さいものが何個あるかを前計算しておいて引く必要があった。permで求めるところだけでなくP未満を作る（現在の位置での）先頭の選択肢も減るよね気づかなかった。

これで2乗が書けたので高速化するだけ。なんとかできそうだ。前計算の部分は、BITを使えばいい。t毎の計算も、BITにmintを乗せて使う。t（tを含まないものを数えている）がP_iより小さいとき、P未満を作るための選択肢が1個減るので、最初から全部1を引いておいて、tの昇順で処理するときにtと等しいP_iが存在すればその分を足してBIT更新（iを求めるテーブルを作っておく）。P_iとtが一致したら打ち切るのでそこまでの和もBITで求まる。もう何時間かかったかわからないが、素直に考えていけば解ける問題だった。

ABC345

ABCDFの5完。久しぶりにABCでいい順位。運も良かった（Dで計算量を確認せずに提出してAC）。Dが重実装（面倒というよりループが深いので書き切るために高い能力が要る）でEも難しく、いいパフォを取るのは半ばあきらめていたが、Fが（おそらくDEが難しいせいで）あまり解かれておらず、結果として早解き（？）で橙パフォ（ABCのカンスト）。

A - Leftrightarrow

"<>"は条件を満たさないけどSの長さは3以上なので気にしなくていい。あとは先頭と末尾と真ん中が全部合ってるか確認すればいい。

B - Integer Division Returns

10で割って切り上げ。X以上で最も小さい10の倍数を得るのは自分のライブラリでできる。それを使えるのか、どう使うのかが最初なかなかわからなかったが、まあ使える。その10の倍数を10で割れば答え。これが本当に正しいのかの証明はすぐにわからなかったが、このしっかりしたサンプルが通っているので大丈夫と判断して提出。まあ10で割った世界だと1の倍数を探すことになり、割る前だと10の倍数を探すことに相当ということで正しいね。

なんとABC239で同様の問題が。問題名まで意識してReturnsを付けている。今回のほうが悩んでしまったな。

C - One Time Swap

ARCのAか？ちょうど1回の操作。元の文字列と同じになるものがあるときとないときがある。操作の位置が違っても結果同じ文字列になることもある。まず、同じ文字が複数含まれているかで場合分け（同じ文字が複数あるときのみ元の文字列と同じものが作れる）。次に、違う2文字を交換するときを考えると、実は元の文字列とその2箇所だけ違った文字列が得られる（操作を区別できる）（いや当たり前なんだけど全然見えてなかった）。つまり解法としては、まず英小文字をカウントしておき、2文字以上のものがあれば答えに1を足す、次に操作の個数（N*(N-1)/2）を足す、最後に足しすぎたぶん（同じ文字を交換したとき）を引く。

D - Tiling

「回転したり裏返したりして置かれていても良い」とあるので警戒したが、タイルはただの長方形だった（裏返しても同じで回転は2通りだけ）。最近はこういうの飛ばさないことが多い。もうちょっと飛ばしたほうがいいというのはけっこう言ってる気がするけど。飛ばしたところであとの問題も典型だからなあって。今回は結果オーライだったけど、やっぱ飛ばしたほうがいいよな。まあ、やる気がないから飛ばさないんだ。あと今回は方針がすぐ見えたし、見えてなかった実装の難しさにやられていたので、普通に考える価値はあるんだよな。コンテスト中だと混乱をどうにかごまかすという動きになってしまい微妙だけど。

タイルの順番と向きを全探索する。7!*2^7でググると100万よりは小さい。そもそも順番とは何かという話だが、条件を満たす置き方があったとき、適切な順番と向きを設定すれば、まだ置いてないマスのうち座標の辞書順が最小のものにタイルの左上隅が来るように置くことを繰り返して置けなくなったらやめることでその置き方になるので、順番と向きを全探索すればよい。順番と向きを決めたとき、まだ置いてない場所を探索し（合計でO(H*W)）、置けるか判定して（ここの計算量があやしい）置けるなら置く（合計でO(H*W)）。あやしいところを除くとO(N!*2^N*H*W)で間に合う。サンプルが合わない（この時点で時刻は21:35）のでEへ。

Fを通して戻ってくると、そもそも順列を使ってなかった。直してサンプルは合ったので、少し迷ったけど提出してAC。結局計算量はあやしいままだった。今考えて、置けないときは、その順番と向きを調べるのはそこで終わりなんだから、結局O(H*W)には収まっているか。ほんとか？breakでどこに抜けるのかとか全然把握できなかったんだよな。これ素早くきれいに書ける人はほんとに実力がある。

（追記）再帰で書き直した。再帰のが見やすいコードになる。まだ置いてない場所を探すのは関数の最初に1回。置けたら再帰。whileやifが深くなって混乱してたのが解消された。ただし、置いたのを戻す処理が必要になる。置いてない場所を探してマス目の外に出たら常にYesなの気づいてなかった。また、こういう全探索をするときNは小さいので、どのタイルが残っているかをビットで持てばいいと気づいた。countr_zeroで位置がわかり、l &= l - 1 で消せる。

E - Colorful Subsequence

連続する同じ色の中からは最大価値を1個選ぶ（結局DPするならこれは必要ないかな）。そこまでにK個を超えて消費したら-1。そうでないとき、残った個数を消費するために、同じ色が隣り合わないように除いていく必要がある。難しい。DP。トイレ行ってそこで考えが整理されたけど、結局K^2が掛かってくる。Fへ。

FとDを通して戻ってくる。TL5秒だしセグ木使えないかなと考えていると、セグ木の長さはK+1とかでいいのでlog(K)も小さめではありワンチャン間に合いそう。自分と同じ色のところだけ都度変更しても全体ではO(N)回になるかな。まあそれをK回やってlogもかかるので重いけど。んでセグ木も回数が違うものの最小値（失う価値の最小値）を得る必要があるから、なんかもうずらしてずらして実装したくないしほんとに実現できるのかっていう。

（追記）2つ記録しておけばいいというのを聞いて、その通りにやる。ずっと、最後に置いたボールの位置を状態としていたが、解説を見たら単に現在の位置で、確かにそう考えればデータ構造要らない。じゃあ色の条件を除いた普通のDPを思い浮かべて書いていくかと思ったが、それ（自分にとって簡単であるはず）もすぐ出てこなくて、こういうDPに興味がないのかなと思った。普通のDPと比べて、ボールを置く処理（そのボールの色しかなくなり2位が-INFになる）と、いいとこ取りの合成が必要になる。2位は必ず1位と違う色であるというのが重要。頑張って書くとサンプルが通る。削除数の降順にやればin-placeでできるのでそのように書き直して提出、WA。色c価値vのボールを置くとき、色が同じ場合にvを足してなかった。三項演算子の優先順位がわかってない人みたいになったけど、まあ負荷が高いとこういうことも起こる。

F - Many Lamps

なんか最大マッチングとか調べてたけど、よく見ると操作回数には余裕がある。ていうか同じ辺の操作を2回以上する意味はない（回数の偶奇のみが結果に影響する）から、実質的に回数制限はない。操作で変化するついてるランプの個数は偶数なのでKが奇数はNo。グラフが連結とは書いてないのが怖い。まずグラフが連結のときを考える。全域木をとって根付き木として葉から決めていけば、根以外は希望の状態にできるし、全体でついてるのが偶数という条件を満たしているなら根も希望の状態になっているはず。実際にはKという個数だけが与えられていて自由度が高いのでけっこう混乱した。まあ個数が残っているかぎり葉からつけていけばいい（葉側でさぼるとあとから取り返せない）。実装は、DFS木を使う。子孫の探索が終わりKが残ってるのに自分がついてないなら親にそれを報告し操作してもらう（この実装がパッとは見えなくて、よくない）。連結成分毎に偶数の最大を取っていく感じ。辺を出力してサンプルとは異なる答えを軽く確認して提出、AC。