ABC352

6完。今週は体調などの色々で競プロを全くやっていなかった。問題文が読めなかったのはそのせいか、あるいはBとかが難読だったからか、微妙なところ。

A - AtCoder Line

値が区間に含まれるかを簡単に書きたいよなー。まあ不等号2個で書けるのでそれを2個書こうと思ったんだけど、XYを必要ならswapして大小関係を揃えて1個で済ました。A問題にしては難しすぎる考察を入れたので、時間が（A問題にしては）かかってしまった（実装時間を10秒減らすために考察時間を30秒増やす行為）。まあ問題文がかなり複雑で、時間がかかること自体はしょうがない。

B - Typing

SがTの部分列になっているのだろうけど、答えは一意に定まるのか？と思ったけど、SとTを見れば高橋君の行動（バックスペースキーを押したかどうか）は決まるので大丈夫っぽい。結果的に、貪欲に部分列をとる実装に。SとTどっちでforを回すか迷ってTにして、答えのvectorにどちらのインデックスを入れるか間違えて、それを直すときインクリメントを付けたままにしてバグらせて、まあ酷かったけど問題が難しすぎるからしょうがない。

C - Standing On The Shoulders

頭の高さが巨人P_Nよりも高い巨人がいる可能性もあると気づいてえらい。まあそれは関係ない。肩の高さは順番によらず一定なので、肩と頭の差だけが重要になる。問題を見た第一印象の通りの簡単さで、本当に300点かと疑心暗鬼になってしまった。

D - Permutation Subsequence

いかつい問題文だが、連番ができるだけ狭い範囲にあるのを見つけるということで、しゃくとりみたいにできそうで、std::setを使えばできそうだ。本来なら最初のK個を入れてからN-K回ずらし、2個のfor文を書くところだが、区間の個数がN-KではなくN-K+1なのが気持ち悪くて1個のfor文にまとめてしまった（また時間がかかることをする）。jがK以上になったらj-Kを消して、jがK-1以上だったら最小値を更新する。末尾の要素は*st.rbegin()でわかる（今回は思い出して使えた）。

いやー、セグ木やSWAGで解けるの全く気づかなかった。

E - Clique Connect

最小全域木だけど、辺がめちゃくちゃ多かったりするからなんとかしてねという問題。普通にクラスカル法でできそうだ。intとvectorのpairを持ち重みのintでソートしておく（vectorのswapはO(1)だよね）。重みの小さい辺から追加していくが、K頂点にK*(K-1)/2辺を加えたとして順番にK-1本の辺でK頂点をつなげばその時点で連結になるのでそこだけやればよく（それ以外は愚直にクラスカル法やってもスキップされる）、これで計算量もOK。サンプル通らなかったけど、頂点1の連結成分のサイズがNでないなら-1を出力するんだ。

解説は間接ソートか。迷ったけどそっちのがよかったかな。

F - Estimate Order

ポテンシャル付きUnionFindでピースに分解できて、あとは各ピースについて置ける場所が一意かどうか（置けることは制約で保証されている）。そんなのできるのか？と思いつつとりあえず実装しようとしたら、Nの制約に気づく（2*10^5とかだと思ってた）。じゃあbitDPでできるんだろうなと思って考えるも、4^Nとかになってしまう。ピースが大きければピースの個数が少ないから間に合うし、ピースが小さければどこにでも入るから簡単そう、ということで、ピースを大きい順に並べてDFSしてみる。サイズが2以上のピースは高々8個、サイズが1のピースはどこにでも置けるから探索不要。8!はかなり小さいけど、サイズ2の初手は最大15通りあるし、でもまあ現実的には途中で置けなくなる配置が多いだろうから余裕で間に合うやつだよねと（終了後に計算したら大丈夫そうだった）。

最初は、初手を全探索して残りをDFSで可能か確認と思ってたけど、実装が面倒なので少し考えたら、単にDFSで全探索してそこに解が現れるか見ればいいということに。解の個数をカウントとか迷走していたが、ピース毎に可能な位置をビットで記録すればいい（今気づいたが、2箇所以上になったらループを抜けていて、これでは枝刈りした先のピースが探索されずまずいか？）。ピースのサイズが1になったら、そこから先も1なので、そこから先のピース全部、今置かれてない場所全部が可能。

