週記（2022/09/19-2022/09/25）

09/19(月)

午後2時起床。先週の週記を少し書きつつ、もっぱらハーメルンを読み続けていた。午後10時前に1作読了。「犬とお姫様」。

syosetu.org

先週日曜日、つまり昨日読了した「女王様と犬」の続編で、比企谷八幡が高3、その他雪ノ下雪乃をはじめとする原作組がほぼ一律で高1となっている。雪ノ下陽乃は大1になっているので姉妹の年の差は原作と同じらしい。高1、高2と雪ノ下陽乃に付き従うことで鍛えられた比企谷八幡のスパダリっぷりが良い。年下になった原作ヒロイン組との関係やその中で改めて構成された原作と同じイベントたちが目新しく、非常に面白かった。

午後11時半を目前にして何とか週記の文章を作った。量が少ないのでハーメルンにかまけていても間に合ったのだ。読み返さずにいったん投稿。

CFの準備をしていたらスマホに通知が来た。30分後からTCO Finalsに関するオンラインミーティングがあるらしい。「午前12時から」と書いてあったので火曜日正午のことなんだなあと思っていたのに、実は日付が変わった瞬間だったようだ。心構えだけしてCF #821 div.2に出た。

Dashboard - Codeforces Round #821 (Div. 2) - Codeforces

Aはインデックスを\bmod kで分類してそれぞれ最大値を取る。Bはxとyのどちらか一方が0で、もう一方がn-1の約数であればよい。Cはちょっと手間取ったが全要素を等しくすることができる。a_1と偶奇が一致するところだけ見て一番後ろの値を全体にコピーし、その後残りにa_1をコピーする。

D1はちょっと面倒。aとbで異なるインデックスを取り出し、奇数個であれば-1となる。偶数個なら必ず達成できて、特に4個以上なら2個ずつコストyで揃えられるので、これが明らかに最適。問題はちょうど2個のときで、ここを頑張って場合分けした。まず隣接していないならコストy。隣接しているとき、その左または右に2マス以上空きがあったら、そこを経由することで2yで揃えられるので、必要コストは\min(2y,x)。

今n\ge 5なので最後の条件は必ず満たされる。コンテスト中はこれに気づかずまだ場合分けを続けた。左右に1マスずつ空きがあった場合は\min(3y,x)になって、これも満たさなかった場合はどうしてもxかかってしまう。

D2はdp。あらかじめy\le xの場合をD1によって取り除くことで、先ほど場合分けしたような左右の空きマスを経由する場合を考える必要がなくなる。あとはどのようにペアにして揃えていくか。異なるインデックスだけ取り出したときに隣り合うペアをxで揃えるという遷移と、yによって揃えるペアの一方として確保する、または以前確保したものとペアにする遷移だけ考えればよい。

確保している個数を次元に持ってO(n^2)。実際は2個確保した段階でその二つをペアにしてしまってよいので、O(n)でも解ける。今x\lt yなので、うっかりインデックスとして隣接するペアをyで揃える遷移をしても問題ない。

ここまで解いたらちょうど日付が変わったので、オンラインミーティングに参加。その間はEの実験を行っていた。そうやって別のことに意識を取られていると、まず英語が全く聞き取れない。内容は全部チャット欄にまとめられた文章で把握していた。一方でEの考察も全然進まなかった。

ミーティングが終了してから改めて考えるとすぐ解けた。t秒後(x,y)にスライムがあるとしたら、それはもともとt-x-y秒の時点で追加されたものであり、それより前に追加されたt-x-y個のスライムだけが今注目しているスライムの動きに影響を与える。

ここで、(0,0)に追加されたt-x-y個のスライムのうち、\lceil(t-x-y)/2\rceil個が右に、残りが下に進んだとわかることに気づいた。以降同様に各マスにいくつのスライムが到達したかわかるので、これを全体に対して求めた後、t-x-y+1個目の動きをシミュレートすればよい。

全完7位。上に4人も日本人がいるのは何事だろうか。

ハーメルンを1作読了。「ようこそ元暗殺者のいる教室へ」。主人公の間延びしたセリフが好きになれなかったが、暗殺教室とよう実のクロスオーバーはいいなと思った。もっといろいろ読みたいと思って探したところ、ほとんど存在しないことが分かって残念。

syosetu.org

週記の校閲を済ませて午前4時くらいに布団に入った。30分ほどハーメルンを読んで就寝。

09/20(火)

午前11時起床。

布団に横たわったままハーメルンを1作読了。「ＲＰＧ要素があるエロゲのＲＰＧ部分にドはまりしてエロそっちのけでハクスラするタイプの転生者」。日間ランキング1位だったので読んでみた。なぜ狂人と思われているのかの理由付けが上手い。最新話まで読み進められたくらい面白くはあったが、今の気分とは微妙にずれているように感じて、それほど印象には残っていない。

