以下の内容はhttps://kotatsugame.hatenablog.com/entry/2025/12/29/205137より取得しました。

週記（2025/12/08-2025/12/14）

12/08(月)

この日にYandex Cupから帰国した。

kotatsugame.hatenablog.com

12/09(火)

仙台に着いてからのことを書く。

ゲーセンで20クレ遊んだ。素手でも調子は悪くなく、理論値が五つ出た。また木曜日に迫ったアップデートで消えてしまうマップを完走することができた。

午後4時前帰宅。いつも片づけるのが面倒で玄関先にスーツケースを数日放置してしまうが、今日はたまたま外から荷物を運び入れる用事があり、置きっぱなしは危険ということでテキパキ片付けることができた。

YouTubeで今年一年のアクティビティのまとめを見た。動画を投稿するたびタイムスタンプ作成のために自分で再生しているからか、競プロの動画を多く見ていると判定されていた。ちなみに一番よく視聴したチャンネルはチュウニズムの譜面保管所で、835本だった。

長い間PCを触りつつダラダラし、午後10時就寝。

12/10(水)

この日は丸一日寝ていた。連続して眠り続けられたわけではなく、ときどき起きてハーメルンを読んでいた。

日付が変わってから新刊チェックをした。11月末発売のラノベからチェックできていなかった。朝までかけて28冊注文。GA文庫の新刊がどれも予約サイトに登録されていなかった。たまにそういう登録漏れがあってもどかしい気持ちになる。また年末に出る「最強魔法師の隠遁計画」20巻は、予約してしまうと年が明けてからの受け取りになるため、自分で買うことにした。

午前8時半就寝。

12/11(木)

午後3時起床。シャワーを浴びて大学生協に向かい、今週末のAtCoder Japan Openに向けた新幹線の切符を買った。前泊と後泊を両方する予定のため、行きも帰りも時間に余裕がある。列車を決めるのも面倒なので自由席を買っておいた。

その足で登校し、院生室にYandex Cup土産を設置した。アレルギーのある後輩には、食べ物ではなくお守りを一つ渡した。消え物でなくても許されるくらい十分仲良くできているという認識。

学食で食事したあとうっかり院生室で寝ていたら、いつの間にか雨が降り出していた。夜中のコンテストのため、いざとなったら原付を置いて地下鉄で帰る覚悟をしつつ、とりあえず一時間ほど待ってみた。すると何とか晴れてくれたので、すかさず帰宅。

午後11時半からCF #1070 div.2。

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

Aは自分より左の最大値未満の要素を数える。Bはd=1の操作を繰り返すべきで、0のみからなる区間の長さの最大値が答え。Cは奇数の最大値一つと偶数全部の和が達成可能な最大。kに合わせ細かいところを丁寧に調整する。

Dは辺に対して値を持つようなdpをすることで、直前2項の値が取得できる。遷移は経由する頂点ごとにまとめて行う。aの昇順に頂点を見れば漏れは発生しない。

Eは各要素を消せる最小コストを考える。コスト側から見ると、a_i以下の値が連続する区間の要素はコストc_iで削除できるので、それぞれchminすることで求めるコストの列が得られる。そして総和から最大値を引いたものが答え。最初の列さえ求めてしまえばあとは区間ゼロ代入のクエリが飛んでくるだけなので、普通の遅延セグ木で解ける。

Fは\omega(a)\le 6なので、\omega(a_i\times a_j)の値ごとにすべて数えられる。約数包除によって\gcd(a_i,a_j)ごとに\omega(a_i)+\omega(a_j)を集計し、重複分を差し引けばよい。

1時間で全完して3位。

www.youtube.com

Discordでも今年一年のアクティビティがまとめられていた。今年はチームjapan406364961のサーバーで190時間通話したらしい。感想戦の時間も含め、コンテスト30回弱ぶん。毎週あるような気がするUniversal Cupだが、長めの夏休みがあったりして、一年間で平均すればおよそ隔週のペースになるようだ。

