以下の内容はhttps://kotatsugame.hatenablog.com/entry/2025/09/01/203030より取得しました。


週記(2025/08/18-2025/08/24)

08/18(月)

ふと目を覚ますと、午後3時半を数分過ぎたところだった。慌てて飛び起き、少々遅れてインターン先定例会に出席。数時間前に行った作業について報告した。

勉強会は定理証明支援系LeanとAIによる証明の自動生成の試みについて。機械が書いた証明なんて人間には読めなそうという偏見があるが、Chain of Thoughtを用いて生成させると思考過程では普通の自然言語が出てくるらしく、そこからアイディアを読み取ることができそう。またNatural Number GameというLeanで遊べるサイトが紹介された。

https://adam.math.hhu.de/#/g/leanprover-community/nng4

それからはずっと先週の週記を書いていた。午後11時くらいに投稿。あまりに眠かったので、Daily Akariの更新だけ待って寝た。

08/19(火)

午前5時くらいに目を覚ましてしまい、それから二度寝できずずっとハーメルンを読んでいた。午前9時前に布団を脱出。

今日から三日間、広島で開催される「離散数学とその応用研究集会2025」にオンラインで参加する。先月の学会でも会った人々が何名も集まるらしく、自分も来ないかと誘っていただけたのだが、昨年のように山形で開催されるならともかく、発表もしないのに広島まで出かけるのはさすがに気が進まず、オンラインにした。

JCCA-DMIA-2025

今日から三日間、山形大学で開催されている「離散数学とその応用研究集会2024」にオンラインで参加する。

週記(2024/08/19-2024/08/25) - kotatsugameの日記

発表を聞きながら休憩時間などに「波及効果」をプレイしていた。Puzzle Square JPにある問題のうち解いていないものは先週末の時点で残り二問、昨日週記を書いている間に一問解いたため、今日取り組んでいた以下の問題が最後の一問だった。先週の週記に書いた(n+1)\times mの典型では太刀打ちできず非常に苦労したが、何度も仮置きを行うことでかろうじて解き切ることができた。これにて全完。

puzsq.logicpuzzle.app

かかった時間をコメントしている人はいないが、解答記録を確認すると投稿からわずか15分で解いている人がいて衝撃的。何か見落としがあったかと思い、午後はずっと自分の解法を再検討していた。不要な仮置きを消したりいくつかマージしたりすることで、そこそこシンプルな手順まで整理することはできたものの、やはり2回程度の探索は必要に見える。

せっかく解法をまとめたので、Puzzle Square JPのほうにネタバレコメントの機能を使って書いておくことにした。実はパズルの作者以外が解法をコメントしているのを見たことがないので、もしかしたらマナー違反なのかもしれない。6年以上前に投稿されたパズルだし許してほしい。

研究集会初日の終了を見届けて、シャワーを浴び大学に向かった。お盆休みの間に駐輪場が草刈りされていた。

まず閉店間際の購買でラノベを受け取った。新刊チェックのときなぜか商品ページが見当たらず、予約できていなかったラノベが店頭に並んでいたため、これも購入した。食事と散髪を済ませて帰宅。

9月末に大阪大学で行われる「組合せ論的ホッジ理論勉強会(第1回)」に参加することを決めた。決心するのに時間をかけすぎたが、伊丹空港近くの東横インの喫煙ルームが一部屋だけ残っていたので、滑り込みで取った。

組合せ論的ホッジ理論勉強会(第1回)

午後9時就寝。

08/20(水)

午前2時に目を覚まし、朝までずっとPuzzle Square JPで「美術館」をプレイしていた。Daily Akariで鍛えているから自信があったのだが、星3くらいでも解けないものがあるうえ、コメントされている解答時間に追いつけない。プレイヤーの層の厚みが違いすぎる。

研究集会二日目の休憩時間にはラノベを読んでいた。「俺がシフトの時だけバイト先の喫茶店に来る、クラスの美少女モデル様」を読了。ヒロインが主人公に惚れ、ガンガン距離を詰めてきて付き合うところまで進んだ。あまりのスピード感に驚愕。ラノベ1冊分で一区切りつけるのを目標にしていたのかもしれない。

