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が苦手なのか、別のものが苦手なのか。

ABC343

6完。結果だけ見れば普通だけど、内容が悪すぎる。競プロに飽きているからパフォーマンスが出ないという説はある。

A - Wrong Answer

言われたとおりに全探索。これ1分切れないのは仕方ない。!(a + b) は思いつきたいけどちょっと難しい。問題名見てなかったな。

B - Adjacency Matrix

素直に出力していくだけ。その場では行の終わりがわからないので、その行で初めての出力でないときはスペースを入れるという処理をする。出力すべき番号がない場合でも改行はする必要があることに注意する。

C - 343

立法数自体が少ないので全部確認すればよい。回文かの確認もto_stringしてreverseというので間に合う。

D - Diversity of Scores

mapで何が何個あるか持つやつ。そういやunorderdでもよかったのか。

E - 7x7x7

やばめの構築？いや、343^3で全探索できる？などという印象だった。まず2つの立方体の共通部分の体積の求め方を考える。次元を下げて考えると区間の共通部分で（最初2次元で考えていたが1次元でいいんだなあ）、これは区間の右端の最小値と左端の最大値の差でわかる（0以上）。たぶんこれを3方向についてやって積をとればいい。次に全探索の方法を考える。共通部分がちょっとだけあって3個つなげるとけっこう広い空間を使うため、定数倍の重い3乗は間に合わない。立方体1個を固定したら2乗でいけそうだ。一辺が21の立方体の中で全てが作れそうなのでそれを確認する。3個全部つながっているときは大丈夫。2個と1個に分かれるときは一辺が14の立方体と一辺が7の立方体に分ければいい。全部バラバラもOK。1個を固定するのは、真ん中に固定して、それではみ出すならずらせば一辺が21の立方体に入るからOK（これも連結成分の個数で場合分けして考える）。確認できたので、各立方体の隅の座標が0から14まで全探索。15通りの6乗が10^7程度なので間に合う。実装はきつい。迷うけど、6重ループにした。あと、3つの立方体の共通部分の体積も知る必要があった。これも同様のコードを書けばいいが、慎重に1文字も間違えないように書くのは大変。あとは包除みたいにして計算。3個重なっていたら体積を3倍カウントするみたいなイメージで(7^3)*3になるか検算。

F - Second Largest Query

区間だしさすがにセグ木しかないだろうと当たりを付ける。問題文はちゃんと読んでいたがいつの間にか脳内で意味が変わって、2番目に「多い」値になっていた。頻度をmapで持ってマージテクのようなことを考えて、実装もして、更新が無理だと気づく（実装するまで気づかないのが弱い）。しばらくして「2番目に大きい値ならセグ木でできるじゃん」と気づく。じゃあその値が指定された区間に何個あるかもわかるか？値毎に位置をmapを持ってと思ったが、個数はわからない（これに気づくのにも時間がかかっている）。で、2番目に大きい値がセグ木でわかるなら個数も普通にわかると気づく（ここでようやく「大きい」と「多い」の勘違いをしていたと明示的に気づく）。セグ木の実装がめちゃくちゃきつい。同じ値はまとめる必要があるのが大変すぎる。2つのノードの2つずつの値（4個）をsortしてuniqueして（もし2個に足りなければ0を入れて）これでOKと思ったら個数もまとめる必要がある。if文を8個並べて、同じ値だったら足すというのをやった。2番目が1番目になることはないので少し減らせるけどそういうことをする余裕はない。しかし書き上がってもサンプルが全然合わない。ソートでgreater<>()が必要だったけど、uniqueは一致するかしか見てないから必要ないんだよなとか言いながら一応greater<>()を入れてしまっていた。よく考えたら一致判定を不等号2回でやるわけがない。そこは一致するかどうかを判定する関数を指定する場所だった。

G - Compress Strings

atcoder::z_algorithmを使うことを考える。完全に含まれる場合は含まれる側を消してしまえばいい。2つの文字列を連結してz_algorithmを使えば、完全に含まれるかどうかも、完全に含まれる以外でどの位置で重ねることができるかもわかる（どっち側からつなげるかで2通りやる（2重forでやるだけ））。文字列の左端の位置が左のものから追加していくことにすれば、完全に含まれるケースがないとしていいことから、最後に何を追加したかが同じなら同じ状況になるのでDPできる。実装上は、完全に含まれるものを消さずに、貰うDPで（含まれるなら最後の文字列が変化しないので）貰う人を変化させる、配るDP風の実装になった（常にpopcountが小さいものから貰うので大丈夫（DAGになっている））。何度となく書いているdp[(1 << n) - 1]を誤ってdp[1 << n]と書いて気づかないなど、酷いミスが多い。z_algorithmを使う部分も難しく、コード量を増やして安定をとったつもりが間違っていた。

ABC342

6完。最後の10分で2問通してるのは、（レーティングの意味で）効率はいいけど、たまに失敗して破滅する。まあ、早解きできた人にはGを考える時間も与えられて羨ましいね。

A - Yay!