次の日の昼過ぎまで日記を書いていた。

ついでにハーメルン「幼女「もらえる経験値、人＞魔物では？」」を読了。立ち上がりは思っていたものと違い、雌伏の時がしばらくあったが、レベルが上がってからは大活躍。倫理観がいい感じに壊れていて面白かった。

syosetu.org

午後3時半就寝。

12/12(金)

午後7時過ぎ起床。すぐ荷造りして、AtCoder Japan Openに向け出発した。

仙台駅で列車を見繕い、自由席特急券を指定席券に変更した。現金払いで購入したからかクレカ専用機では扱ってもらえず、別の券売機に並びなおす羽目になった。noimiさんに渡すお土産を買って乗車。

午後10時に東京駅に到着し、すぐ渋谷まで移動。ホテルにチェックインした。入り口で偶然cn449さんと遭遇した。

部屋に荷物を置いたあと食事しようと出かけたが、夜遅い時間で居酒屋しか開いていなかったため、24時間営業の松屋で済ませた。昔、ICPCのときに利用した横浜駅近くの牛丼チェーンで信じられないくらい汚い器を出されたことがあり、それ以来すべての牛丼チェーンを十把一絡げにして避けているので、なかなかない機会。システムに慣れておらず恐る恐るの注文だった。

ホテルに戻ってベッドに倒れこんだらすぐに眠気がやってきたため、明日の準備はせずそのまま寝てしまうことにした。午前1時就寝。

12/13(土)

午前6時半起床。シャワーを浴びて、ホテル併設のコメダ珈琲で朝食を摂った。モーニングセットはサイズ控えめということか、若干物足りなかったが、追加注文はしなかった。

今晩はnoimi宅に泊まる予定なので、アメニティを自分で用意していく必要がある。すっかり忘れていたのでホテルの歯ブラシを持っていくことにした。しばらく日記を書いて過ごし、午前9時半ごろチェックアウトして出発。ホテルから会場の渋谷ソラスタまでは目と鼻の先だった。

AtCoder Conferenceと同時開催なのでたくさん人がいるかと思ったら、我々のほうが受付時間が早いようでほぼスタッフしかいなかった。コンテスト開始まではあまり時間がないし、話すような雰囲気でもない。

フロアに二つあるトイレのうち片方が壊れているとかで、コンテスト開始前にはConference参加者も使うはずのトイレを案内されたが、始まったあとはなぜかコンテスト参加者専用のトイレが使えた。

午前10時開始。

第二回 AtCoder Japan Open -決勝- - AtCoder

Aは部分列を連続部分列と誤読した人が多かったらしい。自分はこのミスはしなかったが、スコアがネストの深さの最大値と一致すると思い込んで、長い間上限・下限付きランダムウォークを考えていた。とりあえずで計算量の悪い解法を実装したら小さなサンプルから合わず、ここでようやく()()()のレベルが2であることに気づきひっくり返った。

そのあとはすぐ、前半に存在する開き括弧と後半に存在する閉じ括弧をK文字ずつにする解法が降ってきた。証明をしないままに実装したらサンプルが合ってくれて提出、AC。15番目だった。

次のB問題と心中した。最初は真面目に多項式補間することを考え、係数行列の逆行列を睨みつけてエスパーしようとしたり、ラグランジュ補間多項式に相当するものを見つけようとしたり、再帰的に構成しようとしたりしていた。おそらく二時間ほどかけたはず。結局どれも全くできそうな気配がなかった。

諦めて別方針をひねり出そうと試み、差分を取ることを思いついた。h(x+1)-h(x)=2^x(2f(x+1)-f(x))+g(x+1)-g(x)においてg(x+1)-g(x)はN-1次式になっている。N+1回差分を取ればgの寄与が消え、残ったN+1個の値について2^xを補正すると、通常の多項式補間でN次式が復元できる。これをF(x)と置こう。

