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。

ARC173

3完。ありがとう。

A - Neq Number

Neqの意味がわからなかったけど、not equalか。Bも読んで難しそうなのでやっぱりAをやって、わからないので愚直に桁DP（N以下のNeq Numberの個数がわかれば二分探索できる）。N=1234のとき12を0012と解釈して0が連続してるからとはじいてしまうのを避けたい。1桁の個数と2桁の個数と3桁の個数と4桁でN以下の個数を足すことにする。下から1桁目は前の桁の影響を受けないので場合分けして処理。この辺り色々試して添え字ガチャみたいになってた。最上位桁の1から9を足して0は答えに足さないというのがポイントだった。46分でAC。ARCをまともに戦えるギリギリの時間という感じ。

（追記）N桁のNeq Numberは9^N個（最上位から1桁ずつ決めていくと毎回9通り）。よって、9の冪を引いていくことで桁数がわかり、その桁数内で何番目を求めればいいかがわかる。そしたら上の桁から9通りの何番目かで決めていく。9進法と対応付けるのはここ。0以上9^N未満の整数を9進法で表したものが、N桁のNeq Numberと対応している。0から9の中で前の桁（最上位桁の前の桁は0とする）と異なるものから選ぶ。

B - Make Many Triangles

3点が一直線上にあるかは、点のどれかを基準に2つのベクトルを作って外積が0かで判定できる。全探索もできる制約。NGの組み合わせが与えられるので3人組をいくつ作れるかという問題と思ったが、これは全然わからない。もっと問題固有の性質を使う。直線にたくさん乗ってるとき、直線上の2点と他の1点で三角形が作れる。1個余ったときが不安だが、さすがになんとかなりそう。最大で一直線上に何個あるかが重要そうなのでそれを調べるコードを書きたい。よく考えたら3重ループで愚直にできた（なんか工夫なしでは3乗超えそうなイメージ持ってたけど違った）。書いていくとめっちゃ単純な答えになったが、提出してAC。提出後C問題に行ってから少し考えて、一直線上にある最大個数が全体の2/3以下を保ったまま取り除いていけそうだなとか思ってた。解説見ると証明は思ったより大変そう。

山登りが正当性あるのなるほどなあ。最初、山登り落とすケース作ってなかったのかなとか思ってたけど、落とせないんだ。

C - Not Median

中央値ではないとか、解けるわけがない見た目。ちゃんと考える。自分より大きいのと小さいのの個数が同じだとダメ。同じになるのはどういうときか考えると、自分をO、大きいのをH、小さいのをLとして、HLHLOHLHLのようになっているとどうやっても同じになる。このパターンが崩れるところを探せば条件を満たす区間が作れる。左右の長さが違うときを考えると、一番端以外はまあ普通にできて、端のときはOLHHLでも同じになってしまう。さて、さっきのパターンを見ると、LOHのところは単調増加になっている、つまり隣のやつ視点だとLH交互にはならない、答えが小さくなる。これは愚直にやって間に合うやつではと思い（全然証明とかわからないけどそれに賭けるしかないような状況なので）、両端だけ場合分けして愚直を書く。左右でLH逆になるの書き忘れてサンプル合わなかったりしてたけど、サンプルが通ったら提出してAC（WAは出ない予定で、TLEが心配だった）。通って、「ありがとう」と言っていた。何も証明してないのに結果だけをもたらしてくれてありがとう。ペナが多いのは順位表で知っていたし、ただ運が良かった。

D - Bracket Walk

全くわからなかったが、解説放送聞いてなるほどなあすげえなあとなった。Eもなんとなく聞いてたけど、ARCの高難度はしっかり難しいんだよな。