昼は学食に行った。ランチタイムの品ぞろえは相変わらず良くない。なぜ唐揚げカレーがあってカレーがないんだ。提供スピードを上げるためにメニューを絞っているものと思っていたが、客単価を上げるためではないかと邪推してしまう。週末の学生最強コンに向かう新幹線切符を買って帰宅。

午後の部の発表を聞き終えてからは夜中のコンテストに向けて仮眠をとった。ぐっすり4時間寝て開始直前に起床した。

午後11時半からCodechef Starters 200。200回記念でRated for all。日曜開催でもないし告知は今週月曜日だったし、重要なコンテストにしてはちょっと慌ただしい。

https://www.codechef.com/START200A

RESPALはabcabc...でよい。この文字列が長さ2以上の回文を含まないのは結構有名な話。MINSETはかなり苦労した。基本的にはA\oplus Bが2べきになるようなペアだけ選ぶが微調整の必要があり、小さいケースを手で試したり愚直の結果とにらめっこしたりしてそれっぽい式を見出した。

PERMCNTEZは0、1、2を適切な個数並べる。列を0の位置で分割すると各ブロックは非空で、1または2のみになるため、その配分を全探索。両端のブロックについても存在するかどうかをすべて試した。

LEXMATCHは前から見ていくと辞書順最大の部分列に含まれるインデックスが一意に特定でき、ここから各要素の大小関係が復元できる。特にこの大小関係は、不要な辺を除くと木構造になっているため、その上でdpをすればよい。等号があってもよいかどうかには注意を払う。

SSS7は大変だった。R_iは最後の区間を除き、L_iのみから定まる。L_iを左端とする長さK区間を取り出したとき、prefixの最大値がsuffixの最小値より小さくなるような最初の分割位置がR_iになる。これが求まれば、ダブリングで答えの含まれる区間まで移動し、Wavelet Matrixのk-th minを使うことで値を取得できる。ところがRを求めるのが難しい。

i=Lとし、A_iより小さな値を右K個から探し、そこまでの間に存在する最大値の位置を新しくiとする……というのをダブリングで繰り返す方法を実装したが、ランダムケースで落ちてしまう。仕方ないのでこちらでもWavelet Matrixを持ち出し、「右K個」をちゃんと「L+Kより手前」にして正しい分割位置が見つかるまで繰り返してみると、何とか通ってくれた。計算量は不明。

残り時間でEVADEROBOTに取り組んだが間に合わず、5完14位。SSS7でRを求めるには、例えばsuffixの最小値を固定すると良かったらしい。これで分割位置とLとして可能な区間が決まり、区間chminで集計する。

コンテスト終了から15分程度でEVADEROBOTが通った。ロボットの周りをウロチョロすると避けやすいと思い、辺uvに対して「ロボットがuにいてChefがvにいる」「ロボットがuにいてChefがv以外の隣接点にいる」という状態を定めdpを書いた。後者は、前者の状態からロボットがvに移動するときに必要となる。

dpの初期化は、Sからロボットの隣接点までの距離が経過ターン数以下になった瞬間そこまで駆け付ければよい。複数ある場合はそもそもループへ逃げ込めるため勝ちであり、どこでもよい。また遷移を素直に書くとO\left(\sum_u\deg(u)^2\right)となってしまうため、適宜まとめる必要があることに注意。

レート更新がバグっており、参加者全員240まで叩き落されてしまったが、翌朝には直っていた。2986→2969(-17)。

別のラノベを開いたら止まらなくなった。午前7時就寝。

08/21(木)

午前9時前にスマホに電話がかかってきた。常時マナーモードのため出損ねるかと思いきや、奇跡的にスマホの上に手を置いたまま寝ていたため、振動に気づくことができた。少し通話して二度寝に入った。

午前10時に起きて研究集会最終日に参加。今日も空いた時間にはラノベを読んでいた。

「俺は星間国家の悪徳領主!」10巻を読了。非常に面白かった。ロゼッタの言葉が主人公の琴線に触れ、ついに結婚を受け入れるという展開。ところで、このシリーズは巻の前半で主人公が悪意に晒され、後半で巻き返すという流れが典型化している。前半はどうしても辛い場面が出てくるが、後半まで一気に読めば気分爽快間違いなしのストーリー。だからこそ昨日もそこまで読んでから寝たのだった。

