ABC390

6完。全てが上手く行ってギリ黄パフォ。環境が厳しい。

A - 12435

swapしてis_sortedで確認してswapで戻す、というのを4回やる。スムーズに解けたと思ったのに2分以上かかってる。

B - Geometric Sequence

27 18 12 8 みたいのもあり、かなり怖い。サンプルを見て「長さ2以下なら等比数列なのか」「公比が整数でないこともあるのか」などと気づいていて、あまりにも危なっかしい。比を隣同士比べる。整数演算でできる。比べる回数がN-2なの「知らなかった」のでやはり怖い。

C - Paint to make a rectangle

パッと見では全然わからず難しい。気づけばまあ簡単。黒マスのBounding Boxがわかればいい。その中に白マスがあるならできないし、そうでないなら内側を黒に塗って外側を白に塗ればできる。制約を見落としていて、黒マスがないときは塗られていないマスがあるかどうかで決めた。

D - Stone XOR

Nが小さいけど簡単な列挙方法を思いつかない。そもそも1回操作しないとスワップができないとか考えてたけど順番は関係ないのを忘れていた（グループ分けを考えるだけでいい）。DFSで無理やりやる。残っている中で最も左のものを使うとして、そいつと同じ袋になるものをビット全探索する。これで重複なくグループ分けを列挙できるはず（この問題の場合、別に重複してもいいけど）。N=12で実行してDFSの葉が400万個程度であることを確認。unordered_setで数えて実行時間も短い。であれば問題ないので提出、ジャッジに時間かかると思ったら1835msでACしてびっくり。

終了後にsetで提出し直したらなんとTLEした。要素数が400万になるとunordered_setやsetが思ったより遅かった。そもそもの話として、葉が400万しかないなら全部vectorに突っ込んでsortしてuniqueすれば明らかに間に合う。いつものABCだと思って手癖でunordered_setを選んでしまったのがよくない。

E - Vitamin Balance

最小値をとるビタミンを3通り試せばいけるとなぜか思ってしまったができないので考え直す。データをビタミンの種類で分けてしまっていいのはそうなので、別々にDPすることを考える。DP自体は簡単。合計カロリーがこれのときのビタミンの最大摂取量が得られる。これを使って問題が解けるか考えると、二分探索で楽に解けそうだ。しゃくとりで行けそうなのとカロリーがちょうどjではなくj以下のときの最大に変換して安全に処理できるかすぐにわからなかったりして手間取った。結局は変換したし二分探索にした。

Fを読んで順位表を見たら、Eはめっちゃ解かれていて、やっぱ競プロerはDPキチガイだと思った。

F - Double Sum 3

問題文の言ってることはわかるが、それをそんな大量に足すとかできるわけがない。少し考えて、各要素の寄与を足すやつじゃないかと気づいた。例えば9があったら、8と同じ区間になれば操作回数が減る、10も同様。定量的なことが全然わからないけど、とりあえず実装してみる。左右それぞれについて最も近い指定した数の位置を得たい。親切にもA_iが小さいので各値についてインデックスのvectorを持つ。番兵として-1とNを入れてソート。1より1小さい数とかNより1大きい数とかを場合分けするのも面倒なので、0からN+1までのN+2個の値があるとした。1小さいのと1大きいのそれぞれについて、その相手と一緒にならない区間がいくつあるか数える（小さいのと大きいの独立にできそうなの最初は見えてなかった）。とりあえずサンプルをやってみて、2倍ちょっと違う。改めて考え、自分と同じ数と同じ区間になったときも操作回数を削れると気づいた。また、黒板に書かれた連続した数の塊について、両端の要素が1/2ずつのコストを負うことにすると、自分の実装は（Aの要素が相異なるなら）答えの2倍を求めるものになっていそうだ。そこで、区間内の同じ数は最も右のものにコストを負わせることとし、右側で1小さい（大きい）数よりも近くに同じ数があるなら、コストが減らない区間右端の領域はそこまでとした。なんか違う気がしていたけど、感覚に反してサンプルが通ったので提出してAC。

