06/12(月)

午後3時過ぎ起床。購買に行ってパン類を買い込んだ。

午後4時からインターン先定例会での発表資料を作り始めた。先週の1on1で次に取り組むタスクが決まったため、それに関して一度まとめておく。自分の理解を試すという目的と、定例会で全然話題に上がらない部署の話だから知らない人もいるんじゃないかと思ってのことだった。

半から定例会。以前ダメだったことに再チャレンジしますと言ったら少し反応をいただけた。いい気になったが、実際のところまだ手を動かしてすらいないことに気づいて冷や汗。相変わらず失敗に終わる可能性もあるのだから、喜んだりするのは早すぎた。

勉強会は区間推定の話。ある状態が起こる確率を推定するとき、 $n$ 回調べて確率 $p$ だったなら $p\pm 1.96\times\sqrt{\frac{p(1-p)}n}$ の区間に真の値がある確率が95%となる、というやつ。ただし $n$ は十分大きいものとする。

真の値が式に現れないのは実用上当然の要請だがすごい結果だな～と思って調べたところ、ルートの中身は本来真の値が来るはずで、それを $p$ で近似しているだけだった。そう簡単にはいかないか。

その後は週記を書きつつハーメルンを読み進めていた。「スペちゃんとチート持ち転生者の幼馴染」を読了。昨日寝落ちする前に読んでいたもの。トレーナーのチートは描写しただけという感じで、担当ウマ娘が信じられないくらい強いという雰囲気はなかったのに、いざレースになると写真判定もなくちゃんと勝ち切ってくる。なんだかアンバランスに感じた。

syosetu.org

午後10時前に投稿。シャワーを浴びた後しばらく論文を読もうとしたところで寝てしまったようで、起きたらコンテスト15分前だった。危ない。準備を整えて午後11時半からECR150に出た。

Dashboard - Educational Codeforces Round 150 (Rated for Div. 2) - Codeforces

Aは初手で $n-2$ 個の1をまとめればAlice勝ちだろうと思い、実際手で実験して $n\ge 5$ なら正しいことを確認した。逆に $n\le 4$ は全部の分岐でBobが勝つ。

Bは $a_i\gt a_{i+1}$ となるような $i$ （ただし $a_{k+1}=a_1$ ）が1個以下であることが条件。末尾と先頭の比較以外の結果を更新しながら判定した。

Cは変える候補が少ないだろうと考えて考察してみたがよくわからない。結局全探索した。変える位置と文字を固定したとき、それより右側は影響なし、左側は「まだ負と決まっていない数字」を数えておけば求まる。

Dはbeautifulである場合 $l$ の昇順にソートして2個ずつペアにするもののみがvalid。そこで入力された区間も同様にソートし、ペアを作りながらdpした。 $[l_i,r_i]$ と $[l_j,r_j]$ （ただし $l_i\le l_j$ ）をペアにするならまず $l_j\le r_i$ が必要。そして次にペアに使える区間 $[l,r]$ は $\max(r_i,r_j)\lt l$ を満たす。

$i$ を決めるごとに $\max(r_i,r_j)$ としてありうる最小値を求め、適切なインデックスまで飛ばして遷移することで、ちゃんと交差しない区間を選べる。 $O(n^2)$ 。このあたりでいろいろ勘違いをしたり実装ミスを重ねたりして3WAしてしまった。

Eは横一列に並んだマスが多い場所に貪欲に埋めていくのが最適。何マス並んだ箇所がいくつあるかという情報は最大長方形と同様の方法で求められる。

Fはまず人口がそれぞれ $A,B,C,D$ 人だった場合の $m+k$ を考えた。human一人当たりの幸福度が $A-1-B$ であることなどを利用すると、humanとorcの幸福度の総和が $A(A-1-B)+B(B-1-A)=(A-B)^2-(A+B)$ と表せる。elfとdwarfでも同様の計算をし、足し合わせることで $m+k=(A-B)^2+(C-D)^2$ が得られる。