syosetu.org

昼食を摂り、しばらく本を読んでいた。午後5時前になってからノートPCの前に陣取り、インターン先の定例会に備える。月曜日が祝日だったので今日のこの時間にずれていた。

ノートPCにマイクがなくて、チャットによる参加になってしまった。先週の進捗はない。勉強会はOpenCVの話で、様々な画像処理や図形検出の関数が紹介された。幾何の問題として出くわしたら逃亡を選びたくなるほど面倒そうな処理がいくつも実現されていて、その手厚さに感動した。

夕食と入浴を済ませた後、リビングに転がって午後9時から2時間ほど寝てしまった。起きてからSRMに向けた準備をする。Appletを導入するつもりだったが、うっかり寝入ってしまってそれほど時間的な余裕がないので、今日もWeb Arenaで頑張ることにした。午前0時からSRM838。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19420

Easyはシンプルに実装が遅かった。最初にbitsetでdpして復元することを考えて、さすがに面倒だったので、選んだ要素を直接vectorで保持したままdpできないか考えてみた。定数倍もよくて十分間に合いそうだったので実装。サンプルを合わせてから、本当に間に合うかもう一回見積もりをやり直したり、最大ケースを試すかどうか迷って結局試さなかったりと時間をドブに捨て続け、提出したら200点を切っていた。

Medはバカ発見器で、自分は発見されてしまった側。ダイスの面数Sを昇順に見る。これまでの期待値をEとしたとき、新しい数が出る確率が1-E/Sになるらしいので、E\leftarrow(1-E/S)\times(E+1)+E/S\times E=E+1-E/Sと更新する。1/Sを前計算すれば十分高速。これに気付くのに30分以上かかってしまった。

後から計算して納得。期待値がE=\frac 1 A\sum_k kC_kと計算されたとする。ここでC_kは種類数kであるような場合の数で、Aはすべての場合の数の和、つまり\sum_k C_kである。ダイスを面数の昇順に考えているので、今の面数をSとしてこれまでの種類数は必ずS以下であることを用いると、各k=1\dots Sについて新しい数が出る場合の数は(S-k)C_k通り、そうでないものはkC_k通り。

よって更新後の期待値は\frac 1{SA}\sum_k((S-k)(k+1)C_k+k^2C_k)。整理すると\frac 1{SA}\sum_k(SkC_k+SC_k-kC_k)=\frac 1 A\sum_k kC_k+\frac 1 A\sum_k C_k-\frac 1{SA}\sum_k kC_k=E+1-E/Sとなり、先ほどの式に一致する。

Hardは辺の長さ昇順に見て、それ以前の辺によって端点が連結になっていない確率を求められればよい。これはABCで数え上げ版の出題がある。その場で再現できなかったので、少し時間を使って以下の問題を探し当てた。しかし数え上げを確率の計算に書き直せず、それっぽいものを書いて試そうとしているうちにコンテストが終了した。

G - Connectivity 2

チャレンジフェーズは何もせず。Hardが結構落ちてくれたので少し順位は上がったものの、27位となり、レートは2887→2785(-102)。今日はシンプルに僕が悪い。僕の頭が悪い。Hardはコンテスト中に書いていたものを完成させてみたがサンプルすら合わず。Nがやたら小さいことに注目し、UFの状態を全通り持つべきだったらしい。

読書に戻り、午前4時半に1冊読了。「虚構推理短編集 岩永琴子の純真」。第一話「雪女のジレンマ」が好み。雪女とその恋人の馴れ初めが延々語られ、推理は最後のアクセントに。その使い方も苛烈ではあったが人を幸せにする方向で、ハッピーエンドで良かった。ただこれだけで表紙にまで雪女が描かれるのはびっくり、と思っていたら第五話も雪女に関する話だったらしい。こちらも優しい終わり方だった。

さらにハーメルンを読んでいたが、午前6時を過ぎたあたりで寝落ちしたらしい。その後いったん目覚め、そのタイミングで就寝報告のツイートをしていた。

09/21(水)

午前10時半起床。午前11時からTA研修会というのに出たが、これは心得を読み上げるだけで10分程度で終わってしまった。

昼食を摂り、荷物を纏めて昼過ぎに実家を出た。仙台に帰る。母に車で駅まで送ってもらい、午後2時半の新幹線に乗った。車内では1時間ほどハーメルンを読み、残りは本を読んでいた。

午後7時帰宅。PCを起動してしばらく触っていたら眠気が強くなってきて、午後8時から午前1時半まで布団で寝ていた。

起きてノクターンノベルズを1作読了。「無愛想な転校生の裏垢を見つけてしまった。」。もうすぐ電子書籍になるようで、TLに流れてきた表紙イラストに興味を持って読み始めた。それなりに話数はあるものの思ったより進展が遅かった。主人公のリアルとSNSアカウントが紐づけられる展開を期待していたが、まだ描かれていない。