（追記）'('を1、')'を-1とする。ウォークの各位置での累積和が常に0以上で始点（は当然0だが）と終点が0であればよい。始点と終点が同じなので、全体の和が0でありさえすれば、和が最小のところを始点とすれば括弧列になる。言われてみればそう。じゃあ和が0の条件を満たすウォークがあるか。負閉路と正閉路（って言うのか？）が両方ある場合、括弧列以外の条件を満たす適当なウォークをとって和が負だったら正閉路を何回かくっつけて和を正にして、次に負閉路をとって互いの和の絶対値のぶんだけ周れば0になる、つまりYes。どちらもない場合、括弧列以外の条件を満たす適当なウォークをとれば0になってるからYes。片方だけある場合、対称性から負閉路だけある場合だけ考える。負閉路をとって、括弧列以外の条件を満たす適当なウォークからその負閉路で使った辺を取り除く（全ての辺を使ったウォークだからできる）。取り除く前も後も、全ての頂点について入次数と出次数は等しい。よって、取り除いた後のグラフについて、次数が正である頂点があるかぎりそこから出発して（行き止まりになることはないので）初めて同じ頂点を訪れたところで（その頂点を初めて訪れるまでの経路も）切って閉路を得ることができ、結局最初のウォークはいくつかの閉路に分解できる。これらの中に正閉路は存在せず、負閉路は存在しているので、ウォークの和は負であるとわかる。どんなとり方をしてもそうなので、No。いやー解説の行間を埋めるのにめちゃくちゃ時間かかった。全ての辺を使うという条件を使い切るのが難しかった。

ABC344

5完水パフォ。ゴミ。

A - Spoiler

'|'が来るたびに状態をflipして、答えのstringに入れるかどうか決める。'|'を入れないようにするのどう実装するか悩んだが、'|'かどうかで場合分けすればよかった。

B - Delimiter

入力がそこで終わってるかどうかはA_iが0かどうかで判定できる。問題文に書いてあるけど、そこに気づくのが一番難しい。

C - A+B+C

屈辱のunordered_set。bitsetでやれば速いとわかっているが、早くACを得るためにunordered_setを使う。終了後に試したら、メモリ使用量すらbitsetのがよかった。このくらいならコンテスト中でもやったほうがいい
か（気分は大切）。unordered_setを使ったコードの実行時間が思ったより長かったが、出力が多いのを忘れてIO高速化してなかったからだった。

D - String Bags

全然見えないけどさすがにDPだろうと思ってやっていくと実際にDPできる。計算量も余裕がある。「何もしない」があるのを、知ってはいるんだけどなんか忘れてサンプルが合わなかった。DPの更新が大量に入るので、同じ袋の文字列を2回使ったりする遷移が本当にないか自信が持てなかった。提出したらACだったけど。

E - Insert or Erase

双方向リストでできる。std::listは、使った経験がほとんどないし、64bitのイテレータを扱うよりは自前の32bitインデックスでいいだろみたいな感じで自前実装。値と前後のインデックスを持つ。リストの構造体のvectorを最初にN個作って、新たな要素の追加でそこへpush_backしていく。何がどのインデックスにあるかはunordered_mapで持つ。これは、消すときは放置。リストのほうは、消したら-2で埋める。前のインデックスを-1にすることで唯一の先頭の印とするため。あとは普通にリストの処理を書く。サンプルがなかなか合わなかったが、なんと出力で間違えていた。リストを辿ってインデックスを更新したあとでアクセスしてて普通にバグ。直したらACできてよかった。

こういうの飛ばすかどうか難しい。

解説を見て、番兵使うのは思いつかなかったなあ。

F - Earn to Advance

Eに時間がかかったとはいえ、40分以上残っている。だが、一つの方針の検討に20分かかっていては2つ検討してコンテストが終わる（2つ目が当たりだったとして実装時間がない）。最初に最小費用流を考えてしまったが、それで解けるか以前によく考えたら（実行時間が）間に合うわけがない。次に正面から考えて、経路を固定すると最もPが大きいマスを更新していきそこで稼いだことにすればいいとわかる。後ろから見たらどうか、前から見たらどうか、色々景色が違って難しい。最大マスも持って4乗DPとしても、半端のお金の扱いが不可能。

（追記）あとから稼いだことにするんだから、あまったお金はそこまでの最大マスのPより少ない。言われてみればそうだが、ちゃんと理解できてる気がしないなあ。自分の理解が間違っていれば、間違いを見つけることで理解が進むが、これは正しいのだからどうしようもない。貰うDPで書き始めるが、どこに貰うかは最大値が更新されるかで変わるので結局は配る感じにもなる。メモリ制限ギリギリの巨大DPテーブルなのであまりしたくはなかったが最初から全部初期化した（ローカルでは200ms以上かかる）。移動するとき、あまってるお金で足りなくなったらその分を最大マスで稼ぐ（ここで割り算が必要）。その後、最大値が更新されるかで遷移先を決めて更新。いやあ難しい。書いてしまえば見通しも立つが、最初は全然見えなかった。これはDPが苦手なのか、別のものが苦手なのか。