ABC149

いつもと違うPCで参加したけど問題なく終わってよかった。unratedは常に残念ですねー。unratedなことに気づかず戦っていつも通りくらいの結果。いいセットだった。

A - Strings

T+S

B - Greedy Takahashi

Bなのに32bit整数に収まらない。残り行動回数を持ってシミュレーション。

C - Next Prime

どう直したら使いやすいかわからないまま放置してる素数列挙ライブラリを貼った。サンプルが上限を示してくれてるのは気づいたが、まあ最初に見えた方針で。20万までの素数を列挙しておいて初めてX以上になったところで出力する。

D - Prediction and Restriction

DP臭がするうえにわからないので5分くらいでEに行った。

FがわからなくてDがかなり解かれてるので戻ってきた。いやなぜ気づかない。K個の列に分割できるじゃん。あとはDPで解けるが、よく考えると、筐体の出す手（手を筐体が決定するだけで筐体が出すってのは変か）の（分割後の列で）連続する部分列が同じ手で成っていたとして、最初に勝って次妥協してを繰り返すのが最善だ。つまり貪欲でいい。ええと、筐体の連続する2つの手が異なるなら、1個目が勝ちなら2個目も勝てるし1個目が勝ちでないなら2個目の邪魔にならない手を選べる（新ABC、こういう「思ったより簡単にできている」問題が多い気がする）。ということでDPを使わず書いた。

終了後に知ったが、分割せずに（勝敗だけ記録しておいて）貪欲で解けるんだね。

E - Handshake

問題文を頑張って読むと、N*Nのマスになる。Aはソートしていいので降順ソートして、そうするとマスは上に行くほど左に行くほど大きい数が書かれている。これを大きい数から貪欲にM個取ればいい。制約にでかい数が出てこないのでうっかりするが、Mは32bit整数に収まらない可能性がある。

N*Nのマスを1行ずつ見ていく。例えば「10以上の数を全部取ったら何個になるか」はO(NlogN)でわかる。各行で二分探索すればいい。さらにそれを使って二分探索すれば、いくつまで取ったらM個をオーバーするかがO(NlogNlog(max(A)))でわかる。もう少し考えると、最初のO(NlogN)はしゃくとりでO(N)になる。Nがそんなに大きくないのでlogが2つ付いても間に合うけど、最近はしゃくとりにも慣れてきた（それに二重二分探索も決して簡単ではない）。

降順はループ方向が慣れないので、N*N-M個を小さいほうから貪欲に取る問題を解くことにする。全体の和は2*N*ΣAで、ここから引いたものを出力する。これを考えるのも時間かかるけど、これすらわからないようではこの問題は解けないと思ってこの方針にした（実際、これを考えた経験値はこの問題を解く中で役に立った）。入力を昇順ソートし、累積和も持つ（しゃくとりの中で計算できそうだがこのほうが簡単そうだ）。さて、二分探索では「どの数までならM個以下に収まるか」「どの数で初めてM個を超えるか」しかわからない。求めたいのはM個の和だ。とりあえず、コードの全体像が見えるまでテキトーに書き進め、それを見て考える。誤りを含むコードをコントロールして利用できるのは調子がいい。

和で二分探索できないかとか色々考えたが、DDCC2020予選E問題の経験を生かし境界の前後は必ず探索されるという性質を使い二分探索内でM個の和を計算した。具体的には、二分探索内ではt以下の数を全部取ってその総和sumと個数kを求める。個数は二分探索に使い、総和はM個の和の推定に使う。k>Mのときのsum - t * (k - M)の最大値が求めたいM個の和。tが初めてM個を超えた数のとき正しい値になり、それより大きいときは小さく推定するので、最大値。探索範囲は、多少広げても悪いことが起こらない問題設定だったので安全側に振った。最後、サンプルが合わずに苦しんだが、ソートする前に累積和を構築してしまっていた。

F - Surrounded Nodes

Eに時間をかけたあとで意外と時間が残っていたので挑戦したがわからなかった（あと、コンテスト中に挑戦する問題は多いほどいい、復習時のモチベが違う）。内側の白を決めてそれに接する黒を固定し外側を自由に決めるみたいなイメージで考えていったが、穴となる白は連続しているとは限らないし外も自由に決められるわけじゃないし連続している白が内側と外側に分かれることすらあって最初のイメージがボロボロだった。

AGC041

いやーtourist回面白かった。結果は普通だったけどなあ。

A - Table Tennis Training

問題文が異常に読みにくい。外国人が書いたものなので、翻訳が良くても文化が違うのだ。頑張って読むと内容自体は異様に簡単そうなので、3分くらい経過していたこともあり順位表を見てみる。するとWA（TLEとかの可能性は排除できないけどまあWA）の嵐。なるほど、距離が奇数のときは向きが変わるってことか（必ずしも端で出会うわけではない）。min(f(n, a, b), f(n, n - 1 - b, n - 1 - a)) という書き方で時間をかけて書いた（A<Bの制約がなかったほうが楽だった説まである）。

