03/06(月)

午前0時前に目を覚ましたが、布団でハーメルンを読んでいたら2時間くらいでまた眠りにつけた。もし眠れなかったら生活リズムが大変なことになっていたから、危ないところだった。

午前9時起床。夕方までずっと先週の週記を書いていた。日曜日を生活リズムの狭間に消し去ったから残っているのは土曜日の分だけだったのに全く捗らず大変だった。たっぷり寝たうえで朝起きるという経験がほぼないため脳が何か勘違いをしているのか、睡眠時間は足りているはずなのに微妙な眠気が取れない。シャワーを浴びてもそれほど効果はなかった。

午後4時半からインターン先定例会。先週もコードをちょっと書き足しただけ。今週はドキュメントの清書を進める予定。このタスクは先週の広義月曜日の1on1で振られたものだからもう一週間くらい経っているが、まだ手を付けられていない。

勉強会は構築問題について。背景の専門的な話を省くと次のようなものだった： $1\dots n$ の中で「ペアのペア」 $( (a,b),(c,d))$ を考える。ここで $a=b$ または $c=d$ かもしれないが、 $\{a,b\}\cap\{c,d\}=\emptyset$ である。1回のクエリでdisjointな「ペア」の集合を一つ指定し、そこから二つ取り出して作れる「ペアのペア」を全て取得できる。できるだけ少ないクエリでありうる全ての「ペアのペア」を取得せよ。

有限射影平面を用いた非常に綺麗な $O(n^2)$ 解が紹介された。 $n-1$ が素数だとして、位数 $n-1$ の有限射影平面を考え、そこにどの3点も一直線上にないように $n$ 個の点を取り $1\dots n$ と対応付ける。「ペア」を、たとえそれが同じ要素二つの組であっても、2点を結ぶ平面上の直線と思う。そして「ペアのペア」を直線の交点と見なす。

このような直線の存在や交点の存在、また唯一性は有限射影平面の特徴から導かれる。さらに「ペアのペア」となった交点が $n$ 個の点のどれとも一致しないことがその取り方からわかる。

よって逆に、取らなかった点それぞれに対し、そこを通る直線に対応する「ペア」を全部一度に聞けばよい。こうして聞く「ペア」がdisjointであることも点の取り方からわかる。取らなかった点は $(n-1)^2=O(n^2)$ 個あるので、その回数のクエリで全ての「ペアのペア」を取得できたことになる。

午後6時半終了。これからセミナーの準備もしなければならないのに週記が終わっていないため、TUPC部分は参加記として後から投稿することにし、そのほかの辛うじて書き上がった部分を公開した。

セミナー準備も眠気に悩まされ、日付が変わったくらいでとりあえず終了とした。進捗は微妙。用意できたメモは6ページ程度だから2時間持たない可能性がある。先々週行われた前回のセミナーの時に、次の回は1週休みになった分そこそこ進むことを期待しますと言われたのを覚えている。しかし時すでに遅し。

眠気は十分にあるが眠るのをもったいなく感じてしまい参加記を書き始めた。途中で必要になった情報を得ようとTwitter DMからリンクを踏んだら権限エラーで飛べなかった。どうやら全世界的にTwitterのAPIの権限回りが壊れたらしく、t.coドメインの短縮URLを踏むとエラーが返ってくる。リンク文字列が途中まで表示されているように見えても実際は全部短縮URLになっているから、現状どのリンク先にも飛べないというわけ。

{"errors":[{"message":"Your current API plan does not include access to this endpoint, please see https://t.co/2bPk4gfFB9 for more information","code":467}]}
Twitter最高！！！！！！！
— こたつがめ (@kotatsugame_t) 2023年3月6日

午前3時頃に布団に入り、ネット小説を読んでいた。1時間ほどで寝落ち。

03/07(火)

午前9時半起床。昨日せっかくセミナー準備を早々に切り上げたのにその後すぐ眠らなかったのを後悔する程度には眠気がある。時間には余裕があったがその分ゆっくり準備していたので、結局教室に到着するのは5分ほど遅れた。

午前中は同級生の発表。今週から彼もDiestelを読むことになっている。実は春先に早く先に進みたいという理由で1章の後半を飛ばしており、その部分の話題が出てくるたびに少しずつ回収していたのだが、今回彼が担当した部分にも同様の内容があって申し訳ない気持ちになった。

よって今日は1章の該当部分も含めた発表だった。パスの合流を丁寧に観察するためにたくさん場合分けをしていて大変そう。何本ものパスを一気に合流させるから大変なのであって、1本ずつ合流させていけば簡単になるはず。そのことを指摘した。

正午過ぎ、昼食を摂りつつ次回のセミナー日程決め。来週は火曜日にできない代わり別の曜日にセミナーを行うらしい。Muscatキャンプの日程を全力で回避した結果金曜日に決まった。セミナー後すぐオンサイト前泊のため東京に行く予定となるが、何とか頑張りたい。

午後一発目は博士課程の方の発表。数学科なので数式オンリーの説明ではあったが、機械学習の知識があればアンサンブルしているのだと理解できる。ところで結論が「いくつかのモデルをアンサンブルするとそれぞれのモデル単体より精度が良くなった」と言っているように見える。それは……当たり前じゃないだろうか？

発表の終盤から1時間ほど寝ていたらしい。猛省。正確には30分くらいで一度起き、しばらく休憩となったことを聞いてまた寝たのだった。

次は自分の発表。案の定内容が足りず1時間半ほどで終わってしまった。しかし今日終わらせた平面的グラフの平面への埋め込みはグラフ的な話と平面幾何的な話が渾然一体としているから、発表を終えての疲労感はあった。だから内容が薄かったというわけではない、はず。

午後5時半ごろ帰宅。疲れ果ててしばらくTLを眺めることしかできなかったが、一念発起して外出した。

まず仙台駅まで行ってオンサイトのための切符を購入。つけ麺を食べてゲーセンに向かった。チュウニズムデュエルを終わらせたらとっとと帰ろうと思っていたのに、なかなか調子が良くて結局閉店まで遊んでいた。今日の成果は14+のSSS一つと15のSSS二つ。

「Air」ULTIMAは今日初めてのプレイでSSSが出て、2回目でさらに伸びた。3回目ではもう癖がついていてダメダメ。結局「見たまま押す」、といってもぶどう地帯はグシャグシャ擦っているが、ともかくそれしかできていないので、何とかなっているうちにスコアを出すゲームだったらしい。

Air ULTIMA SSS pic.twitter.com/LUPVY1AO3M
— こたつがめ (@kotatsugame_t) 2023年3月7日

「Trrricksters!!」は前回ゲーセンに行った日に「もう一回挑戦したら出そう」と言っていて、その通りになった。すでにほぼ噛み合い待ちだったがかなり上手く揃ったと思う。