150点だけど簡単じゃんと思ったら、けっこう大変だった。文字数をカウントして1のものを探す（Sの長さは3以上なので一つしかない）。位置を知る必要があると気づき、同時に位置も（文字毎に）記録する（知りたいのは文字数が1のものなのでこれでOK）。なんか簡単な方法がありそうだけど、ないのか。

B - Which is ahead?

各人が前から何番目に並んでいるかを求めておく。

C - Many Replacement

各英小文字がどこへ移るかを求めればいい。

D - Square Pair

ソートしていい。0はどうにでもなる。合わせて平方数になるのがどういうときか考えたけど、平方数で割れるだけ割った残りが同じっていういつもの条件だ。素因数分解した状態で考えていたので、残った素因数のvectorをmapに突っ込むとか思ってしまったが、それらを掛けた数でいい（）。mapでカウントしたら、a[i]も書き換えてしまって、各a[i]について相手が何個あるかを足していく。0は別に数えておく。順序違いや自分自身とのペアはカウントしない設定だが、全部数えてNを引いて2で割ることにする。0は全員とペアになれる。そうでないとき、自分と同じのと0が相手になる。

順序違いや自分自身や0の扱いが難しくてサンプルがなかなか通らなかった。0は当然平方数と思っていたけど、「各素因数が偶数個入ってる」という特徴付けで平方数を捉えると、全部無限でほんとに平方数かってなるし、「何と掛けても平方数ってそんなことある？」ってなる。

ABC254が類題だった。当時はmapじゃなくてソートとランレングスで数えてた。同じ悩み方してて草。

（追記）解説にあったエラトステネスの篩みたいな方法でできた。「平方数で割れるだけ割った残り」になりえるものを見つけたら、それに2以上の平方数を掛けてできたものは平方数で割れるだけ割ったらそれになる。また、mapでカウントだけしておけば、入力を受け取りながら簡単に処理できた。

E - Last Train

最終時刻の意味がよくわからなかったけど、ちゃんと最も遅い出発時刻の意味だった。ダイクストラやるだけに見えるが、等差数列みたいだったり後ろからだったり、ひねりがたくさんあってきつそう。逆から見てスタート時刻は10^18+10^9で、2^60にそこそこ近いけど余裕を持って小さい。時刻2^60から始めて、大小逆のダイクストラみたいにやっていく。辺のコストが動的に（？）決まるやつ（遅く来たほうが得するみたいなのがなければOK？）。等差数列は怖いけど、落ち着いてやればそこまででもない。移動時間Cと基準時刻Lを引いて、これが0未満なら間に合わない。そうでないときDで割ってK-1とのminをとる。これで何番目の電車を使うかわかったので出発時刻もわかる。

なぜかサンプルが合わず、飛ばした。Fを通して戻ってきて、サンプル3で正解よりも良い（遅く出発して間に合う）回答になっている。ダイクストラということでなんか手癖が発動し無向辺になっていた（有向辺のダイクストラも普通にあるけど出題頻度が低いというそれだけの理由で）。慎重に、未来から過去への辺だけを残し、AC。

F - Black Jack

ディーラーのほうは戦略が固定なので求めてしまえる。yの各値について、通過する（そこで終わる場合も含む）確率を求める。幅Dの区間に足す必要があるが、いもす法みたいにしてできる。最終的な値の確率は、L以上の通過確率がそのまま使える。自分のほうは、各値で終わったときの勝率がわかればいいかと思ったが、実装しながら詰めていくと、その時点での勝率を後ろから求めていくことができて、x=0の時点の勝率（答え）もそのまま求まる。ディーラーの確率を累積和とって、xからNまでが負けだからその区間の和を求める。自分の勝率も累積和を作りながらやって、そこで操作をやめるかサイコロを振るか勝率が高いほうを選ぶ。

サンプルがなかなか合わなかった。いもす法が普通に間違っていた、ディーラーのL未満を0にするのを忘れた、区間和をDで割るのを忘れていた、区間加算するときもDで割ってなかった。

（追記）ディーラーのほう、配り終えたら自分を0にすれば、全体の確率の和が1のままできるしL未満は0になるじゃん。vectorも2本使ってたけど1本でできる。勝率は、区間和ではあるけどyがNより大きいところは使わないので、y=Nになる確率から順に足していくだけでいい。自分の勝率も累積和にして、最後だけ和をとらずに抜ければいい。

G - Retroactive Range Chmax

読んだだけ。

（追記）解説を読んで考えて書く。要素の追加と削除ができて最大値がわかるデータ構造が要る。とりあえずmultisetでやった。「区間更新クエリが可換」というのが重要なんだね。言われてみれば、セグ木の区間クエリで見る場所のmultisetに出し入れすればできそうだ。双対セグ木は未経験だったが、意外と実装は軽かった。提出して2045msでAC。次にmapでやってみたところ、1512msと速くなった。メモリ使用量はほぼ同じ。意外だった。で、以前実装した優先度を変更できるpriority_queueを試そうと思ったが、ちょっと用途が違う感じ。なので、解説にある「消せる priority_queue」を素直に実装した。310msとけっこう速くなる。今回は（multisetなどの）インスタンスの個数が多い（N*2程度）のでやや特殊なケースかもしれない。