ABC170

昨日よりだいぶ調子よかったけど結果は逆。Fは時間内に解けなかったけど最後までワンチャンつかみに行けていた。

A - Five Variables

15から引いていけば答え。Aでこういうの書けると嬉しい。

B - Crane and Turtle

全探索。鶴がi匹なら亀はX-i匹（iは0以上X以下）。

C - Forbidden List

面白そう。そしてけっこう怖い見た目だが、制約がわりと親切で答えは0以上101以下なので、答え候補を長さ102の配列にしてp_iで潰していき、最後に全探索。pair<int, int>に{ abs(X-i), i }を入れてminをとっていくと楽。もっとスマートな書き方はあるかもしれないけど。

D - Not Divisible

A_iが10^6以下ということで、そこが使えないか考える。割り切るというのは約数ということ。自分も含めて全体で約数が1個だけ（自分自身は約数）と言い換えできる。mapとか必要なく、長さ10^6+1のvectorで個数をカウントできる。あとはそれを使いO(sqrt(A_i))かけて約数が何個あるか数えればよい。計算量に√が付くの珍しいなと思ったけどやはりもっと速い解法があるのね。

E - Smart Infants

やばそうな問題。std::setを使えば解けそうではある。解けるので頑張って書く。multi_setも考えたが、まあset<pair<int, int>>でできるのでそっちにした。setの最大要素を見る定石知らないのでゴテゴテ書いて関数にした（O(1)だと思うけどlogが付いてもいいし）。setを2*10^5個持つのは初めてで本当に大丈夫か不安だった。レーティングは不変だが、どの幼稚園に属するかは変化するので別のvectorで更新する（最初更新を忘れてた）。天才感がなく時間ばかりかかる。PASTかよ。

F - Pond Skater

H*Wが10^12になりえると誤読していた。'@'は別途10^6個くらい位置で与えられるという設定で。ただ、サンプルの入力は最初に見たんだよね。そのうえで誤読にしばらく気づかないの意味わからん。

//広い @は縦横斜めに連結する 塊として捉えられそうにも思ったがKがでかいとき疎な配置で地味に邪魔できるな Kが小さくてもか
//広くはなかったｗ

さて、それなら普通にBFSとかもできそうだ。Kがでかいのでそのままだとダメ。ただ全体で10^6マスしかないので、1マスあたりO(1)で処理できれば問題ない。1回探索した場所に行き当たったらそこでやめればいいか。全然解けてないけど、考えを寝かせる時間で実装するの効率がいいので、実装に入る。実装の途中で、探索済みのマスの向こう側に未到達のマスがある場合があることに気づく。そこで、マス毎に4方向のリンクを持つやつを使う。その方向で次に探索すべき場所を更新していく。探索した場所を飛ばす感じでつなぎ直せばいいだろ。とりあえず書きあがったくらいでタイムアップ。サンプルが動かないので惜しくない。これかなりややこしいから準備が必要だった。そもそもこれで解けるかわからんけど。

東京海上日動 プログラミングコンテスト2020

コンテスト名、全角スペースなの！？ともあれ今日は気温が下がって朝から心の調子が悪かった。コンテスト中も最初はモチベなくてびっくりした。まあ最後はDを書き切れるか通し切れるかでドキドキしてた。

A - Nickname

サンプルも最初の3文字を出力していて親切？substrに慣れないのでresizeした。いま気づいたけどこのサンプル高橋直大じゃん。

B - Tag

設定が多いのでそれ全部確認するのに時間をかけてしまう。まず、座標は差の絶対値だけが重要。そしてスピードが同じかそれ以下だと追い付けない。そうでないときT秒で(V-W)*Tだけ追い付ける。オーバーフローに注意する。文字にすればこれだけ。一つ一つの要素は簡単だが全てを間違いないようまとめ上げるのはかなりの負担だった。

C - Lamps

けっこう照らす範囲が広い。光の強さ0でも自分のことは照らしてる。自分を照らしてる個数が改めて光の強さになるので、かなり更新がきついというか、なんか次元の違うものを代入してる感が。シミュレーションをするならいもす法でできるが、ダブリングなどで高速化するのは無理そう。かなりの時間悩む（そのうち景色が見えてくるんだろうなあと思いながら悩むのコンテスト中よくある）。増えていきそうだなというのはわかる（サンプルもそれを示唆している）。実験をしてみるとやはりO(log(N))で全部Nになりそうだ。何回やれば十分かを考えるのは難しいので、全部Nになったらループを抜けることにした（いいムーブ）。操作回数がO(log(N))でいい証明はできなかったが、小さいケースの挙動を慎重に確認して提出した。

D - Knapsack Queries on a tree