https://novel18.syosetu.com/n0085hq/

その後もノクターンノベルズを漁っていくつか読んでいた。朝が近づいてきて、さすがに明日のセミナーの準備をしないとまずい気持ちになるものの、なかなか手が動かず、結局午前8時になるまでずっとTLを見たりYouTubeを眺めたりしていたらしい。そこから1時間だけ前回の発表資料の残りに付け足したりして、午前9時就寝。

09/22(木)

午前11時半起床。二度寝は怖いしかと言って身を起こすほどの元気もなく、布団に横たわったまましばらくスマホを触っていた。正午くらいにやっと起き上がって準備し、出発。山の上の購買に閉店間際に滑り込んで確保したパンやおにぎりを食べ、午後1時からセミナー。

まず自分の発表が3時間弱。頻繁に止まって確認したり例を挙げたりしつつ丁寧にやっていたら、昨日新しく用意した部分まで進まなかった。なかなか伝わらず大変。うまい具体例を用意できなかったのはあるが、説明も悪かったのだろうか。証明を、「お気持ち」がわかりやすくなるようにと教科書のものから少し変えてみたら、必要な性質を正確に導くのがかなり面倒になったので、そこは失敗だったなと思う。感覚的には明らかなので深く考えていなかった。

次に博士課程の方のセミナーが2時間弱。先々週の続き。これまでずっと前提知識の部分で詰まっていたのが、じわじわ進んで今日ついに補題の証明に入り、感動した。肝心の証明は道具を念入りに確認していただけあってスムーズに理解できた。

午後6時帰宅。小一時間TLを眺めた後、思い立ってラノベの新刊チェックをした。一通り調べていざ注文、という段階で眠気に耐えられなくなり、布団へ。午後9時から午前0時半まで寝ていた。起きてからしばらくノクターンノベルズを読んでいた。

PCの前に戻ってリストアップしておいたラノベを注文。9月下旬から10月下旬まで一か月ちょっとの間に出る作品で、今回は28冊とかなり多めだった。新作にはそれほど手を出していないので、追っているシリーズの最新刊の出版時期が被っただけらしい。

午前3時から昼まで日記を書いていた。途中頻繁にYouTubeやハーメルンで集中を切らしてしまうのでそれほど捗らなかった。書いている間に話数が少ないものを2作読了。

syosetu.org

「大学生、上杉風太郎。インフルエンサーでホストやってます」。五等分の花嫁は原作をほとんど知らないのに、これは完結後の話だったので、回想の描写から結末に至るまでどういう展開やシーンがあったか薄々想像がついてしまった。まあこれは原作を知らないのに二次創作を読むときの宿命か。内容については良くも悪くも感じていない。ただ、ホストっぽいキャラはよくても主人公がホストそのものというのは好きになれなかった。

syosetu.org

「国民的大物女優観察記録」。こちらの原作は全く何も知らなかったので、ほぼオリジナルと変わらない感覚で読んでいた。好感の持てる勘違い主人公で面白かった。エタりかけに見えるが、ちゃんと一段落するところまで投稿されていたのが嬉しい。

午後1時前に就寝。

09/23(金)

午後8時半起床。今日はコンテスト二つ。まず午後9時からCF #822 div.2。

Dashboard - Codeforces Round #822 (Div. 2) - Codeforces

Aはソートして連続する3要素を真ん中に寄せるのを全探索。Bは実験エスパーで各段の両端だけ1にした。Cは1\le k\le nに対してその倍数を全部見てどれを消せるかチェックすることで、逆に各値を消せるkの最小値が求まる。実際、小さい値から順にいま求めたkで消していけば達成できる。今考えてみれば、kを昇順に見て消せる値を貪欲に消しても同じことだった。

Dは難しかった。吸収したスライムの区間を[L,R)として、aの累積和Sを取ることで必要な条件がS_R\ge S_Lと書ける。Lを固定してRを右に動かすことを考えたとき、先の条件を満たせる限界までいったん動かしてみて、その中でSが最大となるところを新しいRにして損しない。ただし端まで到達できるなら即座にYESとなる。Lについても同様のことを行い、どちらでも[L,R)を変化させられなくなったらNOである。

Eも難しい。a_{i,\ast}が交差iの等差数列になるように定めると、a_{r_k,c_2}-a_{r_k,c_1}\equiv r_k(c_2-c_1)となる。0\lt c_2-c_1\lt nかつr_1\ne r_2よりこの値はk=1,2で一致せず、よって条件を満たす。どうやって思いついたか定かではない。確か、行または列の値を揃えて少しずらすことを考えていたのだった。