これにより、問題は $(a-b,c-d)$ というベクトルをいくつか足し合わせて原点から最も離れたときの距離を求めるということに帰着された。なんだか見覚えがある。確かベクトルを一つ決めてその方向に向かうベクトルだけ集めるのが良かったはず……と思ったところで、その手法を使った最短コードを思い出し、手元にクロールしてある一覧に検索をかけることでABC139Fに辿り着いた。

F - Engines

この問題は $N\le 100$ だが解説には $O(N\log N)$ の解法まで乗っている。自分のコードはよくわからないことをしていたので、その場で実装することにした。偏角の差が最大180度未満になるよう、境界に気を遣いながら尺取り法。

$l$ をインクリメントしつつ $r$ を適切に伸ばす方法だとダメで、 $l$ と $r$ のどちらかをインクリメントする度に答えを計算する必要があるらしい。サンプルで落ちてくれて助かった。うっかり一周してしまうケースは無理に取り除かなくても同じベクトルを複数回足さないように気を付けさえすればよい。一周してしまうならすべて偏角180度未満の区間に納まっているからだ。よくない。水曜日の日記を参照のこと。

出したら一発で通ってラッキー。全完7位となった。Cはdpで解けるようだ。言われてみればという感じで全然思いつけなかった。また変える文字は同じ文字の中で最も左あるいは右にあるものに限られるらしい。これは考えはしたもののどう示してよいかわからず捨てた方針だった。

動画を投稿した。前回の動画に音声が小さいという指摘をいただき、自分でも自覚するところではあったので、今回はOBSのほうでマイク音量を300%にまで上げてみた。上げすぎかと思ったがいざ撮ってみるとなかなかいい感じになった、はず。これからも同様の設定で撮るつもり。

www.youtube.com

それから朝まで日記を書いたりハーメルンを読んだりしていた。午前8時前には布団に移動しハーメルンに専念。ブラウザの閲覧履歴を見た感じ、それから2時間くらいして寝落ちしたらしい。

06/13(火)

目覚ましもかけていないのに午後4時前に一度目を覚ました。そこから大学に向かえばサークル活動にちょうどいいくらいだったが、眠気に負けて二度寝。次は午後7時に起きて、それからずっとハーメルンを読んでいた。

日付が変わる少し前に「ヒエヒエの実を食べた少女の話」の1年弱追っていなかった更新分を読み終えた。やはり面白い。原作が開始してオリ主の描写が激減したことについては30話ちょっとを一気読みすることで気にならなくなり、たまにあるシーンを貴重さを噛みしめつつ味わうことができた。逆に言えば更新を放置してしまった原因も主にそこにあるのだが。

syosetu.org

また3時間ほど寝ていた。起きてハーメルンの「Miss.グリフィンドール」を読了。「ハリー・ポッターと野望の少女」を思い出す天才で最強の女主人公が良かった。

syosetu.org

しばらくセミナー向けに演習問題を解いたり教科書を読み進めたりした後、学食の開店を待ちながらハーメルンを読んでいた。うっかりハーメルンに熱中しすぎて気づいたら正午が近づいてきており、人混みを避けるため向かう時間をさらに遅らせることにした。

午後2時前、閉店ギリギリで滑り込み食事。その後散髪して帰宅した。また教科書を読み進めた後午後4時過ぎに就寝。

06/14(水)

午後8時半に目を覚ました。

OpenCupのSlackで話が回ってきたが、今年もMulti-Universities Campがあるらしい。Universal Cupとの兼ね合いか月・土ではなく月・金になったようで、それぞれインターン先定例会とセミナーに被ってしまった。どの日も最初3時間ちょっとしか参加できなさそうで残念。

またしばらくハーメルンを読み続けていたところ、日付が変わるくらいの頃に月曜日のECR150FがHackされたと通知が来た。Hack一覧を見てみると他にも落ちている人が大量にいる。ジャッジミスを疑ったがケースを確認すると単純に自分が悪かった。