午後の部まで終えて4時間ほど仮眠をとり、午後11時半からCF #1043 div.3。

Dashboard - Codeforces Round 1043 (Div. 3) - Codeforces

Aはよい。文字と文字列がこの順で足し算できることを、なぜか知らなかった。Bは\frac{n}{10^k+1}を列挙。C1はnを3進法で表記する。C2はx+1で1回取引する代わりにxで3回取引すると得する。特にxが大きければ大きいほど得も大きくなるため、上の桁から貪欲ができる。

Dは算数でk番目の文字が含まれる数の桁数を特定し、次に実際の数値を特定して、桁和を計算する。桁和の部分まで算数しようとしてとんでもない時間を消費してしまい、結局桁dpで解いた。10^k\dots 10^{k+1}-1の桁和の和だけは算数で求めていたが、振り返ってみるとこれも桁dpにまとめてしまってよかった。

Eはabを混ぜて降順ソートし、すべて使う位置を二分探索で、aまたはbだけ使う位置を算数で求めて解いた。実際のところ二分探索は不要で、x個目のay個目のbの位置を見ればよい。

Fは1からnへのパスに含まれる橋で最も近いものを探す問題。列挙して、距離と橋のインデックスをコストとしたdijkstraを行った。BFSでよい。

Gは盤面の中に縦横それぞれ軸を設定し、ひっくり返して重なる範囲が一致するかをチェックする。縦の軸2m-1通りを定めると各行でどの区間がチェックの対象になるかわかるため、あらかじめ抜き出してZ-algorithmを計算しておけばチェックがO(1)になる、と思ったが文字列の長さがO(nm)になるため到底間に合わない。行ごとにロリハでハッシュを計算し、それを用いることで長さO(n)にできる。

2時間弱で全完して12位。

www.youtube.com

夜中から朝にかけてはまたラノベを読んでいた。「俺は星間国家の悪徳領主!」11巻を読了。主人公の必殺技が強すぎて最近は機動騎士の動きが追い付かず、足枷になってしまっていた。今巻では不思議な力で機体性能が大幅に向上し、ついにフルパワーで放つことに成功。コックピットの中から機体をすり抜けて攻撃することはできないのだろうかと思っているが、そういうことをしてしまうといよいよ機動騎士が不要になって、作者の趣味的には嬉しくないのだろう。

午前11時就寝。

08/22(金)

午後4時起床。シャワーを浴びて大学生協に向かい、ラノベを買って食事してきた。一旦家に帰り、今度はゲーセンに行った。

閉店まで23クレプレイ。成果はいろいろ。

「Unwelcome School」ULTの66小節は五鍵と見て親指を使うのではなく、四鍵の一打目をベチャ押しすればよいと聞いたが、これが大成功。他の鍵盤も軒並み上手くて99AJが出た。

最終鬼畜妹フランドール・S (Chroma Remix)」は曲が好き。ラスサビ前のピロピロしているところが特に良い。絶対にAJ出すぞと思っていたがラストの鍵盤が全く認識できず、今日までかかった。

改めて譜面画像をガン見してからプレイすると、相変わらずよく分かってはいないもののなぜか通ってびっくり。もしかしたら一瞬のボーナスタイムだったのかもしれない。ともかくその間に決めきることができたのでOK。精度はかなり上振れてくれた。

「うい麦畑でつかまえて」は譜面動画も見ていない完全初見のプレイで理論値が出た。途中でタップスライドが降ってきて腰を抜かしかけたが、黄タップとフリックに挟まれて赤タップは二つしかなかったため、綺麗に通った。

「きゅびびびびずむ」は「きゅびずむ」を切り貼りして作られた曲らしく、その再現で譜面も共通している部分が多い。譜面動画だけ見ると意味不明だった配置も「きゅびずむ」のほうをプレイしてから臨むと案外簡単だった。敷地帯については手の動きが大体同じになっている。