わからないままACしちゃった。考え直すと正しい気もしたけど、そのときの気分ももう忘れてしまった。

ABC389

5完2ペナ。こんなもんだけど。

A - 9x9

'0'を引いて掛ける。汎整数拡張みたいなことを考えた。81はcharに収まるけど、A問題を解く一瞬ではそういうことも判断できない。

B - tcaF

存在すると書いてあるので信じてXに一致するまで掛けていく。Nが20以下と書いてあったらだいぶ簡単になるよね。いいひねり方。

C - Snake Queue

いかにも簡単に解けそうな見た目だが、その簡単な解法を見抜くのが難しい。結局整理しきれなかった。現在いるヘビの長さの和とこれまでに削除された長さの和を持つ。その2つの和をdequeに入れて、出力するときはdequeのK番目から現在の削除された長さの和を引くと合う（削除するために各ヘビの長さもdequeに入れる）。そいつが追加された当時からどれだけの長さが削除されたかを知りたいのでこうした。ヘビの数も管理する必要があると最初思ったが、それはdequeがやってくれた。

（追記）解説を見て累積和でやった。自分で考えてこれに到達することができなかった。dequeでもできた。ここまでシンプルな問題だったのかあ。

D - Squares in Circle

二分探索。座標を2倍して整数で比較。第一象限だけやって、軸のところ以外は2倍にする。やるだけと言えばそうだが、相当神経使うよね。

E - Square Price

いつ誤読したのかあいまいだ。誤読とはそういうものかもしれない。安い順に貪欲でいいので簡単そうに見える。最大で10^9個くらい買えるから厳しそう。T円以下のものを全部買ったらいくらになるか計算して二分探索。2乗の和は3乗になるからO(N^(1/3))個しか買えないのではと思い優先度付きキューで書き始める。誤読に気づき二分探索に戻ってくる。T円以下のものを全て買うとM円を超えてT-1円以下だと超えないというTを見つけ、T-1円までは全部買って、残りはT円のものを買えるだけ買うので単に割り算（切り捨て）でいい。コードを見てオーバーフローをケアし提出してWA。1種類の商品では大丈夫でもそういうのを足していくとオーバーフローする可能性があった。ついでに、最大で10^9個くらいしか買えないことをしっかり考えて、二分探索の上限も10^9強に下げた。WAが増えて一旦Fへ。すぐ戻ってきて、二分探索は個数じゃなく金額だった。二分探索の上限をMに戻してAC。違う問題を考えていた時間が長かったし、誤読に気づいてからもその混乱から抜け出せず精度が酷かった。K個目の値段がK^2になると誤読して、2乗の和は式も複雑になるしオーバーフローのケアも大変そうで全然見通しが立たなかった。

F - Rated Range

終了後も考え続けたが、こんなに解かれているのに全く糸口もつかめない。結局40分遅れでAC。わかってしまえば遅延セグ木二分探索やるだけ（遅延セグ木じゃなくてもできそう）。実装もシンプル。

（追記）セグ木二分探索で書き直し、次にBITでもやった。境界がわからなくなり、かなり時間がかかった（できたコードはめっちゃシンプル）。

ARC190

1完。まあこんなもんか。ARCだった。

A - Inside or Outside

操作2がない場合は最短経路問題になるよね。そっちを考えてしまったが、さすがに無理そう。反転させることができるので、意外と小さいコストでできそう。2手でできるパターンがけっこうある。2個の区間があって片方がもう片方に含まれるなら2手でできる。そして、そういうケースを除くと、LでソートしたときRもソートされている（！）。端から出てる区間が特別なので考えると、端から出てるものが2個あるだけで2手でできそう。また、端とは関係なく、共通部分を持たない2個の区間があったときも2手でできる。気づいてなかったけど1手で全部覆えることもあった（簡単なので場合分けする）。含まれるのと共通部分ないのを検出すれば、端から出てるやつで考慮すべきなのは2区間が両端から伸びて操作1だけで全体を覆えるのだけ（こいつだけ浮いてて捉え方がよくわからなかった）。共通部分持たないのを見つける方法がすぐにわからなかったが、単にLでソートして最初と最後で試すだけだった（今回の場合はRが最小の区間とLが最大の区間をそれで選べるので）。あとは2手でできないときだが、Mが2以下なら不可能。そうでないとき、ソートされた連続する3個の区間を見ると、2番目の区間で操作2をしてその穴を1番目と3番目の操作1で埋めることができる。なぜなら、1番目と3番目は共通部分を持っているので（そうでないなら2手でできるのでここへは来ない）。時間はかかったが一発AC。安堵。ここでペナが出ると精神的にきついよなあ。

