06/09(月)

水曜日までMidnight Code Cupでセルビア旅行。帰国時にロストバゲージした。

06/10(火)

06/11(水)

日付が変わる少し前に帰宅した。

旅行前から読み進めていたハーメルン「転生男の娘は道化の海賊を王にする」を読了。3年前に一度最新話まで読んだあと放置していたため、改めて最初から読み直した。もうエタっているが、原作開始前からスタートして頂上戦争までたどり着いている。

面白かった。主人公がバギーの腹心の部下として海賊団を超強化しており、原作開始前に五皇入りしている。これによる序盤のアレンジ、特にローグタウンでルフィを捉え、逃がす展開が良かった。

syosetu.org

午前8時就寝。なぜかセルビアにいたときより寝るのが遅くなっている。

06/12(木)

午後6時くらいに目を覚ました。今日は夜中にCFがある。夜はずっと布団でハーメルンを読んでおり、午後10時過ぎにうっかり寝落ちしたが、念のためかけておいた目覚ましが功を奏してギリギリで起床できた。

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

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

Aは出現回数を0回にすればよい。Bはrotateがしたい。reverse 3回による実装を思い出してみると、最後の1回、全体のreverseが不要なことに気付ける。Cは $a$ で立っていないbitを集めて貪欲。Dは信号に引っかかるタイミングと移動方向の $2n$ 状態で遷移を求め、ループに陥るか見る。Eは中央から縦横交互に長方形領域を拡張していくと通った。おおむね、直前に塗ったマスがチェビシェフ距離最大となるようにする。

Fは辞書順最小を正規形として実験していたが特に何もわからず。Eまで解いて10位。Fで正規形を考えるのは実は外れ方針だったようだ。

www.youtube.com

ハーメルンを読みふけり、午前11時就寝。

06/13(金)

午後5時半起床。布団で転がっていたらホスフィンから夕食に誘われたので、出かけた。

店は「玄米食堂番」。その名の通り玄米を売りにした店で、二人とも鯖の味噌煮定食を注文した。自分はご飯をお赤飯に変更。鯖は美味しく、また骨が取り除かれていて非常に食べやすかった。お赤飯と鯖の味噌煮を一緒に食べるのが難しいことに気づき急遽玄米ご飯をおかわりしたらフードファイトが始まりかけたが、何とか完食。

食事（+玄米大盛りおかわり） pic.twitter.com/VsgEIyvecv
— こたつがめ (@kotatsugame_t) 2025年6月13日

食後少し歩いてホスフィンと別れ、本屋に入って4冊購入。それから閉店までゲーセンで遊んだ。新曲埋めで14クレプレイ。

新しく追加されたものと最近通常解禁されたもので、Lv.15が新しく二つプレイできるようになった。「ひつぎとふたご」のほうは全部擦るとすぐSSSを出せた。85小節目が下手くそすぎたのでもうちょっと伸びると思う。「リ・フィクション・O」はラストが無理すぎる。非常に苦しい。

今日は14クレ pic.twitter.com/lXCu2Cq5CB
— こたつがめ (@kotatsugame_t) 2025年6月13日

ドンキに寄って、日付が変わってから帰宅。それからハーメルンを読みふけって正午くらいにようやく寝た。

06/14(土)

午後6時起床。布団でハーメルンを読んでいた。午後9時からABC410。

AtCoder Beginner Contest 410 - AtCoder

A、Bはよい。Cは配列のオフセットを管理。Dは $N\times 2^{10}$ 状態でBFS。Eは消費体力・魔力に対して何番目のモンスターまで倒せるか持つdp。

Fは適当に転地して $H\le W$ としておき、長方形領域の上下を決め打つと、横方向でZero-Sum Rangesをすることになる。値の範囲が $-HW$ から $HW$ であることから出現頻度を配列で管理することができ、 $O(HW\sqrt{HW})$ を達成できる。

Gは弦の削除操作を不要なものと勘違いして一度コードを書ききってしまい、かなり時間がかかった。円を適当に切り開くと、弦の両端点それぞれにおいて、重なる弦は入れ子の区間になっている。つまり逆に、入れ子になっている区間の集まりをdisjointに二つまで選べば、それと交わる弦が構成できる。prefixとsuffixそれぞれで入れ子になった区間の数の最大値を求めることができ、組み合わせれば答えが求まる。

38分で全完して11位。このうちおよそ半分の時間をGに消費している。

www.youtube.com

一昨日から読んでいたハーメルン「アイドルの世界に転生したようです。」を読了。昔から好きな作品だが週刊連載で進みが遅く、3年ほど放置していた模様。一念発起して読んでみると、その150話くらいでちょうど第八章から第九章までだったらしい。続き物の章だったこともあり、非常にタイミングが良かった。

内容もとても面白かった。もともと外伝『Days of Glory!!』としてオリ主たちのライブシーンが存在したが、これはあくまで外伝扱いで、本編ではなかったことに。それが、より大規模なライブが企画され、第八章はその準備、第九章は全編ライブの話になっていた。このあたりを一気読みできたのは本当に最高。

この作品はアイドルマスターシリーズ全体の二次創作としてかなり長い間連載されており、連載開始後に展開が開始されたブランドももれなく話に登場している。最近は学園アイドルマスターが有名だが、これもいずれ扱われるものと思うと今から楽しみ。

syosetu.org

東北大学からICPCに出場するチームが決定した。今年のコーチは自分と仮の人さんが担当する。割り振りを仮の人さんに決めてもらったので、担当するチームをICPCのサイトで作成した。今年は大学全体で7チーム、自分は3チーム受け持つ。

朝まで日記を書いたあと、ラノベ「二度目はタの付く自由業」を読了。