また、新曲「1番輝く星」の途中でインド人の譜面が降ってきてびっくりした。「ロシデレ」だからインド人なのかな、とか考えたが、曲をよく聞くと「右に行って!」と歌っており納得した。

立ち食いそばを食べて帰宅。シャワーを浴びたあと日記を書き、午前4時半に寝た。

08/23(土)

午後1時起床。しばらく日記を書き、午後3時からAHC052に出た。

AtCoder Heuristic Contest 052 - AtCoder

最初の1時間はずっと方針を考えていたものの、何も思い浮かばなかった。適当に操作しているとロボットが壁の近くに固まってしまうはずなので、まず塗りきることを目指さなければならない。盤面を長方形に分割してロボット1台ずつに担当させることを考えたが、ちゃんと端に壁がないと途中で領域をはみ出てしまうし、そもそもスタート地点まで各ロボットを動かすのが難しい。

どうしようもないので、複数台のロボットを同時に活用しようとするのは諦めた。まだ塗っていないマスに最も近いロボットを1台選び、そこまで移動させることを繰り返す。このアルゴリズムを固定し、キーコンフィグはランダム生成して最良のものを選んだ。提出すると330453点・平均操作回数497回で、案外少なくなってくれることに驚いた。

ボタンを選ぶ際できるだけ多くのロボットがまだ塗っていないマスに近づけるようなものを選ぶと、354819点・平均操作回数335回まで伸びた。ここで定数倍高速化を行い、356942点・平均操作回数320回になった。

キーコンフィグのランダム生成を1点変更の山登りに変えることで360456点・平均操作回数297回。このタイミングでStay操作を入れてみて、手元のシード0のケースでは改善したのだが、他のケースも試してみると軒並み悪化しておりびっくりした。以降もStay操作は抜いている。次に山登りを焼きなましにするもほとんど伸びず、361076点・平均操作回数293回。

そこからさらに定数倍高速化し、特に序盤の無駄なBFSを省いたところ、スコア計算の回数が800回から1600回へ倍増したのだが、なんとスコアが下がってしまった。おそらくキーコンフィグの1点更新は近傍として遠すぎるのだろう。スコア計算の差分更新もできそうにない。

最終スコアは361076点で173位、パフォーマンス1794、レートは+3。しかし減衰分と打ち消しあって、値としては2222のままだった。

あとは夜中までずっと日記を書いていた。明日は学生最強コン、明後日は後泊で今週分の日記を書いている暇がなさそう。一区切りつけ、コンテスト参加のための書類を用意して午前3時半くらいに寝た。

08/24(日)

午前9時前に起床。荷造りしてすぐ出発した。立ち食いそばを食べて新幹線に乗り、正午前に東京駅に到着。

時間があったので東京ラーメンストリートに08/07にオープンした「みそきん」の実店舗を見物しに行った。立ち止まっての写真撮影が禁止されていたため、自分も写真は撮れず。予約制にもかかわらずいくらか行列ができていたので、そもそもカメラを向けていられるような混雑状況ではなかった。まあ見られただけでも嬉しい。

昨年同様に西新宿駅から徒歩で会場へ向かい、午後1時前に到着。受付を済ませたあとはコンテスト開始まで他参加者と交流していた。いつもの勢とRayan Programming Contestについて話し、参加登録すると抽選でTシャツがもらえることを知った。またkidodesuyoさんに声をかけていただいた。

午後2時10分からコンテスト開始。問題に集中すると気にならなくなったが、開始前は会場が寒くて震えていたので、来年は羽織るものを持っていくべきだろう。

第六回日本最強プログラマー学生選手権 -決勝- - AtCoder

Aでかなり手こずってしまった。2進数の各桁ごとに見ること、少なくともX回開催できるようにすることはよいが、X+1回開催できるかを正確に判定するのが難しい。何か2値のフラグを持ってdpするのだろうというところまでたどり着いても、状態の定義で外れを引きまくった。

最終的には上のbitから見て、各Div.をX+1回ずつ開催できるだけの問題案を確保した状態で一つ下の桁で使える余裕を持ち、dpを行った。問題案が足りなくなった場合は1回余分に開催していた分を開放し、それを行ったというフラグを持つ。50分以上かけて何とかACできた。