やはり尺取り法で一周してしまうのは良くなかったらしい。すべて偏角180度未満の区間に納まる場合でも、別の180度区間を選んで一部だけ取り出すほうが良い場合は当然ある。どうやって一周しないようにするかは悩んだが、列を倍にして解いていたのをやめ、「そのまま解く」→「点を180度回転させてもう一度解く」とした。こうすると尺取り法の区間が偏角ソートの境を超えないようになる。

せっかく起きたのでやるべきこと、ICPCのチーム登録を行った。今年サークルから出る4チームのコーチをホスフィンと半分ずつ担当することになっている。ICPCサイトの個人情報の扱いがガバガバでびっくりした。

ICPCのチーム登録、メールアドレスのprefixをタイプしたらそれにマッチするアカウントがドバーッと出てきて個人情報のあまりの扱いに泣きながらひっくり返ってしまった
— こたつがめ (@kotatsugame_t) 2023年6月14日

またハーメルンに戻った。朝になって「【完】これは圧倒的美貌で凱旋門賞馬になる俺の話」を読了。ウマ娘の二次創作を探して見つけた作品。リアル馬がメインの話は別に求めていなかったな、と思いつつ読んでいたが、ウマ娘とか関係なく競馬の話として非常に面白かった。馬と人間の意思疎通もそこそこうまくいっている。その分たまに通じていないシーンは苦しかった。

syosetu.org

3時間ほどインターン関連の作業をした後、購買で昼食や菓子パンを買ってきた。食後は布団に入ってハーメルン。正午くらいに寝落ちしたらしい。

06/15(木)

午後5時起床。1on1の開始時間である。2分ほど遅刻して会議に参加した。

昨日の作業はコーディング少しとドキュメント整備だった。それらの報告後にしばらくコードを動かす作業をして、来週分のタスクを決めて解散。1時間半ほどで終わった。

ゲーセンに向かう。今日からグッズプレゼントキャンペーンで、物理的なグッズには興味がないがゲームで使えるキャラクターはコンプリートしたい。直近では07/05までに30クレ分のポイント、以降08/30まで2週間ごとに同じ量が必要となる。早め早めに貯めておけるとよい。

今日は新曲を埋めていた。「WE'RE BACK!!」をAJ。譜面動画ではラストの5鍵が難しそうに見えたが、ちゃんと譜面を覚えたら押せた。癖がつく前に揃ってよかった。

WE'RE BACK!! AJ pic.twitter.com/qLQZg1LNww
— こたつがめ (@kotatsugame_t) 2023年6月15日

4台しかないスーパーノバにいたが4人マッチが始まったので空気を読んで退店。午後11時前なのでこれから仙台セガに移ってもほとんど遊べない。そこでタイステの仙台クリスロード店に行ってみた。

ここは台数が少なく、今日確認したところ新筐体と旧筐体がそれぞれ1台ずつだった。しかし新規ゲームを開始できる時間が23時45分と先ほど挙げた2店舗より遅い。今日もこの時間から4クレプレイできた。最後のプレイでは14初理論値をラスト1ノーツで逃してしまい残念。

こいつ緊張に弱すぎるだろ pic.twitter.com/NEWKYIAxvJ
— こたつがめ (@kotatsugame_t) 2023年6月15日

油そばを食べて帰宅。それから6時間ほど一心不乱にハーメルンを読んでいた。「漆黒の鋼鉄」を読了。やはり主人公最強は最高。故障しないというチートを強調するためか肉体的なアクシデントが多くてヒヤヒヤしっぱなしだが、それがまた楽しいし最終的にはすべてなぎ倒して勝ち続けてくれる。そういう意味では安心して読めるとも言えるだろう。

syosetu.org

シャワーを浴びてから先週用意したセミナー用の原稿を読み返しておいた。午前8時前には布団に入ったがその後またハーメルンに熱中。睡眠時間を4時間ほど削り取られて正午くらいに寝落ちした。

06/16(金)

午後4時過ぎに目を覚ました。ここから二度寝すると寝坊するかもしれないと思いつつ、身を起こすほどの気力もなかったし昨日読んでいたハーメルンが面白すぎたので、布団に転がってしばらく先を読み進めていた。