71小節後半はなぜか今日上手かった。多分フリック階段の速さがたまたま合っていたのだろう。78小節は黄タップを目印に押す手を変えるとよい。81小節からはどのタイミングでどちらの手を連打するか覚える。88小節は座学しているときに外から内へ擦って通す運指を知った。

Trrricksters!! SSS pic.twitter.com/mLo2KpeQuo
— こたつがめ (@kotatsugame_t) 2023年3月7日

「Strange Love」はラスクレで出た。これも噛み合い待ちだった。プレイする度7小節・26小節からの配置に癖がついて大変。またラストでアタミスを出して鳥寸を踏むことが多くかなり辛かった。

Strange Love SSS pic.twitter.com/sCB6qNbbhG
— こたつがめ (@kotatsugame_t) 2023年3月7日

手元動画を撮っていた。上に挙げた三つ全部撮ってあり、以下のツイートのリプライにまとめられている。鳥寸シーンもツイートしてみた。

Trrricksters!! 3-2 手元 pic.twitter.com/VKHwlKNNgU
— こたつがめ (@kotatsugame_t) 2023年3月7日

Strange Love 鳥寸シリーズ
①全押しで0-2（と1-0）
②最後のタップスライドでアタック
③最後のスライド始点で巻き込み pic.twitter.com/pZOLgqrZ4F
— こたつがめ (@kotatsugame_t) 2023年3月7日

ドンキでパン類を買い込んだ。買ったものをリュックに詰める際、スマホアームをゲーセンに忘れたことに気付いたが、戻ったらすでにシャッターが下りてしまっていた。

日付が変わってから帰宅。上のツイート群を行った後シャワーを浴び、しばらく日記を書いて午前4時過ぎ就寝。

明日からMuscatキャンプだが、参加方法についてのメールがまだ届いていない。いったいどうなるのだろうか。

On March 7th, the day before the bootcamp starts, we will be sending you an email with detailed instructions on how to log in to the bootcamp platform. ←来なァァァい
— こたつがめ (@kotatsugame_t) 2023年3月7日

03/08(水)

午前10時半ごろ目を覚ましたらMuscatキャンプのメールが届いていた。それを確認したらすぐ二度寝すればよかったのに、なぜかカクヨムやハーメルンを読んでしまい眠れなかった。

午後3時前に布団から脱出して準備し、いよいよキャンプ1日目を開始……と思ったら今日は日本由来のセットだった。解いたことのある問題なので参加を取りやめ、日本からキャンプに参加していた3チームで半から代わりのバチャを走った。中国ICPCのGuangzhou大会。

Dashboard - 2022 China Collegiate Programming Contest (CCPC) Guangzhou Onsite - Codeforces

LEHAMCIを解き7完。自分はAMCIを実装した。今日はチームメイト二人にそれぞれ用事があって、ぷらさんは最初と最後、かっつさんは最初しばらくだけの参加となった。

Lはぷらさん、Eはかっつさん、Hはぷらさん。この辺りはノータッチだった。

Aは2乗の木dp。葉を1個見なくてもよいので見ていない葉が0個か1個かで2種類の値を持つ必要があること、ある頂点のモニターを確認したらそれぞれの子以下の部分木から1個ずつ見なくてもよい葉を選べて、それは全体で見ないことにした葉にはカウントされないことがポイント。それぞれ1回ずつWAを出した。中途半端に気付いてしまったため葉の数が1個のケースをずっと特別扱いしていて、考察を進めるたびに場合分けが減って綺麗だった。

この辺りで二人が離脱したはず。Mの考察ができていて、実装も途中まで進められていたが、以下に述べる理由で一から書き直し通した。

解法は桁dp。和に関する制約があるので、途中まで実装されていた上の桁から見る方法はちょっと大変。そこでARC156Dと同様に下の桁から見ることにした。これで毎回偶奇だけ気にすればよくなる。下の桁からでも桁dpできるというのは知ってはいたが、明確に効く問題はなかなか見ない気がする。

D - Xor Sum 5

Cはすべての頂点 $u$ に対し $1\rightarrow u\rightarrow n$ パスがあるという条件から、 $1\rightarrow u$ パスの重み $L_u$ が一意に定まらなければならない。この値を決めることを考えた。

まず、辺 $x\rightarrow u$ と $y\rightarrow u$ が同時に存在する場合 $L_u=L_x+w_u=L_y+w_u$ だから $L_x=L_y$ がわかる。この関係で等しい $L$ を持つ頂点を一まとめにした。また辺 $u\rightarrow v$ があれば $L_v=L_u+w_v\gt L_u$ がわかる。この大小関係を一まとめにした後のグループ間で辺を張って表現した。

これで自己ループができたりグループ間にサイクルができれば矛盾がわかる。そうでなかった場合トポロジカルソート順に値を割り振ることで上の条件を満たせて、 $w$ が復元可能になる。

Iはちょっと面白い。2乗の木dpを全方位木dpにしたくなるが計算量が壊れてしまいできない。そこで連結成分を決めながら根となる頂点も一緒に選ぶことにすると、うまいこと遷移も書けて解ける。

解けたのはここまでで、残り時間はJとKに取り組んでいた。

Jは手で数項計算すると規則性がわかる。整理すると $\sqrt{S_i}$ という値を $\sqrt{S_0}=0$ から負にならないように $\pm 1$ していることになる。 $a_i=-1\pm 2\sqrt{S_i}$ から $\sqrt S$ の上限も求まる。こういうのはよくある問題に見えたが、上下に制限があるとどうしていいかわからない。適当に包除したらWAだった。上限と下限を両方満たさない遷移を引きすぎているようだ。

Kはサンプルが合うように頑張って数え上げる対象を列挙した。まず1辺とその両端点は一直線に並ぶから、追加で1点選ぶ方法はすべてOK。さらに長さ2のパスとその上の端点も一つの平面を定めるためOKで、特に真ん中の頂点以外を選ぶ方法は先ほどカウントしていない。同様の理由で長さ3のサイクルとその上の1点もOK。これは1点を選ぶ方法が3通りある。

これでもまだ微妙に足りなくて、最後に残ったのが長さ4のサイクルだった。この4辺に対応する点の間には線形の関係式があるから同一平面上に乗る。これでサンプルが合った。一応、4点のうち辺の本数が0本から4本まですべてのケースを網羅したからこれで全部だとも考えられる。

数え上げるのが大変なのは $C_3$ と $C_4$ だが、検索すると以下のツイートが出てきて、その先をチェックすることでどちらもライブラリがあることを知った。特に $C_3$ は列挙すらできるようだ。しかし貼って出したらMLEして、最後まで解消できなかった。

C4 counting O(m^(3/2)) は kopricky ライブラリにあるhttps://t.co/SR4xTOhKSX
— ホハム (@soiya_ksk) 2022年7月17日

https://kopricky.github.io/code/Graph/EnumeratingC3.html

終盤ぷらさんが帰ってきてB問題の考察と実装をしていたが、こちらもサンプルが合う前にコンテスト終了。その後通ったらしいのでもうちょっと時間があれば……といったところか。