今日は問題文読むのにむちゃくちゃ時間かかったなあ。根から葉まで最大で18個頂点が並ぶ二分木。番号はセグ木みたいな感じ（二分木に限っては0-indexedにしないほうが実装楽）。まず、二分木じゃなくて普通のナップサックを書く。その価値を実現する最小の重さというのも考えたが、この問題の価値は小さくないのでやはり普通にその重さの最大価値でDPだろう。DPテーブルを共有は無理にしても、上手いこと分岐させて計算量を削減できないか。難しそう。が、上9個（普通にDP）と下9個（2^9全探索）に分けてギリギリ間に合いそうだと気づいてしまった。解説PDFに合わせN=2^(2*K)-1, M=max(L)として、前計算がO(2^K*K*M)、クエリがO(2^K*K*Q)。計算量は落とせるはずと思っていたが、これでギリギリ通るとも思ったので実装に入る（ほんとは計算量を落とすパートが楽しそうだったけど仕方ないね）。

まず、O(M)のメモリを消費するDPを2^9個行う（実装して気づいたが2^8個だった）。子へ移動するときは、頂点番号を2倍して、何個目のDPかのビットを見て立っていたら1を足す。クエリは、番号が2^9より小さければ前計算したものを使わず普通に全探索。番号が2^9以上なら、葉から2^9以上の範囲を全探索して、残りは前計算を使う（初めて2^9未満になった親の番号から2^8を引けば何個目のDPを参照すればいいかわかる）。「重さj以下の最大価値」でDPしてある（ちょうどjではない）ので、重さの合計がWだったら重さL_i-Wの情報だけでいい（前計算の参照がO(1)で済む）。実装上は、何個分全探索するかを先に求めておいた。

提出して、TLEは免れたが、WA。1回くらいのWAは覚悟していた。2.5秒くらいかかっていて、思っていたよりずっとギリギリだった（ジャッジかなり速くなってるから大丈夫だと思ってた）。結果的に3WAからのACだった。子を辿るときビットを見る場所が逆だったのと、何個全探索するか調べて頂点番号を変化させるから元の番号を保存してたのに使ってなかったのと、前計算は9個でDPするけど番号は8回しか変化しないのが慣れない処理で間違ってたので3WA。落ち着いて見直せばペナルティを減らせたと思うけど、落ち着いて考えていたらコンテスト時間が終わってしまうので仕方ない。ACできないんじゃないかと怖がりながら（実際しょうもないミスを最後まで発見できなかったことが何度もある）、よくやったと思うよ。

AGC045

疎外感。今回はたまたまレーティングが上がっただけ（それ自体は嬉しいが）。自分はレーティング1200以上だからratedになってるけど、実力がある人のついででしかない。

A - Xor Battle

最後が人1なら人1の勝ちというのはすぐわかる（0か非0の選択肢がある）。自分の手番が続いたときにどのA_iを使うかの組み合わせは色々あって大変そうだが、掃き出しができる。掃き出す途中で何回も使うの心配になったけどxorなので何回使ってもいい（K回使ったらK%2回使ったのと同じになる）。最大100個のテストケースがあるので、計算量がいつもの感覚でわからなくて精神的にかなりの負荷だ（まあ普通に計算すればわかるけど）。さて、全然解ける気配がなかったが、人1のターンが連続していてもそのうち1個しか使わなくていいことに気づいた（この時点で30分くらい）。

つまり、それよりあとの人0が対処できないものを人1が選べばそれで人1の勝ちが確定する。対処できるものをいくら組み合わせても対処できる（何回使ってもいいので）ので人1がそうする意味はない。とりあえず実装。計算量が心配だが、掃き出しというより、A_iをiが大きい順に追加していけばいいと気づいてきれいに実装できた。MSBがiビット目のものをp[i]に入れて、追加時は被ったらp[i]とのxorをとってより桁数が小さい数にしていけば、log(A)回以内のチェックで済む（これに気づいたの嬉しい）。xorの掃き出し法自体は経験があったけど、要求されるものが少し違うので実装にはやはり時間がかかった。計算量としては、ビット演算が高速なのもあってlog(A)は1個しか付かない（これなら心配ない）。あとは、人1が勝つ方法がそれ以外にあるか、最初のターンが人0だったら何かする意味はあるか、に確信が持てていない。いくつかの例を試して大丈夫そうなので、証明できないけど提出してしまった。AC。ペナ出してる人が多いので心配だった。

B - 01 Unbalanced

'?'がないなら、左から累積和をとりながら見ていってそれまでのminとmaxを更新しながらそれらと現在の値の差のmaxを更新していけばいい。それをベースに色々考えたが、いや大して考えられなかったか。二分探索とか考えたけど、「0が多い」と「1が多い」が対立する中どこを0にするか決めようがない。

C - Range Set

全部1の状態からもスタートできる。あと逆から考えたい。というのはすぐ思いつくが、連続する0があるやつと連続する1があるやつを包除みたくかなり丁寧にカウントする必要がありそう。AよりBがでかいときのはみ出しとか不可能でしょ。