ギリギリになって大学に向かったがセミナーには5分遅刻。今日は発表予定者が自分しかいなかったはず、どうなっているだろうか……と教室に入ったら同級生が演習問題の発表をしていた。ただやはり急な発表で整理しきれていなかったらしく、途中で終了。

実はその演習問題は自分が先生と一対一で話した際に取り上げたもので、証明そのものに加え周辺の知識も少しあるため彼の方針が上手くいかないことがわかる。ただ上手くいかない反例がパッと構成できなくてむっつり黙り込んでいるだけになってしまった。こういうケースで何をコメントしたら良いのかわからない。

それから自分の発表。今日は贅沢に3時間使い、Diestel 6.6章を最初から最後まで話した。Thm 6.6.1の証明は構築なので一度通して読めば理解できるが、逆に通して読むまでは理解できない。証明の前半で構築している謎の列が何の意味を成すのかわからないからだ。原稿を見せた先生からそのあたりをフォローするようアドバイスを受けたため少し言葉を追加したものの、不十分だったようだ。こういう証明の細かいところを詰めるのは各々でできるのだからお気持ちを伝えるのを重視すべきなのだろう。

帰宅して午後9時20分からyukicoder 393に出た。

yukicoder contest 393 - yukicoder

Aはスペルに気を付けて実装。Bは $NK(K-1)/K^N$ である。 $N\ge 3$ である点が優しさ。

Cは $\int_{-R}^{l_i}\sqrt{R^2-y^2}dy=\frac{i\times \pi R^2}{K+1}$ となるように決めることになる。定積分が計算できるためその値を見ながら二分探索することで求まる。 $l$ たちを独立に決めているので誤差も十分少ない、はず。実際通った。

Dは一般マッチングが頭を過ったが制約が大きい。冷静になると $(x,y)$ でソートして順に組にするのがvalidであり、明らかに最大。Eは二分探索＋dijkstra。完全グラフなので毎回確定させる頂点を線形探索する $O(N^2)$ の実装を使った。Fは各頂点についてそこから同じ向きに2個以上の頂点があるかを判定。これは座標の差を取って $\gcd$ で正規化して重複を見ればよい。

Gは訪れる街を固定して扉の行き先を数え上げる。例えばそれが $i\rightarrow j\rightarrow k\rightarrow l$ だとすると、もともと $(N-1)^{A_{\mathrm{all}}}$ 通りあったものに $1-\frac{(N-2)^{A_i}}{(N-1)^{A_i}}$ などを掛けたものが場合の数となる。これの $(i,j,k,l)$ 全通りに対する和を求めるとうまく因数分解ができて、季節ごとに独立に求めた和の積として表せるようになった。

35分弱で全完。これは全体で2番目ではあるが、問題ごとの順位がまんべんなく微妙なためスコアは低く、最終的に9位となった。

以降10時間ほどハーメルンに没頭。「「ウマソウルってうるさいよね」「えっ」「えっ」」を読了した。

syosetu.org

これも主人公最強もの。二重人格である主人公の「人格がひとつしかないというのは構造的欠陥が過ぎる」という考え方がいい感じに人間離れしていて良かった。昨日読んだ「漆黒の鋼鉄」と違い、こちらは主人公を構成する何もかもがチート的。名前の「テンプレオリシュ」に違わずテンプレ的な強さが爽快だし、設定やストーリーもしっかりしていて、総じて非常に面白かった。

シャワーを浴びて日記を書き、また1時間ほどハーメルンを読んで午前11時就寝。明日のUniversal Cupはチームメイトがゆるふわオンサイトに参加するため午後8時からのウィンドウで参加することになっている。

06/17(土)

午後6時半起床。布団に転がったまま「前前世社畜、前世鬼殺隊士、今世ウマ娘」を読了。鬼滅の刃について何も知らないので、それメインの二次創作ならともかく設定を持ち込まれるだけだと何もわからないだろうなと思ってこれまで避けていた。実際よくわからず残念。いや主人公があまり好きになれなかったので特に残念でもないな……。

syosetu.org

準備して午後8時からUniversal Cup 20回目に出た。今日はIndiaセット。