あとは差分を復元すればよい。小さいNで手計算する泥臭い方法で係数を把握した。まずFの寄与は\sum_{x=0}^{X-N-1}\binom{X-x-1}{N}F(x)2^xであり、初項の寄与は\sum_{i=0}^N\binom{X-1}{i}\sum_{j=0}^i\binom{i}{j}h(j)(-1)^{i-j}らしい。後者についてはi回差分の初項をhの式に展開してある。この時点で愚直に計算してみるとサンプルが合ってくれた。

高速化をする。後者はすぐに畳み込みになったので、前者が問題。なにやらXがmodの値より少し小さいので、もしかしたらO(X)なのかとも考えたが、そんなことはない。\binom{X-x-1}{N}の扱いが肝で、これはxのN次多項式になっている。結局、多項式G(x)=\binom{X-x-1}{N}F(x)に対して\sum_x G(x)2^xを求めればよい。

残り時間が少ない。もう何もわからないので必死になってLibrary Checkerを漁ると、\sum_i r^i i^dが見つかった。これを項ごとに2N+1回解くのは無理だが、一縷の望みをかけてNyaanさんのライブラリを見に行くと、なんと求めたい式そのままでライブラリ化されていた。

$\sum_{i}a^i f(i)$ | Nyaan’s Library

これを貼ってみるとサンプルが合う。焦りを抑えて提出すると、なんとMLE。思わず中指が立ってしまった。コードを読み返すと、O(X)を考えていた時の名残でcombinationの前計算がXまで行われていた。呆れながら修正して再度提出し、無事ACできた。

残り10分で何かできるわけもなく、そのまま終了。結果はABの2完で13位だった。配点の小さいBを通しても入賞の可能性は全くないので、ずっと勝ちを諦めたムーブをしていたことになるが、個人的にはAのみ1完で終わるより良かったと感じている。

すぐ昼食休憩。西京焼き弁当と写真に写っている弁当、加えていくつかカツサンドが用意されていた。西京焼き弁当はマラソンのほうのトヨタコンで食べたことがあるはずなので、もう片方を選択した。

食後に会話を楽しんでいると鉢巻きが配られた。八色（ホワイト、エンジ、紺、レモン、若草、スカイブルー、オレンジ、藤）が三枚ずつ用意されていて、くじ引きのようにして引き、同じ色の人と三人チームを組んで余興に臨む。自分は藤色で、noimiさん、Rubikunさんと一緒だった。

鉢巻きの色がチーム名になっており、自分で入力してチームに参加する必要がある。しかし色がどれかわからなくて少し苦しんだ。驚かれてしまったので言い訳しておくと、色味が頭の中で想像できなくても本は読めるのである。

しばらくして表彰式。6位までの入賞者が呼ばれ、それぞれスポンサーから賞金パネルを受け取っていた。

写真撮影も終えて、午後3時40分からはまずは余興その一・パズル。競プロの問題が三問、文章を切り刻まれた状態で与えられるので、80分で復元して解く。

入力形式はすべて同じなのでそこから区別することはできないし、その上制約が若干異なる。問題名は「Chopsticks」「River」「Islands」で、それぞれ「箸」「橋」「橋」がひらがなに開かれていたため、文脈から推測して区別する必要があった。

チームメイトの昨年の経験から、まず机を広く使って文章の形式や登場する単語ごとに大まかに分類した。あとはすべての文章を見渡して、くっつきそうな断片を繋げ、いくつか塊ができたらそれっぽい問題文をひたすらエスパーする。最終的には、以下のような問題であると判明した。

Chopsticks：N本の箸があり、それぞれに長さa_iが決まっている。長さの差がK以下のペアを選び取り除く操作をできる限り繰り返したとき、残っている箸の集合としてありうるものは何通りか。

River：川の両岸を数直線と思うことにする。N人の人がいて、片方の岸の点a_iからもう片方の岸の点b_iへ移動しようとしている。両岸の同じ座標の点を距離0で結ぶ橋を、最大K本まで架けることができるので、全員の移動距離の総和を最小化せよ。

