01/06(月)

午後3時過ぎ起床。半から今年最初のインターン先定例会に出た。昨年末に少し稼働したので話すべき進捗がある。勉強会は、実際に現場で行われた機械学習の精度改善手法について。数パーセントの改善をいくつも積み重ねている様子に圧倒された。

あとは先週の週記を書いて、日付が変わる直前に投稿。その後すぐにKUPCの分を追記した。

午前0時半就寝。

01/07(火)

夜明け前から寝たり起きたりを繰り返していた。起きている間はなろうを読んでいた。

エカスドクィナさんの昨年読んだネット小説まとめが投稿されていた。守備範囲が自分とほとんど重なっておらず、ハリー・ポッター原作の二次創作のみなのだが、その分野では以前投稿された同様のまとめ記事にかなりお世話になったことがある。4年以上前の話で、残念ながらもう削除されている。

sizu.me

毎月5日までに提出すべき書類（Googleフォーム）があって、指導教員の確認が必要なのだが、1日に送ったメールにまだ返信がなく困っている。
週記（2024/12/30-2025/01/05） - kotatsugameの日記

上の件について、ついに先生からメールが届いた。6日まで休暇だったそうだ。休暇でもメールチェックくらいしてほしいと思ったが、これはブラック企業的な思考だった。書類については提出先に状況を報告していたこともあってギリギリセーフという感じ。

午後9時前、ついに起床。合計の睡眠時間は12時間弱だった。

ICPC プレーオフの旅程についてsuzukaze_AobayamaのメンバーとZoomで相談した。ホテルについては三が日のうちにチャットで相談したので、フライトを決める。開催地・シンガポールは日本から南のほうにあり、時差は1時間だけだがフライト時間が7時間以上と長め。仙台空港からだとそもそも乗り継ぎでかなり待たされる便しかない。

羽田・成田からだと直行便がいくつかあるが、午前中に出るものは空港近くでの前泊が必要だし、仙台を朝出て間に合うようなものは今度はシンガポール着が夜遅くになって嬉しくない。どうしようもないので、前泊して午前中の飛行機に乗ることを選んだ。他大学のチームも同じ便に乗るらしいので安心、という側面もある。

LCCなので預け入れ手荷物についても確認しておく必要がある。大きなスーツケースだとそもそも現地タクシーに二つしか乗らないという噂もあったため、事前に荷物をマージしておいて二人分だけ払おうという話になりかけたが、HISというサイト経由で航空券を取ると一人あたり20kgぶん付いてくることが判明した。

【HIS】海外旅行・国内旅行の予約サイト

ところがこのサイトだと予約時に全員分のパスポート情報が必要らしい。実はチームメンバーの一人がまだパスポートを手に入れていないため、受け取ってから再度予約手続きを進めることにして、今日は解散とした。

そのあと航空会社の公式サイトで調べていたら狙っていた飛行機の席が残り少ないことが発覚。明日またZoomで集まり、HISで3人、別のサイトで1人ぶん予約することになった。

しばらくなろうを読んで午前1時就寝。

01/08(水)

午前3時半起床。朝までなろうを読んでいた。

シャワーを浴びて学食で食事し、ラノベを購入。その足で仙台駅前まで出て、航空券を買うための資金30万円をゆうちょ銀行から三菱UFJ銀行の口座へ移動させた。ATMの機能で送金するより自分で持ち運んだほうが反映が早いし、しかも手数料より地下鉄の運賃のほうが安い。

せっかく早い時間帯に駅前に来たので、mont-bellに入ってみた。このビル街にあって前庭を備えているのは驚き。原付に乗るときの防寒手袋でも買おうかと思ったら案外高かったので、尻込みして何も買わず店を出た。

仙台7年目にして初めてここのmont-bellに来た。前庭があるのは驚き pic.twitter.com/XZBfv5h7CJ
— こたつがめ (@kotatsugame_t) 2025年1月8日

イオンに寄りつつ正午に帰宅。すぐZoomを繋いで航空券を予約した。まずパスポートを持っていない一人の分を航空会社の公式サイトで取り、そちらが成功してから残り3人分をHISで取った。どちらも先ほど口座に入れた資金を使ってデビットカードで一括払い。公式サイトのほうはGoogle Payを経由して支払うと手数料がかからなかった。またHISのほうは謎のクーポンで5000円引きになった。