コンテスト後にRubikunさんの解法を聞いて気付いたが、「X回以上開催できる」場合の数から「X+1回以上開催できる」場合の数を引く方法でも解ける。2進法で見る桁をK+10くらいまでに制限しているため、場合の数が有限になる。

順位表情報が十分あったため、solved数を見てCへ進んだ。こちらはすぐ解けた。任意のLに対してB_2,\dots,B_N\le Lとなる場合の数を数えられれば、それが0でない最小のLを二分探索で求めることでf(X)の最小値、さらに答えまでわかる。

あとは数え上げ。k\max(X_1,\dots,X_k)-\min(X_1,\dots,X_k)さえ持てばdpの遷移ができることに気づいた。状態数O(N^2)、遷移は愚直に書いたO(N)が累積和で直ちにO(1)になった。ずっと\bmod Pで数え上げるのは怖かったため、二分探索時は\bmod 10^9+771を採用。これで通ったが、D問題を確認したらHackケースの構築が出題されていて肝を冷やした。

次はB。まずX=Yの場合を考えると、(1,2)(2,1)を必ず同数使うため値1・2・3を取るパラメータ一つの問題に帰着できる。冷静になるとX\ne Yの場合も必ず使う問題案があって、それを除くとX=Yのケースに帰着できる。

答えを二分探索することにすれば状況はさらにシンプルになり、「値i=1,2,3の問題案がA_i個あるとき、和Xt個作れるか」という判定問題を高速に解けばよいことになった。自明な条件としてA_1+2A_2+3A_3\ge tXがあるので、他の条件を探る。

A_3=0のときを考えると、思ったより簡単になった。Xが偶数なら追加の条件なし、奇数ならA_1\ge tである。よってできるだけXを偶数にしながらA_3を割り振る問題となる。Xが奇数なら最初に1個ずつ割り振り、あとは2個ずつ割り振ってみる。\left\lceil\frac{tX-A_1-2A_2}{3}\right\rceil個割り振れればそれでよいという事実も、考えることを減らしてくれた。適当なメモ化再帰で愚直を書いてチェックするとなんと一発で合い、そのままAC。

順位表を見るとRubikunさんに4秒差で負けていた。残り70分もあるし後ろの問題を解いて巻き返し、と思ったらどれも全くわからない。凍結前の時点で唯一解かれていたEを見て平方分割方針を考え、何もできなくて投げ出したあとはDで適当な乱択を回し続けていた。そのままコンテスト終了。

優勝は凍結前にAとEの2完で、その後Cも通したさすがのyutaka1999さん。自分は4位。一つ上と僅差だったのは悔しいが、14人いるABC3完の中で3人目だし下も結構詰まっていたので、これ以上遅れなくて良かったなと思った。2位のpotato167さんだけ別次元の速度。表彰式では、例年とは異なり10位以上の全員がコメントを求められてびっくりした。

懇親会では今年も、AtCoderノベルティをもらうため真っ先にスポンサーブースをすべて回った。今年のノベルティはトートバッグではなくラバーストラップだった。毎年来ている身としてはダブりがなくて良い。また食事もかなりしっかり食べた。特にカレーが最後までずっと供給され続けており、食べ物がなくならなかったのが嬉しいポイント。会話については、珍しいことにsnukeさん・青木副社長と話した。

ホテルにチェックインして、午後9時からABC420に参加。

AtCoder Beginner Contest 420 - AtCoder

Aはよい。Bは何もかも面倒だが列ごとに集計するのが一番面倒。Cは差分更新。DはBFS。EはUFに黒色の頂点の数も持たせる。

ここまでは順調だったのにFとGですべてが崩壊した。FはO(NM\min(N,M))しか思いつかない。ひとしきり苦しんだあと順位表を見るとGがそこそこ解かれていたので、そちらに移った。

いくらか試行錯誤したのち、\sqrt{n^2+n+X}=n+kと置くとn=\frac{X-k^2}{2k-1}と表せることに気づいた。この状態ではkの範囲が不明。しかし実験してみると、n-n-1のどちらかはO(\sqrt{|X|})程度のkに対応するようだった。何も証明していないが、余裕を持った範囲を調べると小さいケースで通ったため提出。なんとかACできた。