実装はマジで重い。この実装を1時間できっちり終わらせてるの、5年前の自分よりはっきり強くなっていると感じる。苦手分野だし、あまり価値を感じないところでもあるけど。UnionFindして、leaderの列をサイズでソートして、leader毎にポテンシャルの最小値を求めてそれを0に補正してピースをビットで持ち、DFSが終わったら自分のleaderの番号を予め作っておいたテーブルで求めその可能な位置が1通りならその位置と補正したポテンシャルを足して答えとする。ソートと復元がマジでやばい。

G - Socks 3

めっちゃ簡単そうなのに難しいらしくて、嬉しくて笑っちゃった。なにもできずFに専念した。

（追記）言われてみれば典型だが、どれも全く思いつかない。解説の「タンスから靴下を i 枚取り出した段階でまだ同じ色の靴下の組が存在しない確率」を愚直に求めようとしてみるべきだったか（愚直にやったら計算量ハチャメチャに大きくなるんで考えもしなかった）。「タンスから靴下を取り出す回数が i 回以上である確率」を直接使えるのも、経験してるけど身についてない。一応差をとると「ちょうど i 回の確率」もわかるけど。分割統治はスタックでやった。

ABC351

6完。お腹の調子が悪かったけどコンテスト中は問題なかった。FGの崖で珍しく座ってるだけになった。

A - The bottom of the ninth

ちゃんと9回裏が存在する点数になっている。チーム高橋が何点上回っているかを求め、それに1を足したものが答え。

B - Spot the Difference

やるだけ。Bらしい、いい問題。

C - Merge the balls

i個目のボールにくっつけていく（相手がいなくなったらそのまま列の一番右に加える）イメージで実装。スタックを用意して、くっつけたら2倍になるので1を足す。1を足す操作は高々N回くらいなのでintで大丈夫（コンテスト中ははっきりわかってなかったが、1を足すたびに全体のボールの個数（最初はN）が1減るのでN-1回以下とわかる）。

D - Grid and Magnet

'#'の隣の'.'を'@'に書き換えておく。制約から答えは1以上なので'@'の自由度（常に1）は考えなくていい。UnionFindで'.'の連結成分を求め、その連結成分のサイズに周囲の'@'の個数を足せば連結成分内の'.'の自由度がわかる。'.'から見て同じ'@'を複数回数えてしまうことがありサンプル通らず。'@'から周囲の'.'（のleader）に配るようにすれば高々4個の要素の重複管理なのでできる（std::setを使っても十分高速）。難しかった。周囲4マスを見る処理を繰り返すが、そこはコピペなのでコーディング量は多くない。なぜ20分以上もかかっているのか自分でもわからない。まあ'@'に関する考察が難しかったからこんなもんかもな。

E - Jump Distance Sum

ウサギは斜めに動く。縦横に動くとして考えてみると、横だけ1次元なら解けるし、縦横独立に考えられる。位置の偶奇と縦横によって2*2通りのvectorを持ち、x,yの和が奇数ならxに1を足して偶数にし、和の1/2と差の1/2（どちらも整数）をvectorに突っ込んでいく。2*2のループを回し、ソートしてそこまでの和を持ちながらやればできることはすぐわかるが具体的にどうやるか考えて書く。符号付き64bitに収まることは確認してあったが、普通にintの乗算でオーバーフローしててWA。WAの原因にはすぐ気づいたけど、こんなWAを出すようじゃ常に64bitを使う戦い方をしない理由が出せなくなっちまう。

F - Double Sum

普通に考えていくと、自分より左で自分より小さいものの和と個数がわかればいい。E問題と似すぎていると思った。座圧してセグ木でできそう。答えが符号付き64bitに収まることも書いてあるので特に考えず書く。BITでできそうとも思ったが時間がかからないほうを選んだ。

（追記）evimaさんの別解の、小さい順に配置していくのはなるほど。座標圧縮要らないのいいねえ。BITを抽象化して使ってみた。

ARC176

Bのみ1完。

A - 01 Matrix Again