ついでに前泊用ホテルも予約した。成田空港近くに素泊まり4人部屋で16000円のところを見つけ、あまりの安さに仰天した。ド平日だとそんなものだろうか。さらにプレーオフの参加登録料も支払って解散。

眠かったので仮眠のつもりで横になったら、4時間も寝てしまった。午後6時に起きて明日のためのセミナー準備を開始。進めていくうち話そうと思っていた内容が全然足りないことに気付いたが、とりあえず午後11時過ぎの段階での資料をメールで送信した。

気分転換としてCodechef Starters 168に参加した。30分こどふぉったので別にタイミングが良かったわけではない。

https://www.codechef.com/START168A

書く

セミナー準備を再開し、午前8時に完了。すぐ寝た。

01/09(木)

午前11時半起床。昨夜作った資料をメールで送り、登校した。予報で天気が悪いことがわかっていたため、地下鉄で登校することは覚悟していたが、なんと雨ではなく雪が降っていた。ただこの時間は降り始めらしくまだ全く積もっていなかった。

学食で食事して午後1時半からセミナー。追加で準備した内容を合わせ、何とかいつも通りの分量のセミナーとなった。次に何をするか未定であること、また別件でテクニカルレポートを作成しないといけないことから、次回のセミナー日程を未定とさせてもらった。そのまま5限。今日は4年生が代数学の基本定理をいくつかの方法で証明してくれたようだが、眠気に負けてしまいあまり聞けなかった。

セミナー中からずっと雪が降り続けており、窓からも結構積もっている様子が伺えた。学食に向かうために建物を出たとき、写真を一枚。

pic.twitter.com/euKsPV8yhi
— こたつがめ (@kotatsugame_t) 2025年1月9日

夜は院生室でダラダラ。今年の箱根駅伝に出場した東大大学院生と、その給水係を務めた教授の記事を読んだ。D4と聞いていたのでやはり研究とスポーツの両立は難しいのかと思ったが、なんとこの箱根駅伝に出場するために卒業を一年遅らせたらしい。話題の給水シーンはテレビで見逃してしまったので残念。

news.yahoo.co.jp

また、久しぶりに立体四目並べの実装をした。アルファ・ベータ法にmove orderingを追加すると、まだほとんど練っていない順序でも驚くほど高速になってびっくり。これによって序盤の読み手数が他のAIに追いついた。ただし読み手の再利用をしていないため、中盤以降はまだ大きく離されている。

午後11時半に帰宅。なろうを読んで午前1時半に寝た。

01/10(金)

中途覚醒して2時間ほどなろうを読んでいた。午前11時過ぎに起床。シャワーを浴び、今日も地下鉄で登校した。雪はまだ降り続いている。

学食で食事して午後1時半から後輩のセミナー。論文の修正をしながら聞いていた。終盤詰まっていたので一緒に考えたものの、分野が違うため議論に慣れておらず、あまりまともなことは言えなかった。

3時間弱で終了。院生室に移動し、先ほどセミナー終わりに先生から解くよう言われていた教科書の演習問題について二人で考えた。午後6時半ごろ学食に行き、食事。

dcコマンドのバージョン1.5.1がリリースされたというメールが送られてきた。昔、コードゴルフ中に見つけたバグを報告した関係らしい。AtCoderの言語アップデート鯖に報告しようかと思ったら、そもそも誰もdc/bcを追加していなかった。自分ももうコードゴルフ熱が薄れてしまったし、なくなるならなくなるでいいか……という気持ちに。

昨日dc書いてるときに謎の空白が必要になってキレていた
— こたつがめ (@kotatsugame_t) 2020年5月14日

bug-dcにメール送り付けた
— こたつがめ (@kotatsugame_t) 2020年6月21日

院生室に戻って三人麻雀を打った。面子は自分、後輩、それにM2から一人。修士論文が大詰めの時期であるが、なんともう完成してしまったらしい。無理に誘ったわけではないことを強調しておきたい。

今日は劇的な局があった。先行リーチされて降りるつもりで手牌の対子を崩していたら、ドラを三連続で引いてきて四暗刻を聴牌。残念ながら上家にツモられて上がれなかったのだが、そのあとこんなの聴牌してたんだぜと手牌を見せ、戯れに次のツモ牌をめくってみたら、なんと当たり牌だった。みんなびっくりしていた。しかしこれでツキを全部使い切ったのか、最後は飛ばされて負けた。