解説を見て。自分は頑張って区間の位置関係を列挙して全部のパターンを調べただろうということで未証明実装したけど、解説にあるように（2手でやるとき）どの操作を使うかで場合分けすればいいんだなあ。

B - L Partition

大きい順に配置していくと、置き方は4通りしかない。ちょっとずれて一回り小さい問題になる感じ。大きい順に置いていって、レベルkを置く段階でターゲットとなる(a, b)が左上隅になるようなものが何通りか考える。L字ではあるが、長さkの横棒を上下どちらかに置き、次に長さkの縦棒を左右どちらかに置く（横棒と重なるけど重なっていい）としても同じことだ。縦横独立に考えられる。ただ、正方形が（左上隅だけでなく他の隅や辺にあってもいいので）四角く動くのが厄介だし、はみ出る処理までできる気がしない。ここで、2乗をまず書いてその高速化というステップを踏むことにする。はみ出るのを気にせず書く（どうせ0になるので）。隅にあるときは当たり判定が大きくなって3通り、そうでないときは2通り。また、レベルkを置けてからもより小さいL字を置くときに4通りずつあるので考慮する。いくつかミスはあったけどサンプルが通り、残り5分。

終了後、Twitterを見ながら考える。最初に考えていた方針で行けそうだが、ちゃんと考えるのがきつい。パスカルの三角形で考えて、C(N-k, a)から上へ広がっていく感じで横方向の和を知りたい。両端を求めて足して2で割ればいい。丁寧に考える。はみ出るけど、0だからうまくいくっぽい。これで解けているはず。10^7なので、除算やpowは丁寧に取り除く（乗算にする）。これでAC。コンテスト中に通すには3倍以上のスピードが必要だったと思う（要するに力不足）。

解説を見る。嘘だろおい。レベルkじゃなくてレベルk以下を求めて差をとればいいじゃん。実装めっちゃ軽い！こんな基本的なことに気づかないとは。

ABともに、そこまで難しいわけではないが、タイムでちゃんと実力差が出ている。身につけておくべき典型に解きながら気づくみたいな感じだったしな。

ABC388

6完2ペナ。まだ干支ネタ使うのかと思ったけど、鏡餅は確かに今日食べた（追記：あと成人の日もあったね忘れてた）。KUPCは好き（ABCでKUPC？みたいな違和感も含めて）。

A - ?UPC

実装は軽いが、必要ない情報（大文字小文字、Sの2文字目以降）が多いので慎重に考える。使わない情報がある問題自体は好き。

B - Heavy Snake

愚直。

C - Various Kagamimochi

しゃくとり。最近は、こういう問題で二分探索を使う意味がないくらい、すらすらしゃくとりを書けるようになっている。

D - Coming of Age Celebration

問題文の内容がかなり難しい。同時に成人したら石の受け渡しはどうなるんだとか思ってた。ちゃんと読めれば状況はわりとシンプルで、左から順に自分より左の人から（その人が石を持っていれば）石を1個ずつもらうという操作。渡すのはもらったあとなので、左から順番に求めていける。石を何個もらうかわかれば、石を渡す対象の区間がわかり、最終的な石の個数もわかる。あとは区間加算ができればよくて、BITを（いもす的に）使う。

落ち着いて考えるとBIT要らんねー。この処理自体がいもす法の過程みたいな感じなので。