例えば (i + j) % N < M を満たすマス(i, j)を1にすればどの行も列も和はMになる。あとはここから行や列を入れ替えて与えられたM個のマスをカバーすればいい。ここでは逆に与えられたマスたちを、M*Mのマスを斜めに半分に切って対角線上は加えた三角形に乗せることを考える。おそらくこれは達成できると思い、各行各列を与えられたマスの個数で降順ソートし左上に集める。それができたら集めたものを戻す変換で最初に作った例を出力する。最初、与えられたマスは出力しないと勘違いしていた。念のためにちゃんと与えられたマスを使っているか確認するコードを書いたところ、奏功してしまった。ソートだけでは達成できない。端から詰めていく。サンプルはよさそうだけどWA。証明してないのでしゃあない。

（追記）けっこう考えたけど他のアイデアを全く思いつかない。解説を見たら、あーもうやってられん。M*Mで考えてしまっていたんだなあ。そっち方向にバラバラにできるのか。ちょっと頭が悪すぎて考えようがなかった。最近、自分の実装力を信じずにARCを信じたほうがいい気はしているが、信じたところで思いつかないのでは意味がない。

B - Simple Math 4

何の性質の良さを使うのか迷う。2冪か、10や5で割ったあまりか、2^M-2^Kか。そういえばローリングハッシュで2^61-1で割ったあまりを求める方法をちゃんと追ってなかったなと。（NがM以上のとき）普通に2^Nから2^M-2^Kの倍数を引けるだけ引くことを考えると、2^N ≡ 2^(N-(M-K)) mod 2^M-2^K がわかる。M-KはMより小さいので、Nからそれを引けるだけ引いてM未満にするまでやって大丈夫。これは割り算でできる。これで、NがM未満の問題に帰着できたので、あとはatcoder::modintでmod 10で2冪を計算するだけ。WAで、言われてみれば2^N=2^M-2^Kとなるケースがあって（例えば2^8=2^9-2^8）、そのときは0を返すようにしてAC。これ気づくのは難しい。時間制限がある状況では仕方ないところ。

C - Max Permutation

グラフで考える。ある頂点から出ている辺のCたちを考える。同じ数が複数あるとき、その数はその頂点になければならない。その数はCたちの中で最小である必要がある。もう寝るので続きは明日書く。

（追記）日曜夜、気温のわりに寒く感じる気はしていたが、起きたら体が熱く微熱があって今日はずっとアニメを見るなどしていた（競プロみたいなことは頭が働かずできない）。夜になってようやくある程度の思考ができるようになってきたが、元の頭が悪いのでやはり大変だ。

コンテスト終了後、答えが0だとわかったときに0を出力して終了する関数を書き、順列の確定した値をセットする（違う値がセット済みだったら0通りを出力する）関数を書く。こういうの早めに整備するの大事。

各位置について確定した値を入れるvectorと何未満であることがわかっているというvector（最初は全部（0-indexedで）N）を持っておく。各頂点について、出てる辺のCの多重集合（2,2,2,3,4,6とか）が、最小のもの以外は全部1個ずつである必要がある。最小のもの以外は、相手がその値で確定。最小のものが複数あったら自分がその値で確定、1つだったら辺で結ばれた2頂点のどちらかがその値になるということで記録しておく。こいつらは、別の頂点を調べることで確定してしまうかもしれないのでそういう処理をする。するとおそらくこいつら（辺の集まり）は頂点を共有しない。つまり独立に考えられるので、どちらがそのCになるか勝手に決めてしまって答えを2倍すればいい。すると、確定した値と何未満であるという必要条件が残っておそらく十分条件にもなっている。ということで小さいほうから決めていけば通り数が求まる（典型だが、確定したものもあるのでやや難しい）。よくわからんので矛盾が生じたら（そういうことが起こりうるか自分にはわからないけど）すぐ0通りを返すようにどんどん処理を入れる。

なかなかサンプルが合わなかった。Cを0-indexedに直すの忘れていた。0未満からN未満まで表現するのでvectorの長さはN+1必要だった。確定した値がセット済みでも同じ数ならOKなのをうっかりした。辺の片側が決まってたときの処理でその値がCと等しいかで場合分けが必要だった。一応ACしたが、未証明とかいうレベルじゃない。通しただけ。解説見たらやはりもっとシンプルなんだな。