午後10時半帰宅。2時間ほどなろうを読んで寝た。

01/11(土)

午前7時起床。

Rubikunさんが3か月ごとに集計しているCF div.2とECRでGP30を計算するランキングにおいて、昨年10月～12月の第12期で1位になった。3期から参加していて初めて。期間中、コンテストでの優勝こそなかったものの一桁順位を何度か取れたのと、他の参加者の調子が悪かったのが効いている。

R-18ハーメルン「ちょっと風紀のゆるいアナグラ」を読んだ。ゴッドイーターの二次創作は一時期読んでいた記憶があるが、ハーメルンのお気に入りを検索しても出てこない。どうやらどれも途中で読むのをやめてしまっていたようだ。

この作品と関係ない話をすれば、モンスターハンターだと古龍を主人公とする作品が大好きなのだが、ゴッドイーターのアラガミ主人公にはあまりそそられない。設定上、人類を攻撃せずにはいられないからだと思う。

syosetu.org

3時間ほど二度寝して午後2時からUniversal Cup。今日は25回目のHangzhouセット。

https://qoj.ac/contest/1893

書く

午後9時からはABC388に出た。

HHKB Programming Contest 2025(AtCoder Beginner Contest 388) - AtCoder

AはTUPCがサンプルにあってうれしい。Bは全探索。Cは尺取り。Dはimos法を更新しながら取得して線形時間で解いた。Eは小さいほうから $K$ 個と大きいほうから $K$ 個を組み合わせることになる。 $2A_i\le A_j$ となる最小の $j$ を各 $i$ について求めておけば、あとは算数で線形時間。 $j$ を求めるのには二分探索を使ったが、Cと同様尺取りでよい。

Fはかなり面倒。どこに移動できるかを幅 $B$ だけ管理し、悪いマスがない区間だけ適当に飛ばしていけばよいというのはすぐ分かるが、悪いマスが幅 $B$ の間に点在していたりするとかなり面倒。一度のジャンプで移動する必要があるかどうかを丁寧に考えながら実装したら何とか1発でACできた。

GはEとほぼ同様で、 $j-i$ の列に対し区間MAXを取ることで判定が行える。遅延セグ木を使うなりSparse Tableを使うなりすれば実装も簡単。しかし自分は累積MAXの列を無理やり管理してその上で二分探索したりしていたため、算数パートでやられてかなり時間をかけてしまった。大きめのサンプルがあって助かった。

62分で全完して21位。AのNibbles 8Bは1分差で負けた。

www.youtube.com

直前でマイク音量がやたら大きくなっていることに気づいたものの、調整している暇がなかったので、動画でも音が大きいままになっている。

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

01/12(日)

1時間の中途覚醒を挟みつつ午後8時起床。寝すぎ。シャワーを浴びて食事し、午後9時からARC190 div.1に出た。マイク音量は調整済み。

AtCoder Regular Contest 190 (Div. 1) - AtCoder

Aは簡単で、コスト2以下で達成できるケースを除いたら区間の状態が1パターンしかなく、区間が三つ以上あれば必ずコスト3で可能ということがわかる。コスト2のパターンは3通りあるため合計5通りとなり、それぞれ丁寧に実装したら問題なく通った。

Bはやたら時間がかかってしまった。マス $(a,b)$ を含むL型を固定すると、レベル $k-1$ までは単に4のべき乗、レベル $k+1$ 以降は上下と左右それぞれ二項係数を求めて掛け合わせれば場合の数がわかる。回転・転置を組み合わせることで、向きを固定したL型を左右にずらすケースのみ考えればよいことになった。

立式してみると二項係数の区間和が出てきて、これを計算する方法がわからず30分以上溶かした。しかし実は典型で、 $f(n,k):=\sum_{i=0}^k\binom{n}{i}$ から $f(n\pm 1,k\pm 1)$ を求めるのが定数時間で可能というもの。ずっと畳み込みのことを考えていた。

solved数を見てDに移った。整数なら $a^p+b^p\equiv(a+b)^p$ だが、行列だと非可換なので成立しない。非可換でも $p$ 乗する理論はあるだろうと思ってしばらく検索したものの、役に立つものは見つからなかった。