感想戦。ぷらさんからLとHの解法を聞いた。Lは人を駅に割り振った後駅ごとに並び替えを考えるのではなく、並び替えてから割り振らなければならないという点が少し気づきにくそう。その後かっつさんがいないので二人でEを解いた。1回ボタンを押すたびに誰かを1秒邪魔できると読み替えるのが重要。

感想戦の途中でKが通った。MLEを回避するため、次数の大小で処理を分けるときの閾値をかなり小さめにした。代償として4.9secかかっている。TLは5secなのでギリギリ。

解散後、日付が変わったくらいにJを通した。鏡像法というのを使うと聞いたがわからなかったので詳細な説明をお願いしたら、次のような考え方を教えてもらった。非常に美しい。カタラン数を求めるときに使う最初に対角線をまたいだ瞬間残りを反転するという方法についても、残りではなくこれまでの経路を反転すると思い直せば同様の解釈が可能となる。

カタラン数の場合、自分は残りを反転した後一対一対応を作るという方法を覚えていた。しかし今回はここがうまく作れなくて困ってしまう。こうやってdp配列の値の対称性を考えることを覚えておきたい。

対応させているというよりは、単に dp table が常に
..., 0, a, b, c, 0, -c, -b, -a, 0, a, b, c, 0, ...
の形になるようにしているという理解をしています。
— maspy (@maspy_stars) 2023年3月8日

しばらくハーメルンを読んでいたが、そのうちうっかり布団に潜り込んでしまった。午前1時くらいに寝落ち。

03/09(木)

午前4時半起床。また延々ハーメルンを読んでいた。午前9時に二度寝に成功。

正午に目覚ましで起床し、シャワーを浴びて用事のため外出した。まず火曜日ゲーセンに忘れてきたスマホアームを回収。その後指導教員の先生、同級生、博士課程の方というセミナーのメンバーで食事会をした。博士課程の方が無事卒業され3月末に母国に帰国されるのでその記念である。

食事 pic.twitter.com/DZP9DWJpMT
— こたつがめ (@kotatsugame_t) 2023年3月9日

大町西公園で咲いていた梅をバックに写真を撮り、帰宅。帰り道は博士課程の方と二人きりで、英語でなんとかかんとか会話しながら歩いた。袴・着物・浴衣の違いがよくわからないみたいなことをおっしゃっていたはず。説明を試みるも話すうちに自分でもよくわからなくなっていった。

午後3時前に帰宅し、そのままMuscatキャンプ2日目。ぷらさんが出られなくて二人だった。ちなみにこのキャンプのセットについてはまだ外部での言及が禁止されているから、当然日記にも書けない。そのうち解禁されてから参加記としてまとめたい気持ちはある。

04/18追記：書いた。

kotatsugame.hatenablog.com

午後6時半からはキャンプを抜けてCF #857 div.1に出た。

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

Aから詰まってしまった。最終的には要素の重複がない状態ですべての $2\times 2$ 部分行列のXORを0にできた。どの2列を選んでも、すべての行についてその行にある要素同士のXORが等しくなればよい。1列適当に決め、他の列をそれとのXORによって決めることで達成できる。適当にやったら同じ要素が出現してしまい1WA。

ちなみに部分行列の一般的な定義では行または列を非連続に取り出したものも考える。上の構築はそれでも条件を満たすが、サンプル出力は満たさない。実際注釈には $5\times 5$ 行列の $4\times 4$ 部分行列が4個だと書いてあった。しかし連続なものしか考えないということは問題文に書いておくべきではないだろうか。ここを確かめるのにも時間をかけた。

Bは $a$ の最大値を決め打って $b$ について考えればよい。ペアとなる $a$ が決め打った値より大きい場合は $b$ を採用するしかない。そうでなくても決め打った値に近い $b$ を持つペアはそちらを採用する可能性があって、setの二分探索で調べるべき定数個を取得できる。

Cはimpressionを得られないアルバムは聴かなかったものとしてよく、この場合聴いたアルバムは最大値の昇順になっているため同様に並べた上でdpすればよい。遷移は列の長さ分時間をかけられるので、アルバム中最初にどの歌でimpressionを得たかをすべて試せる。

Dはよくわからない。頂点番号のほかにこれまで通ってきた中で $w$ が最大の頂点番号も持っておき、パフォーマンスの回数と所持金のペアを距離として最短経路を求めたら通った。所持金が足りなくなるたび $w$ が最大の頂点でパフォーマンスしていたことにしてから遷移するというもの。

Eはsolved数が少なかったが取り組んだら通った。同じ価格だと分かった頂点を新たにマージするのは高々 $n-1$ 回しか発生しないから、マージしなくてよい頂点を飛ばしながらパスを舐めることができればよい。これは、まずHLDによってパスを分解した後、セグ木上の二分探索でどこまで一致しているか見るという方法で実現できる。頂点のマージをマージテクで行うことでセグ木の更新が可能。頑張って実装した。

自分の実装では計算量の保証が全然できていないことにコンテスト後に気づいた。パス上の区間でその間がすべてマージされているものを探したが、ひたすら同じクエリが飛んでくると全然マージされないので区間の数が全然減らない。正解はマージした集合に番号をつけてそれを頂点に振り、数列として一致する区間をロリハで求めることだったようだ。その実装はキツすぎる。

Fはかなり多く通されていたのに全く分からずコンテスト終了。なぜかEがシステスを通過して無事5完、しかしFが通されすぎてこれでも55位、2960→2930(-30)。RoomのBとCが合計で17個落ちていてびっくりした。OI系のコンテストはpretestが強い印象があったがそんなことはないらしい。

その後はハーメルンを読み進めていた。午後11時頃読了。「とある黒猫になった男の後悔日誌」。

syosetu.org

面白かった。主人公の内心と外面がかなり違うことによる勘違いモノという側面もあるように見えたが、メインは単純に無双だと思う。戦闘で強いだけでなく統治・統率関連でも才能を発揮していて良かった。主人公の口調の慇懃さが少し気になる。丁寧な態度とへりくだる態度は紙一重であると考えていて、後者のほうにちょっと振れて見えてしまった。ちゃんと締めるところは締めるのだが。

しばらく日記を書き、午前4時台はインターンの作業をしていた。ドキュメント整備。操作の様子を録画したりして結構丁寧に作った。想定している読者はわざわざChromeをインストールして使っていたりしないだろうと考えわざわざMicrosoft Edgeを使ったが、これはOBS Studioでウィンドウキャプチャできないらしい。画面ごとキャプチャするしかなかった。

ゴミを出して布団に入り、カクヨムから「大学入学時から噂されていた美少女三姉妹、生き別れていた義妹だった。」を読了。

kakuyomu.jp

読み終えて作者の作品リストを見てから気づいたが、この方の書かれた「貴族令嬢。俺にだけなつく」というラノベを読んだことがある。言われてみればヒロインが主人公をヨイショする様がかなり似ている。どちらも過剰に感じてあまり好みではなかった。