Fも難しい。難しい問題だらけ。n+m\le 2^{k+1}を満たすkを取り、S_{[2^k,2^{k+1})}がS_{[0,2^k)}のflipであることを利用することで、いくつかのより小さいn,mに分けて再帰的に求められるが、クエリの個数が爆発してしまいそう。しかしよく観察すると種類数が少なかったため、メモ化することで十分高速になった。トリックはこうだ：分割後にn+m=2^kを満たさないものは高々一つであり、さらにn+mが2べきの場合、以降何度分割してもその回数ごとに高々2種類のクエリしか生成しない。

Fに1時間かけて順位が崩壊した。全完19位。

シャワーを浴びて午後11時半からCodechef、September Lunchtime 2022 div.1。3時間半もあって大変。ペナルティがないので提出し放題だったのだが、各問題に60個程度テストケースがあって、提出するたびにいちいち神経をすり減らしながら待つ時間が発生して辛かった。

https://www.codechef.com/LTIME112A

INCADDはA_{i+1}-A_iを観察するとすぐ解けた。この値をすべて非負にしたい。区間更新はある範囲に+1したあと右端を大きくマイナスする操作になるので、常にR=Nとして操作することでそのマイナスを無視するのが明らかに得。さらにL=1とすることで全体に+1することにして、-\min_i(A_{i+1}-A_i)回操作すればすべて非負にできることが分かった。セグ木で管理してAの更新に対応。ただし操作回数も当然非負である必要があり、これはセグ木に乗せるモノイドの単位元を0にするだけでは不十分だった。all_prodの際わざわざ単位元を掛けたりしていないのは当たり前。

ADJACNTPAIRSは簡単。最終状態を決めたとき、それと異なる値を一つ一つ揃えなければいけないのに加え、ちょうど一つずれたような連続部分列があればその長さlに対して\lfloor l/2\rfloorだけ余分に操作しなければならない。これは高々O(N)種類しかないのであらかじめ計算しておく。あとは最終状態の偶数番目と奇数番目としてそれぞれAにおける出現回数が多い順に値を試していく。O(N^2)通りあるが、明らかに答えを改善しない場合スキップすることでO(N)になる。なぜなら、偶数番目の値を決めるごとに、奇数番目の値としては余分に操作が必要ないもののうち出現回数最大のものしか見なくてよいから。

RMVNUMBERSは難しかった。相手の選択によらず適切に動いてAを空にできるか考える。これまで出現した値のLCMを今見ている値が割り切った場合、またはそのLCMが4\times 10^{14}を超えた場合にそうなるので、操作回数がある程度あればよさそう。2べきが昇順に並んでいる場合が最悪ケースのはずで、これでも50回も操作すれば十分。つまりM\gt 100のとき、先手も後手もやろうとすればAを空にできてしまうので、答えは必ず0となる。

あとはM\le 100の場合が解ければよい。Aを単純にvectorで持って再帰した。一段階再帰するたびにBで割り切れるか否かでAが完全に分かれるため、各深さにおいてvectorの長さの総和がNとなる。よって、空になったらさっさと0を返すのに注意すればO(NM)が達成される。コンテスト中は何を考えたかメモ化してしまい、0.49sec。この問題のTLは0.5secなので本当にギリギリ。日記を書いているときにこのメモ化が必要ないことに気づき、消して出しなおしたら爆速になった。

UNFRIENDLYは謎。どうせ持つべき候補が少ないタイプの問題だろうと思って、列の長さが\maxまたは\max-1なペアしか持たないようにしたら全然合わなかった。この下限をどんどん引き下げて何回も提出してみたが、TLには間に合っているもののWAのケースが全然減らない。そもそもA\le 3のケースですら盛大に間違えている。手元でランダムケースを作ったらすぐ落ちて、ようやく何がダメだったのか気づいた。

A\le 3のときの繰り返しパターンは2種類しかない。序盤でそのうち片方が一定以上優位に立ったとき、そこからもう片方のパターンに切り替えられないようだ。そこで、あるペア(a,b)を持つか決めるときに、対応する列の長さが\max-3以上という条件のほかに、すでにペア(b,a)を持っている場合も持つとするコードを書いてみた。とりあえずA\le 3のケースでは正しく動くはず。これで提出したら、なんと満点を取れてしまった。

残りは部分点。LCAINTERACTは直径を一つ求め、その端点の一方が根でないことを確認した後、そこから根がどれだけ離れているか二分探索で求め、その距離にある点の集合を半分だけ聞くのを繰り返して実際の根を特定するというコードでクエリ回数12回を達成した。直径の端点が根になってしまった場合に次数3の頂点を使った。中心を使うともうちょっと減らせそうだったがWA。BNDSPANTREEは区間スケジューリングで部分点1のみ。