E - Simultaneous Kagamimochi

下になる餅を黒、上になる餅を白に塗ったとき、白と黒の並びには単調性があると予想する。単調でないとするとそういう2ペアを取り出して入れ替えることができるので、予想は正しい。つまり、どこかで区切って、白はそこより左のみ、黒はそこより右のみという位置が存在する。直感的には、ちょうど真ん中で区切ってよさそうだが、証明ができない（解説見たらわりと自明だった）。そこで、二分探索ができないか考える。さっきのをもう少し考えて、ある区切り位置があってK個のペアができたときそこに使った白のK個は左から見て最初のK個にしてしまっていい。区切り位置はKでいいことになる。C問題と同じしゃくとりを回せば、Kペア作れるときは作れるし、作れないときは作れない。これで解けた。

解説を見ると、ペア数の自明な上限のN/2（切り捨て）を区切り位置としてよい。当たり前すぎてなんでわからなかったのか。区切り位置をもっと左にしなくてよかったのかという懸念は、黒も右に寄せて損しないので半分残っていればいい。Nが奇数で真ん中の要素を使うケースもあるのではないかという疑問は、真ん中の要素は使わなくても損しないというのが答え（自分の感覚が間違っていたね）。

F - Dangerous Sugoroku

Fを読んで順位表を見てGを読んで両方考えて、Fをやった。

解けそうに見える。難しいのはNが大きいことくらいで、通れるマスがめちゃくちゃ長く続いていたらそれは位置を好きに合わせることができるので。おそらくB^2程度続いていたらそうなるので、そこまで縮める。M*B^2は10^7くらいなので間に合う（思ったより遅いと思ったらDPでここにBが掛かるのを忘れていた）。通れない区間が長いとDPが間に合わないが、そういうケースはそもそもNoなので場合分けすればいい。しかし、実装していくうち、数々の罠の存在に気づく。最後の通れない区間からNまでも縮めないといけない。A=Bのときは位置調整できない（縮める量を（面倒なのでA!=Bのときも）Bの倍数にするようにして対応）。M=0のときは最後の区間が存在しないのでNまでを縮める対応が別に必要（この認識は誤りで常に必要だった（たまたまL_1が大きいテストケースがなくて通ったのだろう（そこそこ大きいケースはあって遅いのはこのせいだった）））。縮める処理は、ずらし量を加算していく感じで実装。あとは、高々10^7くらいのDPテーブルに通れない場所をプロットして普通にDP。さすがにこのDPは簡単。左から見て到達できるマスから配る。

提出して、RE。配るときにはみ出していたのでDPテーブルのサイズを+100。またRE。最後の区間からNまでを縮める処理を準備したのに使ってなかった。これでAC。ACしたコードにもミスがあったし、まあこういう負荷が高い問題だとミスがめちゃくちゃ増えるよね。

G - Simultaneous Kagamimochi 2

これが解ければE問題も解けるという問題。白の区間と黒の区間を決めたとして、それが全部ペアになるかの判定が、区間の端はできても内部は高速にできないように思うので、解ける気がしない。

（追記）これも解説見たら当たり前に見えてしまう。確かにインデックス引くのは頭をよぎった。ただ、考えが整理されていない状態ではその一瞬で解けそうな感触を得ることはできなかった。解説を見ると、各要素についてどこから相手として選べるか前計算している。ある区間[L, R)でKペア作れるか判定したいとき、[L, L+K)と[R-K, R)を順にペアにできるか確認すればよく、前計算したものを使ってLの相手がA以上だったとしてAがR-K以下の必要がある。この条件が1ずつずれていくのでインデックスを引いて最大値セグ木に乗せればいい。区間の右端の要素のインデックスも必要だったので仕方なくそれも乗せた。自分はインデックスの最大値をセグ木に乗せたけど、解説のコード見たら各要素に1を入れて和で区間の長さを得ているすごい。「当たり前に見えてしまう」と言ったけど、解けるのが当たり前に見えるというだけで、具体的な実装を自分がするのにはかなりの時間をかけた。