体調悪いのでAとCの実装はまたこんど。

ABC350

6完。マスターズの表彰式が終わった18:49頃に離脱。19:00の電車に乗り（会場が地下鉄と直結している）、無事ABCに間に合った。

レーティングは下がったものの、FGに1時間を残し、Fも迷走した中で時間をかけてしとめる立ち回り。ゲームメイクがよかった。

A - Past ABCs

ABCの略称が辞書順に並んでいることを利用する。辞書順で"ABC350"より小さければおおむねYes。ABC316が例外。まさかA問題でそんなことしないだろうと思っていたけど、問題文を読み直したらABC000も例外だった。やばすぎる。

B - Dentist Aoki

治療するたび1をxorする。最後に全部の穴を数える。こういう（青コーダーにとって）軽いBは久しぶりだ。

C - Sort

b[a[i]] = i; のようにして、各数がどこにあるかを持っておく。左から順にswapしていけばよさそう。自分よりも右の要素としか交換しない（既に左には、ここにあるべき要素より小さいものしかない）ので、大小関係は大丈夫。更に、bを更新しなくてもサンプルは通る。これが本当かどうかを考えるが、4 2 3 5 1という例で撃墜できた。ということでbの更新を書く。どっちを先に更新すると壊れるとか面倒なので、交換するインデックスを変数に保存しておいて、aをswapし、bをaを使ってswapした（aはswap済みだが別に入れ替わっていても同じこと）。けっこうきつい実装だった。

D - New Friends

考えていくと、UnionFindだろってなる。友達関係を無向辺として連結成分内は全員友達同士になれる（と思う）。

解説の証明見て、パスをとるのなるほど～ってなった。

E - Toward 0

こういうの（ループがある期待値）相対的に得意だと思ってたけど違ったかも。メモ化再帰。割る数が2,3,5の組み合わせしかなくて割れる回数が高々60回だからその3乗としても間に合う。証明できるわけではないが、さすがにこういうのは何回も出題されて慣れている。あとは再帰を使って計算するだけだが、Y円払う操作で1が出たときY円だけ払って状況が変わらないのが難しい。感覚ではわからんので数式で求める。最初サンプル合わなかったのは、Yを2箇所で足してたからだった。

解説の計算量の説明、切り捨て除算2回をまとめられるの確かにそうなんだろうけど（明らかに証明できそうだし実際証明できたけど）、感覚としてわかってないな。

（追記）Y円払う操作をしたときの期待値を求めるとき、X円払う操作は考えなくていいというのが感覚的にわからなかった。それまでに払った金額がゲーム内容に影響しないので、サイコロで1が出たら最善手も変わらない。ここからが難しいのだが、だから同じ状況で違う操作をしないとしてよい。そういう制約を加えた問題を解けばいいので、X円払う操作は考えなくていい。

F - Transpose

まず愚直（stackで対応する括弧の位置はわかるようにしておく）を書いてサンプルが通ることを確認。きれいではないが、平方分割でできそうだと思う。小さい区間は愚直にやり、大きい区間は名前を付けて1文字に置き換える。反転したかの情報を持っておく。そのためにcharではなくintで処理する。復元は順番に再帰的に。大きい区間をちゃんと縮めるために別の列へコピーしながら。この辺りでさすがにおかしいと思い、正面からの解法を探した。まず、大文字小文字の反転は括弧の深さの偶奇で決まるので簡単に前処理できる。あとはreverse処理だけだが、これは再帰でできそうだ。括弧の相手を前計算しておき、向きを反転させながら順に文字を答えのstringへ追加していく。再帰する部分以外は1文字ずつ処理して大丈夫、再帰するところは対応する括弧へジャンプしてO(1)で済ますようにする。これで計算量は大丈夫。答えが合ってる確信はなかったけどサンプル通ったしさすがにという感じでAC。

G - Mediator

メモリの制約がきついんだね。Nがわりと小さいね。隣の頂点のリストを持って共通部分、bitsetでできそうだね。ビット位置を求める機能なさそうだから自作しよう。提出してMLE。記憶力～。