合計481点で9位、レートは2799→2832(+33)、highest。BNDSPANTREEは明らかな必要条件からLとRを調整するだけで区間スケジューリングの順序と辺の重みの順序が噛み合ってうまくいくらしい。すごい。パスに対するクエリに答える必要があってHLDを使いそう。自分もそろそろ履修しなければならない。

UNFRIENDLYの解法の正当性がよくわからない。下のツイートを元に考えてみる。持つか持たないか迷っているペアが発生するとき、\max\ge 4であるから、今のところ最適とされている選び方の直近四つが(w,x,y,z)と取れる。ここでw=zかもしれないが今は異なるとする。候補として確実に持っているのは(w,x),(x,y),(y,z)で、この三つのうちどれにも繋げることができないのは(y,x),(x,z)のみ。

実際、今確実に持っているペアを反転してみると、挙げた二つはそれぞれ(x,w),(z,y)に繋げることができる。しかしわざわざこのペアを選ぶ必要はないので、なぜこれだけチェックしておけば十分なのかがわからない。例えば(x,z)なら(w,x)というすでにあるペアにzを足すことで再現できるため問題ないと言えるものの、(y,x)のほうはどうやって吸収されているのか本当にわからない。

ちなみに、こういう考え方は\max-2以上を持つとしても同じところまで進める。なんと条件をこれに強めてもACしてしまった。\max-1ではさすがに落ちた。

食事して午前4時からTCB51に参加した。

https://techful-programming.com/user/event/3235

3問目はこの位置としては難しめに見える。ずらす幅を全探索し、対応する要素の差を足し合わせる。4問目は前から貪欲に操作しなければならない。5問目はfの和をA_i\sum_k B_k+MA_jと書き直す。\sum_k B_kの符号を見れば答えの候補は高々二つだが、念のためA_iを全探索した。

7問目はかなり面倒。ある頂点の親を1にするのが最適で、変更した頂点を根とする部分木に対する{\rm dist}(1,\ast)の\maxはその場で計算、他の頂点のそれは全方位木dpのように計算して伝播してきた値を使った。

8問目は謎。最初にO(NM)のdpで値の種類数が1\dots\min(N,M)の数列を数え上げる。種類数がN未満の数列は必要な値をすべて含むような列ならどれからでも作れるが、そのような数列の数え上げにも今計算した値が使える。種類数がちょうどNの数列はそれ自身からしか作れない。

9問目は区間dp。10問目は|S|=cと決め打つとO(Nc)のdpが書ける。まだ決めていないSの要素数を持つことにして遷移をAの値で場合分けしてみると、A=-1の場合はdp_i\leftarrow dp_i+dp_{i+1}をi=0\dots cで行い、A\ge 0の場合はdp_A\leftarrow dp_A、dp_{c-A}\leftarrow dp_{c-A+1}だけ計算して残りは全部0にするという遷移になることが分かった。シンプルでいかにも速そう。これを実装すると、最悪ケースである全部A=-1のケースも手元で2.5secになり、提出してみると3.7secで通った。

理論値。時間は50分弱で、各問題ともボーダーまでかなり余裕がある。10問目はまたしてもTL 5secを悪用して定数倍高速化で通してしまった。改めて考えてみたところ、A=-1の場合の遷移を遅延させることでdp_{\ast}の非ゼロ要素が高々2個になり、具体的な値の取得も定数時間で行えて|S|を決め打つごとに計算量O(N)が達成できた。あまり見ない高速化で面白かった。

このあとYouTubeとネット小説に1時間ずつ時間を吸い取られてから日記を書き始めた。午前11時に切り上げてから少し読書。本を1冊読了。

「虚構推理 逆襲と敗北の日」。長編、ただし最初に短編のようなものが一つ付属していた。ちょうど解決シーンに入るところで数日読むのが止まっていたためちょっと没入感が薄い。そもそも解決自体割とあっさり目で、サブタイトルの意味もそこにはなく、続く主要キャラクターたちのやり取りがメインだった。この部分は興味深かった。岩永琴子はもうちょっと非人間的な性質だと思っていたのにそうではないようでびっくり。がっかりもしかけたが、その分は桜川九郎でバランスが取れているらしい。

ネット小説を読んで午後1時半就寝。

09/24(土)

午後8時半起床、午後9時からABC270。

TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270) - AtCoder

Aはbitwise ORを出力する。とりあえずRakuで書いたあと、もっと短くならないか4分ほど試行錯誤していた。

B問題は難しい。まずX\gt 0となるように適切に符合を反転しておく。0\lt Y\lt Xのとき壁を破壊する必要があって、Y\lt Zならハンマーを拾いにすら行けないため-1。そうでなければ|Z|+(X-Z)である。そもそも壁を破壊する必要がなければ答えはそのままXとなる。丁寧に確認していたらかなり時間がかかった。

