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。記憶力～。

ABC349

5完。今日は、先週のABCの復習にようやく着手できた（は？）。

A - Zero Sum Game

Aとは思えない考察難度。持ち点の総和が0のまま変化しないことに注目する。

B - Commencement

まあ文字をカウントして、その（正の）個数をカウントして、2以外があるか調べる。コード自体はこんな感じで楽に書けるんだろうなと最初からわかってはいる。しかし問題文が何を言っているのかイメージが全くできない。大体の予想はできても、実装に入れるほどのくっきりしたイメージはできない。なんかコンテスト開始前に気づいたら2分前でおしっこに行きそびれたんだけど、ここで行った。そのくらい難しい。戻ってきてじっくり読み直して実装。

C - Airport Code

かなり怖い見た目だが、よく読むと素直な書き方。どちらかの条件を満たすかという問題なので一つずつ判定していけばいい。部分列になってるかの関数を書いておく（この貪欲はDPとかでおなじみ）。TがSの部分列ならYesで、そうでないときTの最初の2文字を取り出した文字列がSの部分列でかつTの末尾が'X'ならYes、そうでないときNo。

サンプル通らず。for (auto &c : t) と書いてTを小文字に変換したつもりがcではなくtに操作していた（コンパイル通るのが怖いところ）。また、Tを小文字に変換したのを忘れて大文字の'X'で判定していた。

D - Divide Interval

セグ木じゃんと思い、自分のセグ木からコードを持ってくる。そのままでACできるわけではないので、正面から考えるか、このコードをいじってなんとかするかで迷う。できそうなので後者を選択。セグ木のノードを観察すると、1段毎にオフセットと倍率が2倍ずつ変化していく。サイズ2^60のセグ木として、普通に処理していく。

E - Weighted Tic-Tac-Toe

9!なら間に合う。普通にネガマックス法で書いていく。手番と得点差と残り手数を持って再帰。得点差は高橋君目線なので、手番が違えば符号反転させて使う。手番から見たスコアを返すことに注意。スコアの最大値求めるのに初期値が0でやばかった（-INFにする）。まあいつものやつ。最初、9手打ってから判定してて危なかった。コード量の半分は三目並べの判定。計算量は問題ないが、一応探索ノード数を出力させて変なことになってないか確認してから提出。

F - Subsequence LCM

アルゴ式の高度合成数を見ると、10^16以下の制約だと4万個以上の約数がありえて間に合わなそう。とりあえず素朴なDPを書く。よくわからないので提出してみたら、TLEじゃなくてWAでびっくりした。Aをintで受け取ってる。書き直したときにintになってしまったのだ。嘘っぽいものを投げ続けていたが、安定のTLE。

10^16で素因数分解させてくるというのは発想になかった。まあ間に合うのはわかるので、あまりよくない思い込みだけど。

（追記）各素因数がMと同じ個数あるかだけが重要で、だからビットで持てるんだね（約数の個数ぶん必要になると思ってた）。このことにコンテスト終了時点で気づいていなかったのは酷い。素因数分解しない前提で考えてたから抜けやすくはあったろうけど。（素因数の種類数をKとして）2^K種類に分類できたらそれぞれの個数だけわかればいいというのも見えにくい。ここまでわかれば、あとは普通にDP。2重ループで自分にはやや見えにくかったが、特に難しいところはない。高速ゼータ変換を使った方法も、各ビットパターンに含まれる個数の和を高速ゼータ変換で求めて、選び方を2のそれ乗で求めて、逆変換でそれぞれの通り数が求まるという自然な流れだった。