サブタイトルから装備と知識がチートなことは分かっていたが、読んでみるとジョブもスキルもチート。しかし天下御免の力を持ちながらもやたら慎重に強くなったり社会的立場を構築したりしており、その様子は楽しめた。ただ終盤の、ヒロインにちょっかいをかけてきた悪役を煽って決闘に持ち込みコテンパンにする展開は好きではない。主人公が理論武装しても相手の頭が悪いのを強調しているだけに見えていたたまれなくなってしまうことが、この作品に限らず多い。

寝る前に宅配便が届いて、何事かと思ったら自分のスーツケースだった。見つかったとの連絡自体は帰国翌日に受け取っていたが、そこから仙台まで運ばれてくるのにさらに二日ちょっとかかったことになる。これが行きで起こっていたら大変だった。ちなみにスーツケースは特に梱包などされず、持ち手にタグが結ばれただけの状態。まあそういうものか。

午前11時就寝。

06/15(日)

午後5時半起床。食事して、今日は午後6時からCF #1031 div.2。

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

$A$ は $x$ や $y$ の小さいほうを優先して使う。Bは縦または横のずれがシートのサイズの倍数になっているかチェック。サンプルが優しい。Cは2回目以降の爆破を必ず金を巻き込まないように行えるため、最初の爆破で消えてしまう金の数を最小化すればよい。

Dは自分が $k$ 回以上勝てる場合、相手の出すカードは $b_1,\dots,b_{n-k+1}$ のどれか。このうちの最小値に勝てるカードのみで、自分の山札の上から $k$ 枚を固められればよい。このことをすべての $k$ について判定した。二分探索すればもう少し簡単。

Eはかなり大変。答えは存在するなら $2n$ 以下なので、それまで毎秒どの頂点にいられるかを管理したい。当然、毎回全頂点から遷移していては間に合わないが、更新される部分をうまく取り出せば $O(nm)$ になるというのがポイント。なぜなら敵によって邪魔されるのは各頂点高々 $m$ 回だから。変なところで $O(\mathrm{deg})$ かけたりしないよう慎重に実装したら通った。

Fは簡単。唐突に辺 $a\rightarrow b$ としてグラフに言い換えてみる。すると、適切に辺の向きを切り替えて、入次数が正の頂点数と出次数が正の頂点数の和を最大化する問題となった。特に次数2以上の頂点が入る辺と出る辺を両方持つようにできれば最大値であり、これは次数1の頂点やサイクルに含まれる頂点を根としたdfs木に沿って向き付けることで達成できる。

1時間半で全完して3位。

www.youtube.com

続いて午後9時からARC200 div.2。

AtCoder Regular Contest 200 (Div. 2) - AtCoder

A問題から大変苦労してしまった。二つのベクトルが平行でなければ構成できるはずで、そのとき特に $N=2$ のケースを解ければ十分。ところがどうしても $A_1B_1$ のような値を使用したくなってしまい、 $X$ の値の範囲に合わなかった。

しかしこの制約は内積がオーバーフローしないためのもののはずなので、いくら何でもこれのせいで構築できないケースがあるとは思えない。冷静になってもう一度式を確認すると、二つの有理数の間にある有理数を構成すればよいことに気づいた。これはABC408Gでも見たやつで、分母と分子をそれぞれ足したものが適する。

これになかなか気づけないのはさすがに意味不明。図形的には、二つのベクトルの「間」にあるようなベクトルを90度回転させることで、それぞれとなす角を鋭角と鈍角にできるが、そのようなベクトルとして二つのベクトルの和が適するという話にもなる。

Bは適当に決めていったらできた。 $\max(A_1,A_2)\le A_3\le A_1+A_2$ が必要条件。 $\operatorname{lcm}(X_1,X_2)/X_2$ は「掛けると $A_2$ 桁が $A_3$ 桁になる数」なので、 $10^{A_3-A_2}-1$ としたい。 $X_1$ はこれと $10^{A_1+A_2-A_3}$ の積にすれば $A_1$ 桁になる。 $\gcd(X_1,X_2)=10^{A_1+A_2-A_3}$ より $X_2=10^{A_1+A_2-A_3}\times(10^{A_3-A_1}-2)$ としてみる。

これで全パターンチェックしたところ、 $A_2=A_3$ のケースだけ落ちたので、それは10のべき乗で自明な構築を与えておいた。

Cは区間の包含関係と $P$ の大小関係を整合させれば不満度の和が最小になる。辞書順最小化のためまず $P_1$ の最小化を考えると、区間 $[L_1,R_1]$ に含まれる人に優先して左の席を割り当てることになるが、これは一部の人を抜き出して同じ形の問題を解いているだけ。残りの人も同様なので、あとは再帰的に解ける。

毎回ソートしていても $O(N^2\log N)$ で、制約が $O(N^3)$ を想定していそうだから見落としがないか心配になったが、出したら普通に通った。

Dは実験。 $K=M$ は自明、 $K=2$ は $M$ が偶数のときのみで $\{0,M/2\}$ 、 $K=4$ は $M$ が4の倍数のときのみで $\{0,M/4,M/2,3M/4\}$ 。残りはなんと $M$ の値によらず同一の $A$ で構築できる。実際、 $\{0,\dots,(K-1)/2\}$ で $0,\dots,K-1$ が、 $\{0,\dots,K/2-2,K/2\}$ で $0,\dots,K-2,K$ が作れる。

Eは全体に $A_1$ をXORすることを考え、 $A_1=0$ として解く。このとき他の数のpopcountは2以下になるので、それらを頂点や辺だと思ってグラフ的にパターンを考えてみた。すると「頂点のみ」「ウニグラフとその中心」「三角形の辺のみ」「1辺と両端点」しかないことが判明。あとは重複がないよう丁寧に数えるとサンプルが合った。