The 1st Universal Cup. Stage 20: India - Dashboard - Contest - QOJ.ac

この時間帯に参加する場合の例にもれず、今日も午後9時から一時離脱してABC306に出た。

Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306） - AtCoder

Aはsedでs/./&&/g。Bはdc。Cは $A$ を先頭から見て、出現回数が2回になった数を順に出力していけばよい。Dはお腹を壊したかどうかを持つdp。Eは上位 $K$ 個とそれ以外をmultisetで持って更新ごとに調整する。

Fはインデックスのことを自分以下の要素の数え上げとして捉える。すると $f(S_i,S_j)$ における $x\in S_i$ の寄与は $\#\{y\in S_i\mid y\le x\}+\#\{y\in S_j\mid y\lt x\}$ となり、後者の $j$ を渡る和がBITで一気に計算できる。前者は単なる算数だがそもそも存在を忘れていてサンプルを合わせるのに手間取った。

Gは頂点 $1$ を含むすべてのwalkについて長さを求めたとき、その $\gcd$ が $10^{10^{100}}$ の約数であればよい。列挙は明らかに不可能なので、知りたいのが $\gcd$ だけであることを利用して調べる対象を減らそうとした。

最初は全ての辺についてそれを含む最短のwalkだけ使ってみたがWA。その後、頂点 $u$ に距離 $x,y,z$ でたどり着くパスがあった場合 $d:=\min(x,y,z)$ と $\gcd(x-d,y-d,z-d)$ を持ってみるということをしていた。しかしずっとWAが取れなかった。

実は $\gcd$ を計算する部分が問題だったのではなくYesとNoの判定がまずかったらしい。素因数が2と5しかないことをチェックしなければならないのに、 $\gcd\mid 10$ かどうかを見ていた。これを修正して提出したのが午後10時10分時点で、それからコンテスト終了までずっとWJ状態だったが何とか通ってくれた。

$\gcd$ の計算については最初のもので問題なかったようだ。解説の方法を含んでいる。辺 $u\rightarrow v$ について考えるとき、解説は $|d_u+1-d_v|$ を見ており、自分の解法は $v$ から $1$ への最短距離を $x$ として $\gcd(d_v+x,d_u+1+x)=\gcd(d_v+x,d_u+1-d_v)$ を見ているから。

7完66位。コードゴルフについては、AとBは最初のACコードがそのまま最短になっていた。CはPerlコードをちょっと縮めてみたがAWKに大敗。以降はUniversal Cupに専念したため手付かずである。

書く：UC

午前2時に感想戦を終えた後すぐDMOJのコンテストに出た。来週火曜日終了のためここにはリンクだけ張っておく。

DMOPC '22 June Contest - DMOJ: Modern Online Judge

3時間のコンテストなので午前5時過ぎに終了。それからまたしてもハーメルンを読んでいた。「【ヒト息子ソウル】原作・競馬ミリしらなので安価で進むしかないウマ娘生【転生】」を読了。心象世界の描写や思わせぶりで尻切れとんぼな発言が多く、内容をうまく汲み取れなかった。そもそも安価で進む作品が自分の肌に合わないのかもしれない。

syosetu.org

少し日記を書いて午前8時頃に布団へ。2時間ほどハーメルンを読んでから寝た。

06/18(日)

午後1時半起床。睡眠時間が足りないまま今日は3h+2h+2h+2hの日。まず午後2時から3時間、模擬国内予選の内部コンテストに出ていた。

直後の午後5時からCF #879 div.2に出た。

Dashboard - Codeforces Round 879 (Div. 2) - Codeforces

Aは $-1$ の個数が半分以下で偶数というのが条件。そうなるように操作で減らす。増やすことは考えなくてよい。Bは何もわからなかったので桁dpした。 $L\le X,Y\le R$ で四つの条件があるため、2⁴状態を持つ。

Cは二人ゲームに見えてBobの行動が最終的なターン数の多少に関係しない。常に $T$ をreverseし続けるとしてよく、Bobが行動した回数の偶奇を固定することで文字列が一致するまでに変更する必要のある文字数を数えられる。あとは算数でターン数が出るので、偶奇を両方試す。