CはXから祖先のリストを管理しつつdfsし、Yにたどり着いた時の状態を出力。Dはdp。Eは何周するか二分探索し、残りをシミュレート。Fは港と空港用の超頂点を用意し、その二つを連結成分に含めるか22通り全探索してそれぞれ最小全域木を求める。

GはX_i=A^i S+B\sum_{j=0}^{i-1}A^jと書ける。A=1は別に計算することにすれば、和を閉じた形にしてX_i=A^i S+B\times\frac{A^i-1}{A-1}=A^i\left(S+\frac{B}{A-1}\right)-\frac{B}{A-1}となる。これがGに等しいので、S\leftarrow S+\frac{B}{A-1}、G\leftarrow G+\frac{B}{A-1}と置きなおすとA^i S\equiv Gが求めるiの条件。S=0は場合分けにより、それ以外はA^i\equiv G/SをBSGSで解くことで答えが求まる。

Exは難しい。しばらく唸っていたら綺麗な表現を見つけて一気に解けた。カウンターの操作を、初期値A_iであるような値C_iをデクリメントするかC_i\leftarrow A_iとするかで表し、状態をS=\max_i C_iで定める。この値が0になるまでの期待値を求めたくて、遷移はカウンターiを操作するときS\leftarrow\max(S-1,A_i)と書ける。これでループのある期待値dpに帰着できそう。

dp_Sを状態Sから0に遷移するまでの操作回数の期待値とする。E=\sum_i dp_{A_i}とおいて、dpの値をすべてEの一次式で表す。S=x\ge 1に対してdp_x=1+\frac{\sum_i dp_{\max(x-1,A_i)}}Nとなり、x-1\ge A_iなるiの個数とそれに対するdp_{A_i}の和が求まっていれば、適切にEから引いたりdp_{x-1}を足したりして計算できる。

最終的にdp_x=X+Y\times dp_{x-1}という形で書けて、XとYは次にx=A_{\ast}となるまで変化しないので、その間の遷移をまとめて行うことができる。これによりS=A_1,A_2,\dots,A_Nのみ求めるのが十分高速。最後にE=\sum_i dp_{A_i}からEの値を求め、dp_{A_N}にそれを代入したものが答え。

本当にEを求められるのか、つまり\sum_i dp_{A_i}におけるEの係数が1にならないか不安だったが、エイヤと出したら通った。ではどんな値になるのかということでコンテスト後に式を追ってみたが、複雑すぎて断念した。

全完3位、日本人2位で賞金10万円。1時間ちょっとで全完したので時給10万円らしい。こんなことならAでコードゴルフしてなければよかった、と思ったが、実際のところ2位との差は10分以上あってどうしようもない。それより4位との差が2分ちょっとだったことのほうが重要で、B問題を丁寧に解いたことやG問題の式変形のコーナーケースを見落とさずノーペナで通せたことはかなり偉かった。

Gはこういう式変形をしなくても直接BSGSできるらしい。結局fのべき乗が同じ形で表せることが重要。解説のBonusは、通常のBSGSを非素数modで計算する場合と同じでf^{-1}を使わず頑張れるという話だと思う。このfでも\log Pステップくらい進めば周期に入るのだろう。

コードゴルフ。これはMHC後に縮めたものも含む。AはRakuよりAWKのほうが短くなった。Bは0とX、Zの間にYがあるかで場合分けしていることになって、この「間にある」という条件は例えば(0<Y)==(Y<X)のように書ける。正確には区間のちょうど端にある場合に注意する必要があるが、今は制約から関係ない。これをAWKで実装したものが最短になっている。

Cは根をYとして各頂点の親を求める方法を実装したがコンテスト中の方法に負け。言語はPerl。DはAWKでdpしたらPerlより縮んだ。EはRuby。以降は手付かず。

午前2時からMHC R2に出た。

Meta Hacker Cup - 2022 - Round 2

A1は文字を取り除いたときに文字列の中心になる場所を2通り試して、左右に出現する文字ごとの個数の差が一つだけ1、残り全部0となることをチェックした。あらかじめ文字ごとに個数の累積和を計算しておく。

A2でも中心を2通り試すのは同じ。その前に列全体のXORを計算することで取り除く値が何であるかを確定させておき、チェックをmultisetのハッシュで行った。値に素数を割り当て、その積を\bmod pで管理する。このpとしては素数をたくさん用意してあり、提出コードでは7個だが、思ったより高速に動作したため手元で18個使っても出力が変化しないことを確かめておいた。ちなみに、原始根を考えることでこれが\bmod{(p-1)}における和を管理しているのと変わらないことがわかる。コンテスト後に気づいて拍子抜けした。

Bは各クライアントに対して上位K個のパスを管理する。遷移も、適切な順序でクライアントを見ることで日付ごとに上位K個のパスを更新しながら行えるため、十分高速。

Cが解けずDに進んだ。D1は左右の和の差が交換によって\pm 2、\pm 4しかされないため、\pm 4、つまり1と3の交換を貪欲に行うべき。