午前8時頃寝落ち。

03/10(金)

正午を過ぎて起床。半から1on1。

いつものように進捗を報告した後来週のタスクについて話した。ドキュメント整備はもうそろそろ終わりにして、そのドキュメントをもとにやってもらった作業の結果を使う準備をしなければならないらしい。とりあえず来週までに最低限整備を終わらせておくことになった。

午後2時終了。今日のMuscatキャンプのセットを確認するとUniversal Cupで使用されたものだったため、水曜日と同じように代わりのバチャを立てて走ることになった。午後3時から開始。

Dashboard - 2017 China Collegiate Programming Contest Final (CCPC-Final 2017) - Codeforces

EACKGJIHを解き8完。自分はCHを実装した。今回のセットはなぜか出力がGCJ形式で、テストケース番号を振るのを要求されていた。

Eはかっつさん。Aは最初自分が読み、完全順列の式を書いて唸っていたが、かっつさんに期待値の線形性から $N-1/N\times N=N-1$ じゃないですかと指摘された。かっつさんはE問題を解いてすでに出力フォーマットの実装が済んでいるため、この問題も書いてもらった。

Cも整理するだけの簡単枠だが結構手間取ってしまった。 $X\gt Y$ ならお互い1点ずつ取り続けるだけで無限に所持金を増やせる。そうでない場合、セットに負ける場合0対11にするべき、勝つ場合0対9から11対9にするべきで、どちらかの回数を全探索できるためそれぞれチェックすればよい。

Kはぷらさん。実験結果から素早く式が作られていたが、答えが64bit符号付き整数に収まらず符号なし整数を使わなければならないところにハマっていた。自分も読みに行ったもののなかなか気づけなかった。1手で上下左右に2マスずつ広がると考えれば到達可能なマスはおよそ $4N\times 4N$ の長方形領域（から角を切り落としたもの）と思えて、サイズが $16N^2\approx 1.6\times 10^{19}$ となる。

Gは自分とかっつさんで考えていたが $O(NK\log N)$ にしかならず困っていた。この $\log$ は区間取得にかかっている。取得する区間の端点を全体の端にできることがわかり、セグ木ではなくBITを使えるようになったので書いてみようとしていたところ、ぷらさんから各点から遷移できる右端にだけ行くという $O(NK)$ 解が提案された。そのまま実装してもらいAC。

後からBITによる解を書こうとしてみたら、単に端点から累積MAXを取っておくことで実現できることに気づいた。こちらも $O(NK)$ になってAC。ちなみにBITを使っても1secで通った。

Jはかっつさん、Iはぷらさんがそれぞれ通した。ここはノータッチでその間自分はFを考え、その後諦めてHに進んでいた。

Hは前セメスターTAをしていた経験が生きた。2次元なら正三角形、3次元なら正四面体状に点を配置すればよい。4次元だと正五胞体という名前になり、その後正単体へと一般化される。よって $N+1$ 点が最大で、入力の制約から必ず達成できる。

構築方法としてまず一つ単体を求め座標変換して入力に揃えることを考えたが、高次元の座標変換はよくわからない。よってそちらは諦め次元を一つずつ拡張していくことにした。点が $N$ 個以下の場合 $N$ 次元の超平面に乗っているから、それの法線ベクトルを求め、適切な長さで点たちの重心に足す。これが新しい点となる。

法線ベクトルは、すでに存在する点に関する線形関係式 $\sum_{i=1}^n a_ix_i+a_{n+1}=0$ を連立させて解くことで $(a_1,\dots,a_n)$ として手に入る。 $(x_1,\dots,x_n,1)^T$ を並べた $N+1$ 行の行列の右側に $N+1$ 次単位行列を並べ掃き出し法を行うと右側の行列の行ベクトルに現れる、という方法で計算した。

掃き出し法には $O(N^3)$ かかるため、毎回行うわけにはいかない。ただし対象となる行列は列が一つずつ増えていくだけだから、前回の計算結果を使いまわすことで毎回 $O(N^2)$ にまで削減できる。これで合計 $O(TN^3)$ 。

TLは……1sec！とりあえず出したらTLEしてしまった。手元で試すと8secかかって青ざめていたが、CFで実行してみたところ入力なしで1060msだったので希望が見えてきた。vectorを生配列に直し、long doubleをdoubleに変え、pragmaをいくつか足してもう一度出したら900msで通った。

残り時間はDを考えていた。解けた気になって実装を始めたが、 $\binom{n+i}{k}$ を巨大な $n$ と連続する $i$ で計算する必要が出てきて時間が足りず放棄。 $i$ に関する結果から $i+1$ に関する結果を求めるいつもの方法だと $n$ くらいの数で割り算をする必要があって、法の $10^9+7$ を軽々超えてしまう。

感想戦。Eはまあ簡単枠。Jは牛ゲー、Iはなもりグラフをループと木に分けて管理するかなり面倒そうな問題だった。それぞれ解いてもらえて本当に助かる。またTLで見た他のチームの解法に、Hで足すベクトルを直交補空間の直交基底として一発で全部求めるものがあった。言われてみれば確かにそういう関係になっている。

午後9時20分からyukicoder 380に出た。最近ご無沙汰だったが、今週はかなり競プロ漬けなのでここまで来たら出られるものには全部出ようと考えた。

yukicoder contest 380 - yukicoder

Aは制約が小さいので全探索。式を考えながら書いていたら実は結構きれいな形だということに気付いたが、そのまま書ききったほうが当然早い。Bは貪欲でよい。この2問はFAだった。

Cはしてやられた。愚直を書こうと思ってもどの範囲まで調べれば良いのかわからない。結局手で計算して、 $5\rightarrow 16\rightarrow 1$ から奇数が全部2手でできそうだと感づいた。「 $N$ が奇数ならある $k$ が存在し $2^k\equiv 1\pmod N$ が成り立つ」と聞けばいかにも正しそうに見える。出したら通った。

Dはダブリング。 $H$ をソートした列の上で $T$ で二分探索したり、結構手数は多かった。

Eは難しかった。包除原理で立式すると、集中精進期間を $d\le N$ 日間としたときの場合の数が $\sum_{i=0}^d(-1)^i\binom{d}{i}\prod_{j=1}^M{}_{d-i}\mathrm{P}_{c_j}$ として表される。ここで $c_j=\#\{A_i=j\}$ である。この式を分解すると $d!$ 以外は $i$ に関する項と $d-i$ に関する項の積に分解できるので、それぞれ計算できれば畳み込みで求まる。前者は簡単。

問題は後者の $\frac{1}{(d-i)!}\prod_{j=1}^M{}_{d-i}\mathrm{P}_{c_j}$ を高速に求める部分。 $\sum_j c_j=N$ から $c_j$ の値の種類数が $O(\sqrt N)$ 通りしかないため、どんな数が何回現れるか集計しておいて、 $d-i$ を固定するごとにその集計結果を全部見ることで全体 $O(N\sqrt N)$ になる。内側でべき乗を計算したりしているが十分高速だった。