この解法の正当性については、その後MMNMMさんが書いてくれていた。

Editorial - AtCoder Beginner Contest 420

Fに戻る。どうしようもないのでQCFium法でO(NM\min(N,M))を通す努力をしてみることにした。この場合、下手にまとめて処理しようと複雑なことをするのはかえって逆効果。愚直に書いてみると一番内側のループが実行順によらない、完全に並列化可能な形となり、また定数倍に2分の1がついて、手元では1.3sec程度だった。

一応コードテストで最大ケースを試そうとしたが、このころにはジャッジが詰まりまくって結果が一向に帰ってこなかったので、エイヤと投げてしまった。ジャッジは手元よりさらに速く、無事1.1sec弱でAC。69分全完の20位、BANが終わると14位になっていた。上位勢が軒並みいない中でこの順位はかなり不甲斐ない。

シャワーを浴びて午後11時半からCF #1044 div.2。もうだいぶ眠くてヘロヘロの状態だった。

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

Aは最初と最後のギア比を同じにできればよい。Bは降順ソートして二人ずつ友達にしていくコストが下界で、あとはg=0の人同士を結べば達成できる。

CはS={1,\dots,n}として始点をすべて試す。返ってくる値でグループ分けすると、答えとなるパスはそれぞれから1点ずつ選んで並べたものになるため、辺の有無を高々n-1回聞けば一つ構成できる。

Dは、一度下に落ちたスタックは下から順に倒していくものとしてよい。そうでなければ、同じ操作を下に落ちる前に行っておくことでよりダメージを稼ぐことができる。あとは上にいるモブを落とすためにどのモブを倒すかdpで決める。

Eはかなり苦しんだ。高々n/4頂点選び接続する辺を削除することで、残った連結成分がすべてパスになるようにできればよい。適当に根を取って、葉から順に「子が三つ以上ある点」か「子に『子が二つある点』がある点」を対象に操作していく。どちらの条件も特殊な位置関係にある四つの点を前提としているため、選ばれる頂点は高々n/4個になる。

Fは爆破範囲に包含関係のあるクリーパーを選ぶ必要はないため、選ぶクリーパーを順に並べると爆破範囲も順にずれていくような形になる。またこのとき、隣り合うクリーパーの爆破範囲に互いが入るようなことがあれば矛盾するが、逆にそうでなければ可能な爆破順序が存在する。

クリーパーiの次にクリーパーjを選べる条件を式で整理すると、セグ木の1点更新・区間取得や区間更新・1点取得で書ける形になるため、実家dpができる。あとは爆破順序を適切に定めるだけ。ところがなぜか合わず、そのままコンテストが終了してしまった。

5完5位。順位だけは立派に見えるが、それは上位勢がここにもいなかったからで、このセットで全完できなかったのはかなり出来が悪い。FのWAは爆破順序を正しく求められていなかったのが原因だった。

午前3時就寝。


ところで、日曜夜のコンテストに上位勢がいなかったのは、午後8時からUniversal Cup Semifinalsがあったからである。実は我々japan406364961は一部の問題のwriterを務めており、そのため不参加だった。

このことを馬鹿正直に言いふらすことはできないため、学生最強コンでは「チームメイトに用事があって後日バチャする」と真っ赤なウソをついていたし、6月頭のMidnight Code CupでRubikunさんにSemifinalsの話題を振られたときも、risujirohさんと一緒になって素知らぬふりをしていた。

https://qoj.ac/contest/2506

The 3rd Universal Cup Semifinals Analysis (Draft) - Blog - Qingyu✨'s blog

チームで作問したといっても、実のところ自分がしたのはNyaanさんが作った問題のテスターだけ。H問題「Shortcut on Tree」の解法が想定解に採用され、writerにも名を連ねさせてもらえた。risujirohさんの問題もあるがそちらは結局ノータッチで、申し訳ない。




以上の内容はhttps://kotatsugame.hatenablog.com/entry/2025/09/01/203030より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14