D2は1と2しかないため交換しなければならない個数がわかって、それがc個だったとすると、Zから左に見てc個目までの1を右に見てc個目までの2と入れ替える、あるいはこれの1と2を逆にしたものを行うことになる。個数を管理するセグ木の上で二分探索することで範囲がわかり、その範囲内でインデックスの総和を求めると、差が答えになる。

Bが落ちて64点、178位。オーバーフローしていた。パスの利益は\max_i X_iで押さえられると思っていたのに、Y_i\lt X_i、つまり高く買って安く売る能無しクライアントのせいで壊れていた。

朝までC問題と格闘していた。はかりの左右どちらに乗せるかが重要だと思っていたが、対称性から無視できるらしい。とはいえ解説のこの部分はサラッと流されてしまっていたので、自分で説明を加えた。計算量は少し悪くなったものの間に合うオーダーに落ち着いたので満足。まずW_1と同じ重さのクッキーを1個以上はかりに乗せる確率を求める部分について、これは単に選ぶ順番(K+1)!通りを全部キャンセルしているだけなのでcombinationでよい。

次に、W_1と同じ重さのクッキーをk=1\dots C_1+Y個使う場合について考える。このケースに制限すると解説の文言が納得できた。k個をどのタイミングで選ぶか決めるごとに、そのうちどの位置に置かれたものが最後まで残るか一意に決定して、そこに置かれる確率はk個どれでも等しく1/kになるのだ。これによって、相変わらず選ぶ順番(K+1)!通りをキャンセルしてよいことがわかる。選び方を数え上げ、すべてのkに対して和を取った後、\binom{C_1+X+Y}{K+1}-\binom{X}{K+1}で割ることにしよう。

k個のうち0\le j\le k個がバッチ1由来である場合を考えると、まずこれが起こる場合の数が\binom{C_1}{j}\binom{Y}{k-j}\binom{X}{K+1-k}通り。そのうちj/kが当たりなので、これを掛けて足し合わせたい。Wolfram|Alphaに投げるとうまいこと閉じた式にしてくれて、C_1\binom{C_1+Y-1}{k-1}\binom{X}{K+1-k}/kになった。kは全探索できるので、これで解けている。

しばらくABCのコードゴルフの続きをした後、昼前から日記を書いていた。金曜日のCodechefの部分に差し掛かって、UNFRIENDLYを通した自分の解法の正当性が証明できず、布団に逃げ込んだ。午後3時就寝。

09/25(日)

午後8時半起床。午後9時から久しぶりのTOKI、TROC #27。

https://tlx.toki.id/contests/troc-27/

Aは列Aに偶数が含まれているか調べる。Bはそれより大きい最小の2^k-1までインクリメントし、一気に消すのが最適。

Cはインドネシア一流の謎パズルで、(N-2)(M-1)+M+1とそのNとMを入れ替えたものの\maxを提出して1WA。4\times 4を考えて右上と左下を結ぶ線の上以外を暗くすることが可能だと気付いた。答えはNM-\max(N,M)。

Dはやたら合わせるのに時間がかかった。F=1の場合は自明。F=2の場合、「先頭が1で隣接項の差が2以下の長さiの順列」をi\le Nに対して前計算しておけば、適当に足し合わせることで答えになる。この前計算は挿入dpを考えるのが正解だったらしい。隣り合う2項を交換するか決めるだけでは1,3,5,7,6,4,2のような並び方を生成できない。

EはM\le 2という制約に気づかず1WA。しばらく実験して、N以下で最大の2^k-1と、2^k\le Nならそれも聞くことで特定できることに気づいた。前者によって1\le s\le 2^k-1を、後者によって2^k\le s\le Nを区別できている。

Fは面白い。好きな辺を選んでそこまで往復することでウォークの美しさを\pm 2W_iすることが可能。これでユークリッドの互除法を行えるため、g=\gcd(W_1,W_2,\dots,W_{N-1})として2gで割ったあまりを求められる。この時点で、とりあえず根を一つ決めて各頂点までのパスの重み\bmod{2g}を求めておいた。それをd_uとすればf(x,y)\equiv d_x+d_y\pmod{2g}である。{\rm LCA}(x,y)より上のキャンセルも\bmod{2g}に吸収される。

d_x+d_yを0、(0,2g)、[2g,4g)に分類するのは難しいな、と思っていたが、冷静になると\forall i.\;g\mid W_iなのだから、d_uは0またはgだった。これなら0+0を2gに置き換えるだけでよいので簡単。

Gも面白かった。実験するとN回コピー後に値Mは\binom{N-1}{M-1}個あることがわかる。この値は\binom{N-2}{M-1}+\binom{N-2}{M-2}と等しく、先頭から\binom{N-2}{M-1}個は1回コピーをキャンセルしてもMで、残りはM-1になるということがわかる。このことから、NをデクリメントしながらDとMを丁寧に更新するO(N)の方針が得られる。ただしcombinationは適切に差分更新を行う。