諦めて真面目に考えたら解けた。 $A_{u,v}=0$ なる $(u,v)$ に対し変数 $a$ と行列 $P=(\delta_{(i,j),(u,v)})_{i,j}$ を考え、 $(A+aP+\dots)^p$ を展開して $a=1\dots p-1$ などで和を取ったが、やっていることは解説と同じ。

$p=3$ がコーナーケースになることも気づいていたものの、実装が5分ちょっと間に合わなかった。AB2完の106位。Dで調べ学習しようとしていた時間が無駄。あるいは、読んでいたPDFに一度不定元を導入して特殊化することで等式を導く方法が書いてあったので、それを試してみてもよかった。

www.youtube.com

振り返りをギリギリで終え、午後11時半からはCF #996 div.2。

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

Aはお互い相手のほうにジャンプしてみて、それができなくなったほうが負け。まあこんな方法で判定するより $a-b$ のパリティを見たほうが早いだろう。Bは2種類以上のインデックスに対して操作するのが損。Cは $x=0$ とできるか考えてみる。 $n-1$ 行・ $n-1$ 列までは1マスずつ使って達成できて、このとき残りの1行・1列の和が等しくなっているため最後の1マスで両方揃えられる。

Dは大変。「カカシ $i$ が座標 $y$ にいて、カラスが座標 $y+k$ またはそれより右にいる」という条件のもと $y$ がとりうる最大値を時刻 $t$ に対して考えた。この関数は常にある1点 $(t,y)$ から傾き1で伸びる半直線の形をしており、カカシ $i$ の結果からカカシ $i+1$ についてが計算できる。また遷移をよく見ると $2t,2y,t+y$ が常に整数になっている。

Eは空にする順番を考えた。 $1,\dots,n$ の順とすると、まず $\sum a\le \sum b-b_n$ が必要。このとき $n$ 番目に全部押し付けることで必ず作業を完遂できることがわかる。

あとはコストの最小化だが、 $\sum_{i=1}^{k-1}b_i$ の容量に $\sum_{i=1}^k a_i$ だけ入れて、はみ出した分を $n$ 番目に押し付けるというのを $k=1,\dots,n$ で行うと考えると、 $\sum a+\max_{k=1,\dots,n}\left(\sum_{i=1}^{k-1}(a_i-b_i)+a_k\right)$ になる。2項目を最小化したい。

$(+1,+a)$ と $(+1,-b)$ を繋いだ折れ線の最大値だと思うと、この問題は見たことがあって、 $a-b$ の正負によって分けたあと適当な比較関数でソートするのが最適だったはず。すると最後の要素を全探索することもできる。ところがその比較関数を導き出すことができず、最終的にググってABC167-Fを見つけた。ちなみに、自分が見覚えあると言っていた問題はARC053-Cだったらしい。

$a-b\le 0$ のとき $a$ の昇順でよいことはほとんど明らかだったのだが、後から考えてみるとこれを用いて $a-b\gt 0$ のソート順も直ちにわかる。折れ線の終点も固定されているので反転して考えればよく、 $b$ の降順になる。

F - Bracket Sequencing

C - 魔法使い高橋君

Eに1時間以上かけたためFをやっている時間は残されていなかった。5完13位。

www.youtube.com

ARC-Cのupsolveをした。左上と右下からそれぞれdpしたテーブルを管理し、適当なところでマージする方針。更新クエリが変な形をしているので、dpテーブルの更新によって値が変わる範囲のうち、実際に再計算する必要のあるところは少ないだろうと考えた。

具体的には、マス $(x,y)$ を更新したとき、左上からのdpテーブルは $[1,x]\times[1,y]$ 、右下からのdpテーブルは $[x,H]\times[y,W]$ の範囲が正しい値になっているようにし、再計算が必要なマスを長方形領域の和として管理した。

遠くのマスの再計算が必要ならそのマスから今いるマスまで移動してくる必要があるから、ならしでクエリ $O(1)$ を達成できたかと思ったが、マス全体をぐるっと一周するように更新クエリが来ると全体を再計算する必要があるため、実際は $O(HW/(H+W))=O(\min(H,W))$ になって公式解説と同じ計算量のはず。しかし今のところFastestではある。

atcoder.jp

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