Fは結構すんなり解けた。 $A_1\gt 1$ または $B_1\gt 1$ なら1が答え。そうでない場合どちらかのデッキから取り出せる数は答えにならない。逆にそうでない数、つまり $k\notin A\cup B$ に対する $[k^2,(k+1)^2)$ が答えの候補になりそう。

そのような $k$ のうち最小のものを取ってきたとき、この区間に素数が含まれていればそれが答えの上限となる。多分あるだろうと思ってプログラムを書いて試してみると確かに存在し、しかも最小のものは $k^2$ に十分近いところにあると分かった。よって $k^2$ からその素数までを全探索し、それぞれ約数全列挙してチェックすることができる。出したら通った。

Gは難しかった。こういうシチュエーションの期待値に関する事実があったことを思い出し、「一様分布」「最小値」「期待値」で検索して出てきた以下のページを眺めながら考えていた。

最大値と最小値の分布（一般論と例） | 高校数学の美しい物語

$x\gt y$ である確率を $P(y)$ と置くと、これはどんな経路を通っても $y$ 以下の数が高々1個しか存在しない確率に等しい。サンプル1の $2\times 2$ マスの場合、 $y$ 以下の数が出現するマス数としては0個、1個、または左下と右上の2個というケースしかない。それぞれ確率は $(1-y)^4$ 、 $4\times y(1-y)^3$ 、 $y^2(1-y)^2$ である。足すと $P(y)$ になるはず。

スコアの期待値を計算するためには、 $x$ が特定の値である確率を知る必要がある。 $x$ の累積密度関数 $1-P(y)$ を微分すれば得られる。それに $y^K$ を掛けて $0\rightarrow 1$ で積分することで答えが求まる。上の例をWolfram|Alphaに投げると確かに13/30となった。

あとは $P(y)$ の計算。 $T=\min(H,W)$ と置くと、 $y$ 以下の数が出現するマス数 $c$ は $0\le c\le T$ を満たす。また $c$ 個のマスをどの二つも右下への経路に同時に乗らないように配置する方法は、 $c$ 行と $c$ 列を決めて左下から右上に並ぶようにするしかないので、 $\binom H c\binom W c$ 通りあると分かった。これに $y^c(1-y)^{HW-c}$ を掛けて足し合わせたものが $P(y)$ となる。

このあたりでコンテストが終了したがそのまま実装を続けた。多項式を直接計算するとサンプルがあったもののTLE。さすがに $HW$ 次の式は扱っていられないようだ。和の形に分解したまま計算する場合は、 $c$ ごとに $y^c(1-y)^{HW-c}$ を微分し、 $y^K$ を掛け、積分できればよい。手計算とWolfram|Alphaを組み合わせて何とか閉じた式が得られた。

まだ $(HW+K)!$ くらいの階乗が出現して組み合わせ計算のライブラリを貼っていては間に合わなかったが、分母分子で打ち消しあって狭い範囲の積しか残らないようで、そこを丁寧に扱うことで爆速になった。30分遅れで無事AC。

コンテスト自体はFまでの6完で、writer・testerを除くと5位。Gの解説を読むと $(1-P(y))'y^K$ ではなく $P(y)(y^K)'$ を積分していてびっくりした。これでもよいことの直接的な理由は分からないが、maspyさんに部分積分と $P(1)=0$ を使うことで同じ式になると教えてもらった。

03/14追記：writerの方から教えていただいた。

writerです。解いてくれてありがとうございます。

離散verとして、k回になるときのスコアがkのときのスコアの総和を求めてみます。「f(k)=k回になる場合の数」としてsum[k]k*f(k)を計算するのがこたつがめさんの方法、「g(k)=k回以上になる場合の数」としてsum[k]g(k)を計算するのが解説の方法です。
— noya2 (@noya2ruler) 2023年3月13日

食事してから迂闊にもカクヨムを読み始めてしまった。午前3時頃「【悲報】売れないダンジョン配信者さん、うっかり超人気美少女インフルエンサーをモンスターから救い、バズってしまう」を読了。

kakuyomu.jp

配信やコメント・掲示板の描写にやけにリアリティがあって辛い。現実のVTuber・配信者に関するネタがポジティブ・ネガティブ問わず盛り込まれていて、読んでいて微妙な気分になるシーンがいくつかあった。しかし話の内容・展開自体が面白かったため、それらの要素を飲み込んで読み進めていけた。主人公が気弱そうなのにちゃんと無双していて嬉しい。ダンジョン探索者としても、配信者としても。

シャワーを浴びて日記を書き、午前6時に布団に入った。何を考えたのかハーメルンで1時間弱溶かしてから就寝。

03/11(土)

午後1時半に目覚ましで起床。今日はMuscatキャンプが休みだが代わりにUniversal Cupがある。日程の被りが見事に回避されていていかにも全部参加してくれと言っているかのよう。

Universal Cup 7回目でZaporizhzhiaセットだった。今回は、少なくとも解いた範囲では考察の難しさのわりに実装が簡単な問題ばかりだった印象。

The 1st Universal Cup. Stage 7: Zaporizhzhia - Dashboard - Contest - QOJ.ac

チームでEKGHIMJDを解き8完、53位。自分はKHJの考察＋実装に加え他のいくつかの問題でも考察に参加した。

かっつさんがEを通している間にKを考える。 $n=2$ で実験すると、次のような行基本変形ができた。上の行から順に見て、下の適切な行から引いている。この操作で行列式の値は変わらない。

右下三角形が0になったので、符号に気を付けながら余因子展開を行えば行列式が求まる。右上から左下への対角線上にある成分は、添え字をbitの集合と見てある集合の上位集合すべてを符号を入れ替えながら足しているとエスパーできる。これはゼータ変換っぽい感じで求まる。

Gの考察に参加した。条件を式で書き移項すると $a_1+a_n=a_2+a_{n-1}=\dots$ が得られて、ここから $n$ が偶数の時はすぐわかる。 $a$ をソートして両端からペアにしていけばよい。 $n$ が奇数のときどうなるかちょっと悩んだが、中心の要素が二つにコピーされると思えば偶数のケースに帰着できた。実装はかっつさんに任せた。

Hを考えていた。 $G$ が単なるサイクルのとき、同型なグラフの個数は円順列の数と一致するから、 $n\ge 5$ ならNO。次に $G$ がサイクルを含む場合も同様のことを考えて、同様に $n\ge 5$ なら必ずNOになると思い込んだ。後述するようにこれは間違っている。

とにかくサイクルを含むケースの処理が終わった。 $n\le 4$ での場合分けは複雑なので、この範囲は全探索することにした。よって残りは $n\ge 5$ かつ $G$ が森である場合。