Nがとんでもなく大きいと困る。しかしM=3ですでに\binom{N-1}{M-1}=(N-1)(N-2)/2からN\approx\sqrt Dとなるため、M\ge 3では十分間に合いそう。よってM=1,2のケースさえ別に判定すればよく、この部分は実験で容易に解ける。

Hは解けず、7完8位でレートが2732→2762(+30)。highest。

10分のインターバルで午後11時半からCF #823 div.2。

Dashboard - Codeforces Round #823 (Div. 2) - Codeforces

Aはよい。Bからすでに難しかった。xでソートしx_k\le x_0\le x_{k+1}となる場合を考えるのを繰り返す。t_i+|x_i-x_0|はi\le kかどうかによって絶対値記号を外せるので、それぞれ外す。x_0の項を除いて適切に\minや\maxを求めるのは、あらかじめ左右から累積的に計算しておける。これを使うと最小化する値が\max(x_0-L,R-x_0)のような形になり、二つの値が等しい場合に最小値を取る。

Cは簡単。後ろから見て累積\minとならない位置の文字は動かすべきで、それもちょうど1回動かすとしてよい。するとどんな数字に変化するかわかり、残した累積\minの広義単調増加を壊さないような位置に挿入するのが最適になる。

Dは信じられないほど難しかった。ずっと実験で文字がどう入れ替わるか観察していたが全く光明が見えない。ふと不変量について全く考えていないことに気づき、その気持ちになって眺めると、s_1のi文字目とs_2の後ろからi文字目がペアとなり、必ず異なる文字列に入ることに気づいた。ペアの列を並び替えたり、要素の順番を逆にするのは自由にできると信じる。

もし文字aとbのペアが二つあれば、文字列における対称の位置、例えば先頭と末尾に置くことでそのインデックスを揃えることができる。同じ文字のペアが奇数個しかない場合、それがaとaのような形をしていれば文字列の中央に置ける。逆に、異なる文字のペアだったり、文字列の中央が埋まっていたりするともうダメ。この判定を書いたら通った。1時間かかったらしい。

次により多く解かれていたFを考え、bitDPをしても見るべき状態数が少ないから間に合いそうだと思ったが、とりあえず書いたらサンプルが合わず、そのままコンテスト終了。4完。かなりの大失敗だった。Bはx_0の位置にかまわず|x_i-x_0|=\max(x_i-x_0,x_0-x_i)として展開してしまう方法が賢い。コンテスト中のようにLとRを使った形に整理できる部分は同じながら、x_0の範囲が制限されておらずここから即座に答えが出る。

コンテスト後にFをupsolveした。まずbitDPの説明から。インデックスiを見ているとき、v=p_{q_i}としてここに置ける値の範囲を考えてみる。まず自分より左にi-1個の値があって、これらはすべてv+k以下である必要がある。そのような値はv自身を除いてv+k-1個しか存在しないため、v+k-1\ge i-1よりv\ge i-kが得られる。同様のことが右に対しても考えられて、v\le i+kもわかる。

つまり値をこれまで置いたかどうか記録しておかなければならない情報が2k+1個分、v=i+kはインデックスiで初めて置けるようになった値なので、正確には2k個記録しておけば十分で、bitで表現できる。

端を除けば2k個のうちちょうどk個が埋まった状態しか考えなくてよい。k=8で計算してみると\binom{16}{8}=12870通りだった。これで出してもTLEしてしまうが、ここで「また値vを置いていないのにv+kより大きな値が置かれている」という状態をちゃんと無視することで十分高速になった。値vを置くときにダメだと気付くのでは遅く、状態数が多くなりすぎるようだ。そのほか、転倒数をあらかじめi-k\le v\le i+kに対して計算しておくなどする高速化を入れて提出すると、1400msで通った。

TCB51の結果が出ていた。理論値は3人いたが時間差で優勝。10問目を非想定で押し通しているとはいえ、2位と20分以上差をつけていて気分がいい。

来週水曜日にたいぺーとホスフィンと3人で家で飲む予定。いつもはドンキでお酒を購入するのだが、今回はAmazonで見繕ってあらかじめいくつか購入しておくことになっていた。ギフト券残高の消化。これの希望が出そろっていたので、しばらく時間を使ってそれが本当に最安値か調べたりした後注文した。

午前4時から午前11時まで月曜日のインターン先勉強会のための発表スライドを作っていた。内容は考えてあったので今日一日で何とか完成。

途中でRating Historyを確認したらAtCoderとCodeforcesのAC数が両方ほぼキリ番だった。

生協に行って菓子パンやラノベを購入し、正午就寝。