Islands：K個の島がある。N人の人がいて、島a_iから島b_iに移動しようとしている。島iと島i+1の間に橋を架け、人を適切に移動させ、架けた橋を壊すという一連の操作を、最小で何回行えば全員が目的の島へたどり着けるか。

制約は「Chopsticks」のみ準線形で他はO(N^3)。我々のチームは「Chopsticks」と「River」をACしたものの「Islands」は解けなかった。これは他チームも同様で、すべてのチームが問題文の復元は完了したらしいが、「Islands」にはACが出なかった。余興にしては問題が難しすぎる。昨年もそんな感じだったらしい。

2完が5チームいて、我々は3位だった。2位までのチームにはAtCoderカレーが配られた。AtCoder Conferenceのスポンサーブース巡りで得られるものと同じとのこと。

少し休憩して午後5時15分から余興その二・陣取り。ABCの過去問がA問題からE問題まで20問ずつ、10x10に並べられているので、40分でLockout形式の陣取りゲームをする。解くマスに制限はないが、得点は連結成分のサイズの最大値となる。盤面が狭いので、四チームずつに分かれて対戦した。

最初に真ん中あたりを狙い、声掛けして解く問題が被らないようにしつつ陣地を広げていくというのが基本戦略だった。しかし自分の声掛けが下手くそすぎて同じ問題を解く事態が多発。また気づいたら周囲を囲まれていて、かろうじて残された細い道を解き進んでいくしかなくなっていた。

盤面を横断し、他のチームをうまく締め出したチームに大差をつけられて負け。それでも2位だった。AtCoderカレーが配られるのは1位のチームだけだったので、どちらも惜しいところで逃してしまった。

1位のチームが確保した陣地をよく見ると、A問題やB問題が数多く含まれている。これはもう最初に狙った場所による運ゲーとしか言えないが、もしかしたら最初に連結性を無視してA問題だけ拾うというのも一つ良い手なのかもしれない。

余興が終わると、あとは何もイベントが用意されていない。即座に解散となった。懇親会がなかったのは、スケジュールを決めた時点では今日の夜中にMHC Finalがあったかららしい。AtCoder Conferenceのほうはすでに終了しており、人はあまり残っていなかった。

振り返ってみると、コンテスト参加者はAtCoder Conferenceからほぼ完全に隔離されていた。実況ルームの様子なども一切不明。またスポンサーは表彰式の間のみ部屋にやってきて、パネルの授与でほんの少しスピーチしただけ。さらにノベルティも存在せず、AtCoderカレーを逃した自分が手に入れたのは名札のみだった。しかしこの潔癖さこそ、全日本人対象のオンサイトコンテストに相応しいと感じる。

会場の外にはそこそこの人数がたむろしていた。ここで岩井星人さんを発見。参加者数名と握手しておられたので、自分も駆け込んで握手していただいた。他の人が会話する機会を奪ってしまった気もするが、少しだけご挨拶できて大変嬉しかった。

この件については以下の雑談配信で少し言及してもらっている。手が冷たかったのはよくわからない。手が柔らかいというのは単にお互いの握手の力が弱すぎただけであり、自分も岩井星人さんの手を柔らかいと感じた。

www.youtube.com

noimiさん、rin204さん、tute7627さん、Rubikunさん、Nyaanさんに加え駆け付けたrisujirohさんと七人で、渋谷で二次会。店は「天空の月」。同世代の競プロerの噂話やUniversal Cupの話をしたはず。

座席の時間制限が来て、午後8時半くらいに店を出ていかざるを得なかった。外は小雨が降っていて落ち着いてABCに参加できない。noimiさんの案内でいくつかのカフェを回ったが、週末の夜ということもありどこも満員。そのうちコンテストが始まってしまった。ABC436。

AtCoder Beginner Contest 436 - AtCoder