同型でない二つの木が存在すると必ずNOになることが言えた。すべての木が同型である場合も木が複数あるとNO。正確には1頂点の木が $n$ 個あればYESだが、今 $m\ge 1$ なのでそれは考えなくてよい。

最後に残ったのが $G$ が木である場合で、これは葉とその親を二組固定するとそこだけで $n$ 通り以上の頂点番号の入れ替え方を作れそうだった。これもNO。

結局 $n\le 4$ は全探索、 $n\ge 5$ はNOとして提出した。しかしWA。実は3ケースだけ特別扱いをする必要があって、それぞれペナを出して4回目でようやくACできた。

特別扱いするべきだったのは、完全グラフ、完全グラフ＋孤立点、ウニグラフ。まずウニグラフは $G$ が木でありかつ「葉とその親を二組固定」ができないケースだった。完全グラフ＋孤立点はこの補グラフで、完全グラフは「1頂点の木が $n$ 個」の補グラフ。これ以外を特別扱いしなくてよい理由はわかっていない。

Iも考察に参加した。1回目にどの順で頂点を取ったか固定し、その順で頂点を見ながら2回目の操作を挿入dpっぽく考えることで、被ってしまう操作の回数を数え上げる。これまで $k$ 点取って $k+1$ 点目を考えているとき、それを1回目と同様 $k+1$ 点目に取るなら辺の張り方は $2^k$ 通りあるが、もし1点目に取るなら $2^0$ 通りしかない。

その間も足し合わせ、合計 $2^0+2^1+\dots+2^k$ を $k$ 点目までの値に掛けることで $k+1$ 点目までの値が求まる。この計算をあらかじめ行って途中の値を保存しておけば、クエリごとに定数時間で答えが出せる。実装はぷらさんにお願いした。

Mはかっつさんが取り組んでいたがWAが出て直っていなかったため、自分も問題と実装を読んで考えてみた。最初は使用するボールの個数を疑っていたが、一周期にかかる秒数を $n$ で割ったもの、つまり一周期で列を何周するかを使用する現在の実装が正しいことに納得できた。

次にどちらの手を使うかを疑ってみた。 $n$ が奇数のとき同じインデックスでもループするたびに偶奇が変わってしまうことがポイントに見えて、そのあたりで考えていると、片方の手だけ使うと判定されたボールでも一方の手に集中するのではなく両方の手に半分ずつ分かれるということに気づいた。このコーナーケースを伝え直してもらったら無事通った。

Jはrollbackを使えるなら使って全コイン賭ける、使えないなら1コインずつ賭ける、という戦略が最適だと予想。最悪ケースでは $m$ 回でrollbackを使い切り、所持コイン $2^m$ 枚の状態で $n-m$ ターンしのぐ必要があるので、 $2^m\lt n-m$ なら答えは「破産」になる。

そうでない場合、どのターンでrollbackを使い切るか、使い切らないなら $n$ ターンで何回使うかを変数において立式してみた。

前者について $k$ ターンだとすると確率が $\left(\binom{k}{m}-\binom{k-1}{m}\right)\times\frac{1}{2^k}$ であり、所持コイン枚数については $k$ ターン目の $2^k$ 枚以降期待値的には変化しない。掛けて $m\le k\le n$ で足すと $\binom{n}{m}$ が得られる。

後者について $k$ 回だとすると確率が $\binom{n}{k}\times\frac{1}{2^n}$ であり、所持コイン枚数は必ず $2^n$ 枚となる。 $0\le k\lt m$ で足し上の値も含めることで $\sum_{k=0}^m\binom{n}{k}$ が答えとなった。マルチテストケースなのに $m$ の総和にしか制約がなかったのも納得。これでサンプルが合い、そのままACした。

Dも考察に参加した。右下で2回ほど余因子展開することで漸化式 $A_k(x)=xA_{k-1}(x)-b_kA_{k-2}(x)$ が得られる。ここからゴリゴリ $A_9(x)$ くらいまで計算した結果、 $b_1+b_2=b_3+b_4=b_5+b_6=b_7+b_8=0$ や $b_1+b_5=b_5+b_9=0$ という関係式を手に入れた。

しかし規則性が見えない。すでに得られた関係をもとに項を消去しているから複雑なんだと感じたため、そのまま計算してみたところ、なかなかいい感じの表現が見つかった。

$A_k(x)$ は $x^{k+1}$ 次式で、 $[x^k]A_k(x)=[x^{k-2}]A_k(x)=\dots=0$ 、 $[x^{k+1}]A_k(x)=1$ 、 $[x^{k-1}]A_k(x)=b_1+\dots+b_k$ 。 $[x^{k-3}]A_k(x)$ は $b_1,\dots,b_k$ から「添え字が隣り合わないように」二つ選んで掛け合わせたものすべての和になる。 $[x^{k-5}]A_k(x)$ の係数はそれを三つ選んで行ったものになる。以下同様。

この表現を考えることで計算が楽になった。三つの積まで観察し、上で求まった類の式から増えないことを確認してかっつさんに実装に入ってもらったが、その後計算を続けていくうちに四つの積に関する式 $b_1b_3b_5b_7+b_5b_7b_9b_{11}=0$ が見つかった。上の式を用いて整理することで $b_3+b_{11}=0$ が得られる。

さすがにこれ以上はやっていられないが、計算の途中で2べきっぽさは感じ取っていたため、おそらく次の式は $b_1b_3b_5b_7b_9b_{11}b_{13}b_{15}+b_9b_{11}b_{13}b_{15}b_{17}b_{19}b_{21}b_{23}=0$ となるだろう。これも整理すると $b_7+b_{23}=0$ と綺麗な形になる。添え字の差が4、8、16と増えているのもそれっぽい。これで改めて実装してもらったら通った。

残り時間はAとLを眺めていた。Aは実験結果から $m$ が素数なら $m\bmod 4$ で場合分けして解けるが、それ以上のことはわからない。平方剰余で検索しても特に進展はなかった。Lはそもそも $m$ 辺のDAGを数え上げるのすら難しそう。一応OEISにあった。

A081064 - OEIS

感想戦。Eはいくつかの場合分けで解けるようだ。 $L$ と $R$ が両方偶数の時に作れないのはちょっと面白かった。他の問題については上にほとんど書いたので省略。

Hの3ペナは大反省だった。補グラフにも注目すべきということを1ペナ目くらいにはわかっていたはずなのに、ウニグラフとその補グラフで1ペナずつ使っているのが意味不明。コーナーケースを1個見つけた瞬間狂喜乱舞して提出せずにはいられなくなってしまう。

実は両親が仙台に来た。19時まで対応できませんと伝えてあって、コンテスト終了後部屋に招き入れてからも感想戦のためさらに待たせてしまった。駆け足で終わらせたが20分くらいかかり、その後ABCに間に合うよう急いで外食に出かけた。