（追記2）ユーザー解説で素因数分解しない解法があったのでやった。Mの約数であるようなA_iに対して、各素因数をMと同じ個数持っていなかったら0個に潰してしまう。そういう半端な素因数はA_iとM/A_iの両方に含まれるので、gcdを上手く使うとできる。これをビットで持つために素因数毎に分解したいが、変換後のAで違うもの同士をぶつければgcdで分解していけそうだ。ここは少し考えたが、結局解説の方法が良いということに。分解したリストを持っておいて（最初は空）、リストにあるもので割れるだけ割って残ったものを今度はgcdで調べて、共通部分があったらそれをリストに追加して元の要素はそれ割る（2個に分ける）（A_iを割り切らないものしかないので1が追加されることはない）。リストが完成したとき、素因数毎にバラバラになっている保証はないが問題ない。提出前に解説を読み直して気づいたが、リストの総積がMに足りなければ答えは0通り（あぶなかった）。あとはそのリストを使ってビットに変換して高速ゼータ変換に合流する。まあコンテスト中にできる分量ではないかもしれないが、実際のコンテスト中にはこういうのを思いつきたくて考えていたのだ。解説を書いた人ありがとう。

ABC348

ABCEFの5完。

A - Penalty Kick

ちゃんと問題文読むのあきらめて、サンプルとかも見てそれっぽいのを書いて提出したなあ。

B - Farthest Point

距離の2乗は整数なのでそれで比較する。番号が小さい順にやればよい。

C - Colorful Beans

mapを使って色毎においしさの最小値を求めその最大値が答え。高速化したくなるのをぐっとこらえる。

D - Medicines on Grid

サンプル1の説明を見て、薬を使わないことも可能だと確認。スタート地点に薬がないと詰み。薬は持ち運びできない。これで問題を把握できた。実装が重くなる予感がするが、そもそも難しい。薬がある場所からBFSして、その場で薬を使ったあとに別の薬やゴールへ行けるかは判定できる。てことはO(N)頂点の有向グラフが作れて、そこでDFSしてスタートからゴールへ行けるか判定すればよさそう。たぶん解けたので、飛ばした（21:18）。

EFを通して戻ってくる。頑張って実装スピード重視で書き、15分くらいでとりあえず書き上がって提出してWA。添え字のi,jが2種類あったのと、有向辺の行き先かの判定が普通に間違ってたのと、4方向のループの添え字がhで高さのhと被ってたので、コンテスト終了後も含め3WA。

E - Minimize Sum of Distances

C_iが頂点数のようなものだとすぐ気づけてよかった。Cの合計とD（距離）の合計を管理すればよさそう。1つの辺を使うとCのぶんだけDが増える。これオーバーフローしないか？と思って計算すると、ギリギリlong longに収まる。なるほどNが微妙に小さいのはそのためか。まず、DFSして自分と自分より下のぶんを計算する。もっかいDFSして、自分より上のぶんを足す（けっこう大変）。最後に最小値を求めるところでは、初期値に頂点1の値を使う。サンプルが合わず、原因はCの合計の変数をC_iの変数に間違って書いてたことだったが、デバッグに15分くらいかかった。

（追記）全方位木DPで解き直した。確かに準備しておけばコーディング量自体はかなり少ない。

F - Oddly Similar

AtCoderで400万個の数値の入力はかなり多い。入力だけでTLEする人も出そうな。さすがに、2000*2000*999は4*10^9くらいなのでダメそう（書き方によってはいけるらしい）。2000*2000の配列を用意して、一致する個数をある程度高速に書き込めれば（あるいは書き込んだことにできれば）よさそうだが、それができるか。数列の位置毎に考えていいことに気づく。一つの位置に最大で999種類の数があり、同じ数毎にその個数の2乗の個数の場所に1を足したい。種類数が多いぶんには（計算量的に）困らなそう？問題文を読み直すと個数の偶奇だけわかればいいから足すんじゃなくてxorでいい。かなり難しそうに思ってそれでもかじりついて考えていたが、bitsetを思いついて確信はないが実装に入った。999種類の数毎にxorしたい位置を1にして、N個の数列から見て実際にxorする。一つの位置につきN^2/64程度の計算回数でそれをM回なので間に合う。実装で、数列の番号をi、数列内の位置をjとしていたので、問題文のi,jが両方数列の番号であることを忘れてNとMを間違えて最初サンプルが合わなかった。