ABC169

1ペナ全完。これでこの順位はしょっぱいなあ。一応レーティングは上がった。

Bみたいのどんどん出題されてほしいけど、かなり難しいと思って時間をかけたのにRE食らってめちゃくちゃ残念。Eは順位表にペナが少ないのを見て甘えた。Fの解法は天才感あった（これをあんな大量に通してるのおかしいでしょ）。

A - Multiplication 1

「積雪深差」を思わせる簡単なA。用意したテンプレにa*bと書き込むだけだったので、少し見直しもしたのに16秒。これは早い。Aはこのくらい簡単でいいと思う。

B - Multiplication 2

俺はプロだから見た瞬間わかるんだけど、これはめちゃんこ難しい。10^17*10^17みたいな掛け算が生じうるから、掛けてからの大小判定ができない。10^18を途中で超えても0を掛けて0にされちゃうことに気づいたときはあまりの難しさに笑ってしまった。まず、ll（long long）で10^18の定数を用意する。1e+18（double）から変換しても、さすがにこのキリのいい数はdoubleで厳密に表せる（constexprにすればIDE上で確認できる）。入力を受け取りつつ、0が来たら0を出力して終了。10^18を超えるかの判定は、A*R>10^18 をしたいので、A>M/R、10^18を少し超えたものを見逃すのはいいけど10^18以下の数を超えたと誤判定するのはダメなので、切り上げてA>(M+R-1)/R。掛け算の前後に超えたかの判定をして、超えてたら最終的に-1を出力する。

提出してRE。難しいのはわかっていたのでかなり慎重にやった。しかし頭がオーバーヒート気味で、バグを残してしまった。最近どこかでこういう処理の周辺をかなり調べたのになあ。このコードでREの原因は0除算くらいしかない。既に超えたと判定していたら割り算はしないように修正、AC。（オーバーフローすると乗算の結果が0になることがある（2^32*2^32など））

REのとき表示がいつもと違うことに気づいたが、しばらくするとClarに「ジャッジ結果の表示方法が変更されています」というお知らせが来た。

C - Multiplication 3

これは簡単。しかし楽な実装を考えるのは難しい。特に思いつかないので愚直な実装で。Bを文字列として受け取り、小数点を無視して整数化。最初、答えが最大で10^19近くなると勘違いして、unsigned long longで1.6*10^19まで行けることを確認していた。しかしよく見ると10^18未満なので何も考えなくてよかった。値を受け取ったら掛けて100で割ればよい。

D - Div Game

要するに、素数冪で割っていく。素因数分解して、各素数が何個あるかわかればよさそう。速度も要求されないので、std::mapを使って数えた（楽だった）（約数列挙と違って反対側を見なくていい）。同じ数は使えないので、p^1, p^2, p^3 のように取れるだけ取ったら、それより多くは取れないし半端は一番大きいやつに押し付ければ達成できるので、その個数が最大。普通の問題もいいものだ。

（解説配信を見て）あ、Nを1にしなくていいの忘れてた。

E - Count Median

何でソートするのかなーとか。図を描いて右にN/2個とか考えても全然わからんしFと交互に考えていた。EFを見て両方解ける可能性がそれなりに高いと思ったので、双方に惜しみなく時間を使う。

まあ中央値の最大値を考える。すると、Bを（Aは無視で）ソートして真ん中のものがそうだ（Nは奇数とする）。中央値以上のものがN/2（切り捨て）個ないといけないので。たまにあるパターンではあるけど、Aが関係ないのやばいね。同様に最小も求まり、その間の数は全部達成できるのでは？いくつかのあやしそうな例で考えてもそうだし、順位表を見てみんな解いててペナが少ないし、もう時間もかなり来てるので、提出してAC。これは難しい。想像も証明もできない。

F - Knapsack for All Subsets

ABC159の"Knapsack for All Segments"を思わせる。空集合もありにしていいことを確認。なんか高速ゼータ変換が浮かぶけど、Nが3000になるので2^N個はハチャメチャに多い。とりあえず普通のDPを書いてみたり。どうも2^Nの大きさを忘れがちで思考がグルグルしていた。さて、f(全体)は求まったがこれからどうするか。一応、ちょうどi個で和がSになるやつらの通り数が各iについてわかれば解ける。O(N^3)のDPでできそうなのでそれを高速化したい。けっこう悩んだ。"Knapsack for All Segments"のときは、普通のDPとほぼ同じコードで解けたので、その方面で考えていると何かひらめく。ばらばらに（各iについて）求める必要はない。ちょうどi個のやつらは2^(N-i)回足されるので、DPのタネを最初に2^N倍しておいて、DPの更新で足すたびに「お前らは半分ね」していけば。ちょっとコードがバグってたけど落ち着いて直してサンプルが合い提出してAC。これは天才みがあって気持ちのいい問題だ。