今日はココス。ちょうどにじさんじとのコラボキャンペーンをやっていたが、特典のクリアファイルは売り切れだった。期間終了も間近だし仕方ない。

食事 pic.twitter.com/daGBNZNvFC
— こたつがめ (@kotatsugame_t) 2023年3月11日

帰宅してすぐABC293に出た。まだ親がいるので今日は実況はなし。

AtCoder Beginner Contest 293 - AtCoder

Aはsedで2文字ずつマッチさせ、それぞれキャプチャして入れ替えたものに文字列置換することで実現できる。

Bは問題文を読んでいなくて $\{1,\dots,N\}\setminus A$ を出力しようとしていた。しかも提出欄にRubyコードを直接コーディングしたところtypoがあって2RE。ちゃんと手元で書こうとしたタイミングでようやく問題文が思っていたのと違うことに気づいた。C++で実装。

Cは $\binom{H+W-2}{H-1}$ 通りの経路をbit全探索で生成しそれぞれチェック。dfsのほうが途中でチェックを行えて速いだろうがこちらでも問題なく通った。

Dは頂点を倍加して赤の端、青の端に対応させ、入力の通りに繋いだ。すでに繋がっているロープの両端点を結んだときに答えの $X$ をインクリメントしておけば後から閉路のチェックをしなくてよい。

Eは $\frac{A^X-1}{A-1}$ に書き換えてから割り算ができないことに気づきしばらく固まっていた。結局書き換え前の形で考え、 $X\leftarrow\lfloor X/2\rfloor$ としたときの解をずらして足し合わせれば二分累乗法っぽいことができると気づいてAC。

Fは難しかった。 $b$ を適当な範囲で全探索したいから、 $b$ 進法で表記したときの桁数が小さいものは直接計算することにした。1桁はありえない。2桁なら $b=N,N-1$ である。3桁なら2次方程式を解いて4通りの解候補が得られる。4桁は……やっていられない。このままでは $O(T\sqrt[3]N)$ かかってしまう。

そこで適当な数 $B$ について $b\ge B$ かつ4桁以上で表現可能な $N$ をあらかじめ全列挙しておくことにした。10⁶まで見ればいいのでなんとか間に合う。あとはクエリごとに $2\le b\lt B$ かつ $b^3\le N$ の範囲で全探索すれば求まる。 $B=1000$ で出したら2secかかったが通った。

Gは $A$ に出現する回数が多いものと少ないもので処理を分けた。具体的には、 $W$ 回以上出現するものはそれだけ集めてクエリを一つ一つ計算、それ以外はまとめて計算。

後者の具体的な方法は、 $k=1\dots N$ の順に見て、 $A_i=A_k$ なる $1\le i\lt k$ に対しBITの $i$ 番目に $\#\{i\lt j\lt k\mid A_j=A_k\}$ を足しておくというもの。クエリ $(l,r)$ に対しては $k=r$ の処理が終わったタイミングでBITの $l$ 番目以降の総和を答えればよい。毎回 $O(W\log N)$ かかる。

最初は前者の計算時に抜き出したインデックス上の二分探索を行っており $O(Q\log N)$ かかっていた。 $W=500$ として提出しTLE。この二分探索の代わりに毎回 $O(N)$ かけてすべて計算しておき、 $W=200$ としたら1secで通った。

Exはまず木dpで直接答えを求めようとし、二分探索が必要なことに気づいてdpの遷移を書き直していたら時間が足りなかった。30秒遅れで書きあがったものを提出するもWA。

7完70位。Dは頂点を倍加する必要がないらしい。Fは3桁以上なら $b$ が高々一意であるようだ。そういうことを考えた気もするが、なぜかたくさんあると思い込んでしまった記憶がある。Gの想定解はMoだった。

コードゴルフ。AはVimで「カーソルの下の文字を削除→カーソルの直後に追加→カーソルを右に移動」をループすれば解けて、12Bでsedの文字列置換19Bより短くなる。午後10時くらいに気づいて提出しておいたが、コンテスト開始直後に同様の提出があって負け。

また日記を書いているときに確認したらbashにも12B解があった。ddコマンドのオプションでconv=swabを指定すると2バイトずつペアにされて入れ替えられるようだ。これは太古の昔、エンディアンが異なるデータを扱うために使用されたらしい。

history - Why does `dd` have `swab` functionality - Unix & Linux Stack Exchange

BはAWK。フィールド変数を書き換えながらループすることで、最終的な$0は呼ばれなかった番号が昇順に並び間が穴あきになった文字列となる。これを$0に代入しなおすとNFが現在のフィールド数、つまり呼ばれなかった番号の数に更新されるので、わざわざカウントしなくてもよいというもの。結構改善が残っていて負け。

CはRubyでdfs。既出の要素はhashに0を入れておくことにして要素が重複した時の返り値にしたり、盤面の外に出ないかチェックして再帰呼び出しするところまでを条件式と捉えて終点のチェックを1回しか行わないようにしたり、細かな改善が結構うまくいった。

Dは入力の制約から通常の閉路検出より実装が軽くなる。常に「ひとつながりのロープにおけるもう一方の端」を持っていると考えることで、ロープを結ぶ操作がDancing Linksと同様にして行える。Rubyで書いたらPerlで縮められたが、AWKで書いたらさらに縮んだ。

Eはdc。解説にある $\bmod{(A-1)M}$ で計算して $A-1$ で割る方法に仰天。何度も見たのにまた忘れ去っていた。これをdcで書いた。0で余りを取ろうとすると演算自体が行われなず、スタックの中身が通常とずれるのを利用することで $A=1$ の場合分けが行えた。

以降は手付かず。

Exをupsolveした。部分木の根と同じ色を今見ている頂点にも塗れるか、塗れないかで2状態持った。子の数の2乗で計算するコードを書き答えを合わせてから1乗に落とした。かなり大変。

Submission #39650680 - AtCoder Beginner Contest 293

maspyさんの実装が簡潔と聞いて見に行った。今見ている頂点に塗った色に関する次数を持ってdpしているようだ。子をいったん全部集めると遷移の際に「子のうち値が大きいほうから二つ」みたいなものが欲しくなるが、この捉え方なら自然に書けるということには見覚えがある。今回はそこまで思い至れなかった。

Submission #39622473 - AtCoder Beginner Contest 293

日記を書いて午前7時前就寝。

03/12(日)

午後2時半起床。食事して午後3時から5時間Muscatキャンプ4日目に出た。

今日はかっつさんが用事で不在のため二人……と思っていたが、かっつさんも合間を縫って読解と考察に参加してくださっていたようだ。途中誰も読んだ覚えのない問題の概要と考察がHackMDに書かれていて、ぷらさんと二人でびっくりしていた。

午後8時に終了し、しばらく感想戦をして解散。食事して午後9時からARC158に出た。

AtCoder Regular Contest 158 - AtCoder