Dは「人 $i$ の手の高さ」引く「人 $j$ の手の高さ」を最大化することを考えてみるとトピック $[l_i,r_i]$ を全部聞くのが最適だとわかる。このとき差は $[l_i,r_i]$ と $[l_j,r_j]$ の共通部分のサイズ $\min(r_i,r_j)-\max(l_i,l_j)+1$ が小さいほど大きくなる。

区間を $l$ でソートすると、 $j\lt i$ なら $l_j\le l_i$ より共通部分のサイズが $\min(r_i,r_j)-l_i+1$ となる。これは $r$ について左から累積MINを取っておくことで求まる。 $i\lt j$ はもうちょっと面倒だがほぼ同様。

Eは区間の数が $n^2$ 個程度しかないので大きなLCMを無視してよい。区間の右端を固定して左端を左に動かしていくと、LCMは変化するなら倍以上になるから、変化する点を $O(\log n)$ 個しか見ずに済むということになる。この点を列挙したい。

Sparse Tableを使っても、結局1回はその場でLCMを求めるため $\log$ が付いてしまう。これで二分探索をすると1点見つけるのに $\log$ が二つ付くためさすがに間に合わないだろう。そこで、左に見ていった時の累積LCMの変化点を管理しながら右端をインクリメントしていくことにした。管理する点の数は常に $O(\log n)$ 個であり、更新は各要素につき1回ずつLCMを求めるだけで済む。従って全体で $\log$ 二つになった。

Fは $i\rightarrow p_i$ という辺を張ったグラフのサイクルに沿って要素を入れ替え続けることで達成可能。この時のキャリッジリターンの回数は $i\gt p_i$ なる $i$ の個数に等しい。そしてこれは下界である。なぜなら、数を自分より前に持っていくためにはバッファーに入れてキャリッジリターンするしかないからである。

答えはあらかじめ $p$ 、 $\mathrm{rev}(p)$ のすべてのrotate状態について求めた。元の状態におけるインデックス $i$ が答えに寄与するときのrotate幅が高々二つの区間で表されるため、imos法で該当箇所をインクリメントしておけばよい。

全完して16位。Bは先頭から見て初めて $L$ と $R$ が食い違う箇所を見つけ、それより後ろを全部9と全部0で埋めると解けるらしい。確かに $L\le X,Y\le R$ を満たすし、桁の差の和をこれ以上大きくしようとすれば全部0や9で埋めたところより上の桁を弄る必要があって範囲からはみ出てしまうとわかる。

www.youtube.com

ICPCチーム登録の完了メールなどが届いていたのでメンバーに配布した。そのほか食事などをして時間を過ごし、午後9時からARC162に出た。

AtCoder Regular Contest 162 - AtCoder

Aは人 $i$ が候補になるためには $i\lt j$ なるすべての $j$ について $P_i\lt P_j$ であることが必要。そして実は十分でもある。往路のタイムに思いっきり差を付けると往復のタイムをかなり好きに並べられる。 $O(N^2)$ が許されていて不安になったが出したら通った。度胸試し。

Bは2手で1回swap操作を行えると嬉しいがうまくいかなかった。微妙にずれてしまう。このずれは転倒数の偶奇に関するものではないかと思い調べたところ、操作でそれが変わらないことが分かった。

またそれとは別に、先頭から要素を並べていく方針も考えてみた。並べたい要素が末尾になければ1手で持ってくることができる。末尾にあっても3要素ぶん猶予があれば2手でOK。猶予がない場合、つまり最後の2要素が $N,N-1$ と並んでしまったときは、先ほどの考察がどんぴしゃりで最初から転倒数が奇数ということになって不可能だった。

CはAliceが高々1手操作して勝てないならBobが勝つ。Aliceが操作した場所に応じてBobが適切な頂点に $K$ を置くと、せっかく操作した分が台無しになって、1手操作しても勝てない状態が延々続くからだ。その「適切な頂点」については少し勘違いしていたが、結論は正しかった。