B - Voting Judges

簡単そうな設定で奥があるのすごい。V=1なら簡単なのだが、Vがでかいとライバルにも票を分配することになるので難しい。とりあえず、ある問題を採用できるかの判定を考える。これがO(N)でできれば二分探索で解ける。tourist回、前回もこの辺の問題で二分探索してなかったか（好きなのかなと思いながら解いていた）。さて、毎回その採用したい問題に投票するのは当然として、Aが自分以下の問題や、上位P-1個の問題にも毎回投票して損しない。残ったライバル問題も、自分が到達できるA_i+M以下までなら投票していい。逆にそれより多く投票したらダメだ。で、票の配り方が難しいと思ってたけど、M*V票をM個以下ずつなら自由に分配できることになんか気づいて（M個ずつV問に配ってから切り崩すイメージ）、これで解けた。

C - Domino Quality

N=2はできない。3はできる。4はできる。できるやつの倍数もできる。ここで、様子を見るために提出（こういう戦い方ができるの楽しい（これで正解なのではという疑いがなくなるのも大きいし、半分くらいACなのでフォーマットが正しい確認にもなる））。かなりWAが多いので、あまり惜しくない感じ。3以上なら常に可能という線も濃くなってくる。5はできた。3の周囲を囲えばいい。周囲を囲ってN-2やN-1のケースに帰着させるテクはありそう。しかし、7や11も簡単ではない。5だけ書き足してまた提出することも考えたが、そうしているうちに11ができてしまった。あまりにもケースバイケースすぎてこういうのが想定とは思えない。7ができない証明とかも思いつかないし、7もなんかできてしまった（碁石を使って考えていた）。終了時刻付近で考えていたのは、周囲を太さ1か2で囲うことで残りを必ず3の倍数にできて、3の倍数なら比較的密度をコントロールしやすい（そもそもN=3に密度の異なる2つの解があるしそれを好きな個数並べることで何でも作れそう）ので、全てのNについて可能なのではと。違うサイズの解を組み合わせる発想が出なかったのが残念。コンテスト中は、「N=7はできるのか？」とかが楽しいからついそっち考えちゃう。視野がせまい。

ABC148

ratedでこれはさすがにクソゲーすぎる。全完でレーティングが落ちるんじゃ、俺はこのコンテストで何を得たんだよ。

A - Round One

自分はABC075のAでxorを使えたことだけを心の拠りどころとして生きているので、ここでもxorを使おうとしてしまった（a^b（1^2^3==0なので））。1分切ってるから結果オーライだけど、冷静になってみると、6-a-bなどと書いたほうが自然だった。

B - Strings with the Same Length

新たな文字列は作らず、SとTを1文字ずつ出力していく。

C - Snack

最小公倍数を出力するだけ。えっ、マジ！？って何回も確認して時間食った。

D - Brick Break

この「任意の」読みづらいからやめてほしい。「全てのiについて条件を満たすとき」って意味なんだろうけど「どのiでもいいから条件を満たすとき」にも見えてしまう。ここでトイレに行った。直前にも行ったけど出なかった。先週何もなかったので久しぶりのコンテストで緊張していた。トイレの中ですっきり解けたので実装。1,2,3,4みたいななるべく長い部分列を見つけたいので、1から貪欲に探せばよい（同じ数が複数あるときも最も左のものを取ってデメリットがない）。

E - Double Factorial

2つ前を見るということでフィボナッチみたいなイメージを持ってしまったが、よく見るとただの階乗じゃん（!じゃなくて!!のほう）。Nが奇数のときは積も奇数なので10の倍数にはならない。偶数のときは、サンプル1やそれよりNが小さい領域でも5より2のほうが多いので、素因数5の個数がわかればいい。（(2n)!!は2^n*n!で2^nに5は入ってないので以下NをN/2で置き換えてN!を考える）1以上N以下の5^kの倍数の個数をk=1から5^kがN以下の範囲で足せばいい。125の倍数だったら3個だけど、5の倍数と25の倍数のときにも足してるので（ということをコンテスト中はあまり深く考えてなかった気もするが）。1以上N以下の5の倍数の個数って単にN/5（切り捨て）でいいんだよね。それはそうなんだけど、意外にも感じる。

F - Playing Tag on Tree