Aから大変だった。操作を $+0,+2,+4$ に読み替えたのが敗因だったらしい。偶奇の条件をチェックした後2で割ることで $+0,+1,+2$ をする問題になる。和が3ずつ増えるので、もともとの和も3の倍数である必要がある。ここから先に進むのに30分かかった。二分探索を考え操作回数を固定しても判定関数が書けない。それっぽいものでサンプルが合ったので投げたがWA。

結局場合分けと貪欲で通った。最小の要素に $+2$ 、最大の要素に $+0$ するのを三つのうち二つ以上が揃うまで行う。揃ってからの操作はどこが揃っているかでそこに $+0+1$ と $+1+0$ をするか $+1+2$ と $+2+1$ をするかを変えるだけ。和が3の倍数という条件からこの操作でいつか必ず揃えられるし、絶対に必要なことしかしていないから最適。

Bはすぐ解けた。式を分解すると $\frac{1}{x_ix_j}+\frac{1}{x_jx_k}+\frac{1}{x_kx_i}$ となる。選ぶ数の符号を決め打ってみると各項の符号も分かって、項の絶対値を大きくするべきか小さくするべきかが定まる。それに応じてできるだけ絶対値が大きい・小さい値を使えばいいので、正負それぞれ候補は高々六つしかない。取り出して全探索。

Cもすんなり解けた。桁ごとに分解して考える。 $10^k$ の位を考える際、数を $\bmod{10^k}$ でソートしておくことで、ソートした列のどの範囲の数と足したら繰り上がりが起こるかが決まる。繰り上がりが起こる範囲と起こらない範囲でそれぞれ $10^k$ の位の数字をカウントしておき、それを見て答えればよい。

Dは解けなかった。左右で式の次数を合わせるため $x+y+z\equiv 1$ としたいと考えあれこれ試していたがどうにもならず、 $p$ が小さいケースで試したところそもそもそのような解が見つからないことを知って絶望。順位表や点数を見る感じEにもチャンスがありそうだったので、そちらに進んだ。

Eは見た目的にDより解けそう感があって、実際解けた。分割統治。マスとマスの間で縦に切ると、パスがその境目を1行目と2行目のどちらで通るかが一意に定まる。左右それぞれ両方のケースに対する答えを求めておく。

境目の左のあるマスで $L_1$ 、 $L_2$ 、右のあるマスで $R_1$ 、 $R_2$ だった場合、 $L_1+R_1\le L_2+R_2\Leftrightarrow L_1-L_2\le R_2-R_1$ なら1行目で通るとわかる。左右で分離した式が得られたので、それぞれ求めてソートなどしておくことで計算できる。

寄与の係数を間違えているのになかなか気づけず、通ったのはコンテスト終了6分前だった。ギリギリ。結果は4完遅めの102位。

今日は実況を撮っていた。この後のCFまで間30分空いているのを振り返りで埋め、一つの動画として投稿する予定だったが、思ったよりARCが不出来だったのでたくさん話す気分になれない。手短にまとめていったん録画を終了した。

午後11時半からCF combined。今日はサイトが不調なのか提出が失敗しがちだった。再提出する前に本当に提出が失敗していたか確認を挟むとさらにページ読み込みの待ち時間が嵩んで苦痛。

Dashboard - Nebius Welcome Round (Div. 1 + Div. 2) - Codeforces

Aは何も考えず直前の移動も持つBFSを書いた。コンテスト後に改めて考えると、途中までジグザグ、残りは休みながら真っすぐ進むのが最適とわかり、 $|a|\le|b|$ として $|b|+\max(|a|,|b|-1)$ が答えになった。

Bは同じワクチンパックを使う人が区間になっているとしてよく、人 $l$ から $r$ までが一つの区間に入れる条件が $t_l+d+w\ge t_r$ と書ける。各 $l$ に対して最大の $r$ を求め、その $(l,r)$ だけ使う遷移のdpをした。後から貪欲でよいことを知った。

Cは $f=qn+r$ と表示して $\sum_{i=1}^f i\bmod n$ を計算すると $n(n+1)/2\times q+r(r+1)/2$ となった。よって $q=2$ とするのと $q=0$ とするので値が変わらないから、 $(q,r)=(0,0)$ が許されないことを考えても $1\le f\le\min(2n,p)$ の範囲で全探索すればよい。

Dはかなり難しかった。最小化のほうは11を貪欲に二人部屋で埋めてよい。足りない場合は残り一人部屋を埋めるだけなので必ず可能、足りた場合も一人部屋が十分な個数あるので調整が効き、矛盾が生じることがない。

最大化も実は00、01、10を貪欲に埋めればよかったらしいのだが、なかなか納得できなかった。左から順に一人部屋も使いながら貪欲して1WA、実装ミスでもう1WA。時間も30分以上かかっていた。

Eはそこそこスムーズに解けた。ループであってグラフの全頂点との距離が1以下になるようなものが必要で、それがあればループに適当に向き付けたあと残りの頂点からループに向かうパスをなもりグラフのように作っておけばよい。

ループの列挙は普通に書くと始点・終点・通った頂点集合の $n^22^n$ 状態持つ必要があって、遷移 $m=O(n^2)$ を込めて計算量 $O(n^32^n)$ になる。ここで始点をループの中で頂点番号が最も大きな頂点と固定すると、見るべき状態をかなり削減することができた。具体的には $\sum_{u=0}^{n-1}m2^u=O(n^22^n)$ の計算量。

計算量が悪い状態で一回提出しているが、こちらはそもそもループの復元にミスがあってWAだった。

Fは解けず。適当に選んだ1点から最も遠い頂点までの距離 $L$ を求めると、それが $d(G)/2\le L\le d(G)$ を満たすことはすぐ気づけた。二つ目の不等号は自明で、一つ目についてはどの2点も選んだ頂点を経由することで必ず距離 $2L$ 以下になることから従う。

この値をどうにか管理しようとしていた。最初に距離を求めたとき、使った辺を記録すると木になって、あとは木に辺を追加しながら最遠点を求め続ける問題になる。いかにもありそうだが、少なくとも手持ちの道具では不可能。直径はそう簡単に短くならないのではと考え、再計算するまでの間隔を指数的に伸ばす方針はWAだった。

適当にパラメータを弄って提出し、落ち続けるうちにコンテスト終了。5完遅めで順位は200位ちょっとだった。2930→2829(-101)。

Fをupsolveした。手に入れた値の上限が $2d(G)$ ではなく $d(G)$ であることのうまい利用方法が見つからなかったが、あったらしい。

$i\lt j$ に対し $d(G_i)/2\le a_i\le d(G_i)$ と $d(G_j)/2\le a_j\le d(G_j)$ が見つかっている状態で $a_i\le 2a_j$ が成り立つ場合、 $d(G_i)/2\le a_i\le 2a_j\le 2d(G_j)$ となってクエリ $i\dots j$ の答えを全部 $a_i$ にできる。クエリを半分に分割しながら計算する必要がある部分だけ再帰的に求めることで十分高速になる。