Dは頂点 $v$ が良い頂点となるような良い木を数え上げる。 $v=1$ あるいは $d_v=0$ のときは単に良い木の数え上げとなり、これはケイリーの公式で行える。根以外の次数を1増やしていったん無向木として数え上げた後、根から葉の方向に辺を向き付けると良い木になる。

それ以外の $v$ については、まず $v$ 以下の部分木を作ったあと、それを出次数0の頂点に圧縮して再度良い木を数え上げるとよい。 $v$ 以下の部分木に含まれる頂点の集合は「頂点数」と「次数の和」を状態としたdpで数え上げられる。 $v$ を降順に計算すれば全体で $O(N^3)$ 。

木の数え上げは完全に独立には行えない。分子に来る頂点数の階乗はよいが、分母が選んだ頂点集合に依るから。しかし実は常に同じ値で、根と $v$ 以外の次数を1増やした上での $\prod(d-1)!$ となる。最初はdpと一緒に考えようとしていた。

Eは $B$ における個数が多い値から置いていくとうまくいく。そうすると置ける値の集合も、それを置ける位置も単調に増加するから、それぞれいくつ使ったかの情報さえ持てば計算可能。よってその2次元dpを行った。

置く個数を決め、これまで置いた値の種類数、今から置く値の種類数、これまでいくつ置いたかのループで更新していく。 $O(N^4)$ に見えるが一か所は調和級数になっており $O(N^3\log N)$ 。手元で最大ケース2.5secだったので出したら通った。

Fは条件が「1が左上と右下にある場合右上と左下にもなければならない」みたいな感じになる。なので基本的にはグリッドの格子点みたいに1が配置され、そのような格子が左下から右上にかけて並ぶはず。ところがその格子が重なる部分をうまく扱えなかった。結果は5完15位。

www.youtube.com

午後11時半からCF #880 div.1に出た。

Dashboard - Codeforces Round 880 (Div. 1) - Codeforces

Aは制約をよく読むと $a$ が全探索できるとわかる。桁数が同じ場合辞書順と数の大小は一致するので、あとは小さいほうから試せばよい。

Bは非常に難しく、また面倒で辛かった。まず選んだ数字を $s$ と決めたときに勝てるtarget $t$ を数えてみる。数字 $a$ のチケットを持っている人より当たりが優先されるためには $|s-t|\lt|a-t|$ が必要。これは $s$ と $t$ の中点 $(s+a)/2$ より $t$ が $s$ 側にあることと同じである。

$n$ 個の $a$ について $s$ との間の中点を考えたとき、そのうち $s$ に近い値から大小それぞれ $k$ 個目にあるものが $s$ が勝てるかどうかの境目となる。中点を取っているだけなので、 $s$ の左右でそれぞれ $k$ 個目に近い $a$ が求まれば境目も求まり、 $t$ を数えられる。

注意点として、 $a=s$ については左右どちらでもカウントされる。つまり $s$ がどれかの $a$ と一致する場合は計算が少し面倒。これは $n$ 通り計算することにして、それ以外を考えてみる。

$s$ から大小 $k$ 個目に近い $a$ をそれぞれ $a_l$ 、 $a_r$ とおくと、targetが存在する区間はだいたい $(s+a_l)/2$ から $(s+a_r)/2$ まで。幅が $(a_r-a_l)/2$ なので整数もそのくらいあると考えられ、targetの数が $a$ の偶奇によって多少ブレるだけだと分かった。なので $s=a_l+1,a_l+2$ を試しておけばよいことになる。

$a_l$ や $a_r$ が存在しない場合は逆側に寄せるべき。いずれにしても $s=a-2,a-1,a,a+1,a+2$ の $5n$ 通りについて答えを求めれば十分だと分かった。あとは $n\lt k$ の場合に備え $s=0$ も計算することにして、試すべき値が $O(n)$ 個になったので $a_l$ 、 $a_r$ を管理しながら昇順に調べていくことで答えがわかる。

最初の提出は算数のミスだったり調べる範囲の不足でWAだった。愚直を書いて慎重にデバッグし2回目の提出でAC。途中で解いている人が全然いないのを確認していたのでかなりじっくり取り組んだ。