木なので、辺は全部橋。青木君は高橋君に向かって動くだけで追い詰めることができる。高橋君は（青木君を根として各頂点の深さを計算して）深いほうへ逃げるだけ？解けてないけどとりあえず必要そうなところだけ書き始める。書いてる途中で、シミュレーションせずとも深さの値だけでよさそうだと気づく。書き上げて、とりあえず実行してみるが、サンプル3が合わない。ここで気づく。高橋君が一旦浅い場所へ戻ってから別の深い場所へ逃げるケースが漏れてた。証明はすぐできそうになかったのでその実装をやる。かなり時間をかけて汚いコードを書くもサンプル3の出力が変わらない。めっちゃ体温上がってた。こういう、やりたいことはわかってるけどゴチャゴチャしてるの苦手すぎる。ここでググってサンプル3のグラフを可視化。合ってそうだが、ここで気づく。青木君の初期位置を根とする根付き木で考えていたので、uが青木君だと勘違いしていたのだ。そこを直したらサンプル通ったので（もういい時間だし）提出、AC（実装で混乱しててWAにならないのわりと珍しい気もする）。もっといい方針があったと思う。そうすれば証明もできたし証明と実装の時間もかからなかった。これは今の実力だと仕方ない。

ABC147

4完。楽しかったけど結果で死亡するやつ。

A - Blackjack

Yes/Noにしろってchokudaiさんに言われませんでしたか？内容自体はいい問題。

B - Palindrome-philia

全探索じゃないBもいいね（貪欲かな）。N/2（切り捨て）まで調べる。

C - HonestOrUnkind2

2^N通り調べるだけ。実装がそこそこ重いけどさすがにこのくらい慣れてますよと。が、ふと我にかえると条件がわからなくなる。不親切な人を調べなくていいのはわかる。じゃあ、正直者が「この人は不親切な人だ」と言ってる対象が嘘を言っていなかったら？矛盾はないけど正直者でない証明にはなっていない。じゃあどっちでもいいんじゃ？みたいな感じで最初正直者の不親切発言を無視していた。サンプルが合わずその条件を入れる。これで「正直者が嘘を言ってないか」はチェックされるので深く考えず提出（さすがに深く考えるのはコンテスト後でいい）。当然AC。実際は、どっちでもいいなんてことはない。最初に各人が正直か仮定してるので、それに反したらダメ。具体的には、不親切な人の発言はチェックしてないから嘘を言っていたらアウトだしそもそも正直者にカウントしてない。めちゃくちゃやんけ。全探索してるんだから、不親切として矛盾がなけりゃいいんだよ。

D - Xor Sum 4

A xor B = (A + B) - (A and B) * 2 みたいな性質があるので、まず全体の和を求める（各AがN-1回現れるっぽい）。そして各Aとのandだが、これはループを回しながらbit位置毎のそれまでの出現回数を持っといてA_iの立ってるビットと掛け算すればいい。入力を配列に保存せずできてよかった。

E - Balanced Path

AとBがあって塗り分けるというけど結局AとBの差だけが重要。各マスに1個の非負整数が書いてあって、経路上での合計が100で、いくつか選んで50にできるなら偏りは0、みたいな問題。経路がわかっていれば簡単だが、経路が多すぎるので無理。情報を保持するには値の範囲が狭くないとと思って制約に気づいた。全部80やんけ。全部80だから見えないんだよね。さて、この制約なら、そのマスに至るまでの合計としてありえるものを保持とかはできる。しかし、経路によって使える数が変わるので、合計から偏りはわからないし、現れた数を経路の数だけ保持するのは無理だし、経路関係なく現れた数だけ保持しても意味ないし。Fも少し読んでいたのだが、ここで完全に詰まって、以降ずっとFをやっていた（残り45分くらい？）。

（追記）合計じゃなくて偏りで普通にDPできたは。

F - Sum Difference

例えば数列が1,2,3,4,5なら簡単で、作れる最小値から最大値まで全部作れる（0から15まで16個）。制約から、選ぶ個数を0からNまでN+1通り試す方法を思いつき行けそうだと思う。XがDの倍数だったり全然関係ない数だったりが難しいが、これはもうGCDをとって割ってしまう。XとDが互いに素になった。-1を掛けることでXかDを非負に固定できる。どっちがいいのか最後まで揺れてた。Dが0のときは場合分けしてしまう。必要かどうかわからないけど、一応Xが0のときも場合分けしてしまう。さて、選ぶ個数を固定すれば答えは簡単。しかし、被りが生じるのでそこは引き算しないといけない。選ぶ個数をiとすると、Xの寄与はX*i。Dの寄与はDの倍数。互いに素なので、X*i%Dで分けることができる。Dで割ったあまりが異なれば被りは生じない。あまりが同じもの同士でmapを使い（使わない方法もある気がしたが短時間ではわからなかった）区間が被った分を引いていく。たぶん区間の変化は単調だろうから不連続な区間は左右の端だけ保持すればいいと思った。閉区間なことに気をつける。サンプルを試し答えが大きく出るので、区間の長さをDで割る必要があることに気づく。この時点で2分前。しかしサンプルが惜しいところで通らない。原因を考えていたら終わっていた。

（追記）ミスを直したら通った。それとは関係なく、各変数がどのくらい大きくなりうるか全然わかってなかった。