とりあえず歩きながらA問題をACしたが、その先は厳しい。なんとか「クリスピー・クリーム・ドーナツ」という店が空いていることを発見し、腰を落ち着けることができた。ただし席を使えるのが午後9時半までなので、30分で全完する必要がある。後ろのほうの問題だけ見た人から「Gは自明なのでいける」という励ましをもらい、以降の問題に取り組んだ。

B、Cはよい。DはBFSだが、最初に判定だけ行うコードを書いてしまい、いろいろ書きなおすのにかなり時間を溶かしてしまった。Eは典型。Fは明るさ最大の星を固定すれば数え上げられることに一瞬で気づくことができ、問題文の読解からACまで三分かからなかった。ここはかなり冴えていた。

しかしなんとGが解けない。このころには全員がGの概要を知り、みな一様に自明であると評価していたため、とんでもない勢いで煽られて大変だった。noimiさんがとても心配そうな顔と声色で「ChatGPTに聞きます？」と言ってきて、顔が引きつるのを隠せなかった。

またしても時間切れで机と椅子を失い、店の前の通路に座り込んでコンテスト続行。ついにBostan-Moriであることに気づいてACした。自明と聞いていたので自明な解法を探していたが、残念ながらBostan-Moriは自分にとってまだ自明な道具ではない。43分全完で31位。

しばらく立ち話をして解散。noimi宅に向かい、買ってきたパンを食べ、お土産を渡し、シャワーを借りて寝た。午前1時だった。

maspypy.com

12/14(日)

午前9時半起床。noimiさんと一緒に朝マックを食べた。朝は通常のバーガーメニューがないことに驚いた。「グラコロ」がグラタンのコロッケであることを知った。

noimiさんには今日も予定がある。東京駅で解散し、午前11時過ぎのやまびこの自由席に乗って仙台に帰った。

車内でハーメルンを二作読んだ。まず「ホビアニTCG世界でカードデザイナーやってるTS配信者」。この世界における主人公の重要さに比べて、普段の行動や付き合いのある人物の規模感が見合っていない。

syosetu.org

続いて「ホビアニ系TCG世界にTS転生したので、いっちょラスボスを目指してみる」。この設定で無敵じゃないのには驚いた。ライバル役が必要とは思えない。

syosetu.org

午後2時前に全体に到着。自分がいない間に雪が降ったらしく、路面がぐちゃぐちゃになっていた。

久しぶりにアンパンマン像の写真を一枚。近くに飾られていたクリスマスツリーなどを構図に入れようとした結果、像がメインには見えない写真となった。単に、アンパンマン像のある風景。

買いたかったラノベを探して本屋を五軒梯子し、メロンブックスでようやく発見した。

それからゲーセンで遊んだ。新曲「モニタリング」に粘着したが、疲れていたのか理論値は出ず。少し遅い曲で、譜面をガン見しているとどのタイミングで押せばいいのか分からなくなってしまう。目押しだけでなくちゃんと曲も聴くべき。かなり混んでいたので、8クレで退散した。

大戸屋で食事した。冬季限定「炭火焼きチキンのマスタードクリームソース」を注文。鶏肉の香ばしさが非常に嬉しかった。汁物も限定メニューのとん汁に変更してみたが、これはそこまででもない。塩味が強すぎる。

帰宅。ARC210の抽選に当たったようで、estieのTシャツが届いていた。

AHC058に少しだけ参加した。貪欲を提出。

ALGO ARTIS Programming Contest 2025 December（AtCoder Heuristic Contest 058） - AtCoder

川内キャンパス近くのセブンイレブンが12/18で閉店するという情報がTwitterで回ってきて、衝撃を受けた。これからどこのコンビニに行けばいいのだろうか。

午後7時から、運営に連絡して用意してもらった枠でUniversal Cupを走った。今日は9回目、Grand Prix of Jinan。

https://qoj.ac/contest/2693

書く

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



以上の内容はhttps://kotatsugame.hatenablog.com/entry/2025/12/29/205137より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14