Cも難しかった。区間の数が $2^{2k+1}$ 個ありXORの種類数は $2^{2k}$ 通りなので、必ず答えが存在する。

まず $g$ に0が二つ以上ある場合、それが答えになる。そうでない場合は高々1個の0を削除して考えてもよい。答えの区間に0が含まれる場合、それを削除してもXORは変わらないからだ。もし0のみからなる区間だった場合は、もう片方の区間が「長さ2以上」「XORが0」を満たし、これを二つに分割したものが必ず条件を満たす。

次に、見つける区間は異なってさえいればdisjointでなくてもよい。区間の端点四つをソートして順にペアにしたものもまたXORが等しい区間になるから。もしどちらかの区間の幅が0になった場合は、先ほどと同様の議論でもう一方の区間を分割したものが答えになる。

以降は累積XORを考える。今 $g$ は長さ $2^{k+1}-1$ 以上なので累積XORの値は $2^{k+1}$ 個あり、下 $k$ bitで分類すると平均的には2個ずつに分かれて下 $k$ bitが等しいペアを $2^k$ 個作ることができる。偏りがあってもペアを作れる個数は増える一方。

ペアを全部見ていく。もし上 $k$ bitも等しければ、それはXORが0の区間を表すから答えになる。そうでない場合は上 $k$ bitのXORに対してペアを記録しておく。 $2^k$ 個以上のペアから $2^k-1$ 通りの値が出てくるため、鳩ノ巣原理により必ず同じXORを持つ二つのペアが見つかる。これはXORが等しい区間二つのことであるから、答え。

Dを読んだら有向グラフのループの $\gcd$ に関する問題でびっくりした。ABC-Gで出たばかり。しかし細部を詰め切る時間は残されていなかった。3完66位で2888→2870(-18)。

www.youtube.com

Cは乱択で通した人が多そうだ。できるんじゃないかと疑いはしたものの信じきれなかった。区間のXORを乱数としたら、ランダムに引いて衝突するまでの試行回数は出てくる数の種類数の平方根オーダーになるらしい。これを誕生日攻撃という。ハッシュに関してもそうだが、乱択に関する理論の知識が足りていないのをたまに実感させられる。

誕生日攻撃 - Wikipedia

Dをupsolveした。強連結成分ごとに解く。長さ $2K$ のclosed walkを取りたい。サイクルの長さの $\gcd$ を使う議論は、取ろうとしているclosed walkの長さが $n^3$ 以上ならOKだというのをABCの後TLで目にした記憶がある。よって今回も同様に $\gcd=:g$ を計算し判定した。

その後答えを数える。まず頂点をどこかからの距離 $\bmod g$ で分類する。もし長さ $K$ のclosed walkが存在するなら、同じグループに入る頂点のペアはvalidである。サンプル1で言えば $6\leftrightarrow 7$ の強連結成分がこの処理に該当する。そうでない場合 $g$ は偶数で、距離 $\bmod g$ の差が $g/2$ であるようなペアがvalidとなる。サンプル1のもう一つの強連結成分がこれである。

今日出たコンテストのうち内部コンテスト以外の三つは動画を撮っていたものの、DMOJ参加時のコードや入力サンプルが映り込んでしまった。編集で消せばよいのだが、安全のため来週火曜日のDMOJ終了まで塩漬けにしておくことにした。ちなみに内部コンテストはそもそも別PCから参加したため、痕跡は一切残っていないと自信をもって言える。

06/26追記：動画を投稿したのでリンクを追加した。

しばらく日記を書いていたら強烈な眠気に襲われたため、逆らわず就寝。午前5時半だった。

今週はハーメルンに押しつぶされた1週間だった。ウマ娘の二次創作が面白すぎる。それで睡眠時間を削り取られたまま週末8h+9hはいかにも競プロ頑張ってますという感じで、コンテスト以外で精進していないのを負い目に思っている自分の自己肯定感にプラス補正。実力へのプラス補正はほぼない……。