週記（2024/12/16-2024/12/22）

12/16(月)

午後3時過ぎ起床。半からインターン先定例会に出た。

先週は1on1でタスクをいただいたのみで、まだ稼働できていない。勉強会は遅延セグ木＋AVL木で要素の挿入・削除操作を可能にするという話だった。すごい木を使う問題はUniversal Cupでたまに見かけるが、いつもNyaanさんにぶん投げて終わってしまう。

解散後に追加で1時間ほど1on1。別のタスクが降ってきた。数学的なことをやってほしいという感じだったが、専門が違いすぎてもう何にもわからない……。やるだけやってみようとは思う。

あとは週記を書いて、午後11時半くらいに投稿。全部書ききることができた。それから朝まで、本を2冊読んだ。

一冊目、「視線から始まる」。女性視点の学園恋愛小説。普通の女子高生と謳っておきながら実は校内で親衛隊ができるほど人気を集めており、びっくりした。また彼氏のほうの恋愛感情は一目惚れであることが明かされたが、彼女側がなぜそれに応えたのかよくわからなかった。さらにエピローグで急にオカルトな設定が追加され、これも謎。

二冊目、「才女のお世話」9巻。面白かった。選挙戦における主人公の振る舞いは、読者の自分からすると勝ち馬に乗ろうとしているようにも見えてしまうが、作中の学院生からはその仕事ぶりやこれまでの実績から好意的に受け取られているらしい。ずいぶんと立派になったものだ。

午前8時就寝。

12/17(火)

午後7時前に目を覚ましたが、セミナーのために論文を読んでいたら2時間ほどでまた寝てしまい、次に起きたら午後11時だった。セミナー資料を作ろうと机に向かったはいいものの、うっかりラノベに手を出してしまい、一冊読了。

「異世界転生したのでマゾ奴隷になる」。ハーメルンからの書籍化。面白かった。タイトルも表紙もいかがわしいし、内容もまあいかがわしい部分は多いが、それを補って設定と描き方がよい。主人公自身が自分の特別性についてかなり自覚しているのに、それでもなおめちゃくちゃな行動基準で動くところが好み。それにしても、イラストや本文の一部に白黒以外の色がついているという、この装丁への気合いの入りようは何だろう。

次のラノベに手を出し、結局セミナー準備が一切進まないまま午前7時半就寝。

12/18(水)

午後5時過ぎ起床。シャワーを浴びて大学生協に行き、ラノベを受け取って食事してきた。帰宅してから午後11時までかけて、セミナー準備を何とか完了。

ラノベ「屍王の帰還」2巻を読了。非常に面白かった。主人公陣営の強さを引き立てる設定・キャラ・描き方がどれも大好物。また、主人公が異世界人だというのを側近にもひた隠しにする理由として、1巻時点では「話すと仲間を失うから」としか言っていなかったが、その正確な事情が明らかにされた。主人公の不誠実さに少し引っ掛かりがあったので、解消されて良かった。

しばらくなろうを読み、シャワーを浴びて午前7時就寝。

12/19(木)

午前11時直前に起床。それから1時間ほど1on1をした。この1on1はタスクに関してではなく、最近どうですかというもの。和気あいあいと話して終了した。

この時期になっても仙台は雪が積もっておらず、それどころか今日は非常に良い天気であった。寒さは強いが原付で登校。

学食で食事して、午後1時半からセミナー。準備してきた内容を過不足なく話し、今日も2時間弱でまとまった。これが年内最後のセミナーとなり、新年は論文で参照されている別の文献の議論を追うところから始まるだろう。今日の論文については一段落したため、キリがよいと言ってよいのではないかと考えている。

談話室で小一時間過ごし、5限。今日は指導教員が同じ後輩がセミナーをした。二人のセミナーの日時がずれてから数か月経ち、ずいぶん久しぶりに聞くが、正直文脈がよくわからずあまり身が入らなかった。そもそも講義の一環とするのには無理があったのではないだろうか。

午後7時過ぎに終了して学食で食事。それから立体四目並べの実装をした。アルファ・ベータ法を実装したら探索が爆速になって、さすがにさぼりすぎだったと反省した。また、久しぶりに麻雀を1半荘打った。東1局でメンタンピンツモドラ赤の跳満を上がり、守り切って1着。

午後11時過ぎに帰宅。半からCGR28に出た。

Dashboard - Codeforces Global Round 28 - Codeforces

Aは操作1を操作2で再現できる。Bはkの倍数のindexに小さい値を置き、残りは適当に。Cは片方をs全体と固定してよく、もう片方のrを全探索できる。DはKevinが解けない問題だけ考える。より簡単なものはより多くの参加者に解かれてしまうため、それらはできるだけ使わないようにし、さらにどうしても使わなければならない場合は最小限のコンテストにまとめるとよい。

Eはなかなか思いつけなかった。2m本の辺を持つ色があるため、m\ge 2nの場合は不可能。そうでないときはできればパスを作りたい。ジグザグに張るのを適宜ずらしていくと上手くいくようだが理由は不明。

Fは最小値で分割していくと区間がO(n)個になり、それぞれ操作する回数に応じた達成可能な最小の最大値を持つと解ける。状態数がk:=1+\log\max aで、マージはmax-min convolution。O(k^2)かけたが、列が単調減少なのでマージソートっぽくO(k)になる。

Gは簡単。左辺をwと置くと、条件は\exists i.\;\forall j.\;a_{i,j}\le wかつ\exists j.\;\forall i.\;a_{i,j}\ge wになる。2重に包除原理を行うとO(vnm)が得られ、一番内側の計算を二項定理でまとめるとO(vn)になる。

Hには50分残せたが、まとめきれず。結果は7完55位でレート3081→3044(-37)。EとFでかなり詰まったのが苦しい。

www.youtube.com

その後Hをupsolveした。操作をする度に0の連結成分それぞれが一つ短くなるようなので、後ろから操作回数を持ちつつ、0が残る連結成分だけ伝って遷移するようなdpを行う。とりあえず計算量を無視して書いてみるとサンプルが合い、そこから遷移をまとめてO(|s|\log|s|)にしてAC。実はすぐO(|s|)にもなる。

なろうを読んだり日記を書いたりして、午前9時半就寝。

12/20(金)

午後2時半起床。登校し、午後3時から留学生のセミナーに出た。留学プログラムも折り返しを過ぎたが、自分と彼はセミナーが一緒でなかったため、何をしているのかいまいちよく知らなかった。

去年と同じ半年だけの留学プログラムで、今年は後輩が留学生のチューターを担当している。

週記（2024/10/14-2024/10/20） - kotatsugameの日記

今日は四色定理の証明において計算機を使う前のパートで用いる定義・定理とその証明をいくつか話してくれた。Kempe鎖を縦横無尽に用いる議論で、非常に面白かった。おそらくこれらをポスターにまとめるのだろう。余裕があれば実際に彩色を求めるプログラムも書きたいと言っており、かなり熱意があったが、ポスターセッションで見せられるような出力をさせるのはかなり大変そう。

午後5時半ごろ学食で食事し、院生室に戻って麻雀を打った。最初の半荘は親満を2回ツモられる立ち上がりだったが、そこから自分にもツキが向いてきて、最終的には何とかまくることができ1着。次の半荘は特に良いところがないまま、後ろの予定が近づいてきたため東場だけで交代し帰宅した。

午後11時直前に家に着き、Universal Cup 22回目、Zhengzhouセット。明日からICPCで家を空けるのでこの時間にずらしてもらった。CF div.2はお休み。順位表情報がないかと思いきやすでにHoMaMaOvOと03 Slimesが走っており、また現地チームも十分強かったので、問題選定に関してはそこまで大変ではなかった。

https://qoj.ac/contest/1873

書く

感想戦を終えて午前5時。それからシャワーを浴び、少し日記を書いて、午前6時に寝た。

12/21(土)

今日から二日間はICPC横浜地区大会。自分がsuzukaze_Aobayamaの、milkcoffeeさんがAobayama_Marinesのコーチを担当しており、共に現地にいた。

午前7時半起床。鬼のように眠いが何とか布団から這い出し、1泊分の荷造りをして出発した。先週の反省から今日はちゃんと「そばの神田」に行った。麺は同じくらい柔らかくても、より細いこちらはそれほどブニブニした感じがなく、食べやすい。

もうちょっと早めに駅まで来て、少し歩いて「そばの神田」に行くようにしたい。

週記（2024/12/09-2024/12/15） - kotatsugameの日記

思ったより早く着きすぎて、仙台駅で30分ほど暇になった。本屋を覗くと知らない新刊がいくつか。「新 謎解きはディナーのあとで」の2巻を見つけておったまげ、奥付を確認して9月に出ていたことを知りひっくり返った。もう初版は手に入らなそう。

www.shogakukan.co.jp

「ありふれた職業で世界最強」14巻も今月発売だったらしい。ついにアフターストーリーが書籍化される。こんなに良いものはほかにないから、すぐにでも手に入れて読みたい。なろうのほうは、実は途中で読むのが止まってしまっているが、最高だった。

over-lap.co.jp

元の世界に帰ってからの話も欲しかったなと思っていたら、アフターストーリーという形でなろうで連載が続いていると後書きにあった。それも刊行されるかも、とも書いてあったが13巻発売から1年経過して音沙汰がない

週記（2023/09/11-2023/09/17） - kotatsugameの日記

また「引きこもり姉ちゃんのアルゴリズム推理」が気になった。児童書らしいが、著者が井上真偽さんなので内容に期待が持てる。

publications.asahi.com

そうこうしているうちに新幹線の時間になった。午前9時半仙台発、午前11時東京駅着。車内では寝ていた。東北大勢はチーム6人＋コーチ2人全員この列車に乗っており、改札のあたりで合流して、それからはずっと固まって移動していた。

横浜駅で乗り換える際、駅ビルのレストラン街でいったん昼食とした。二グループに分かれて別々の店に入った。自分はそば屋。つい数時間前に食べたなあと思いつつ、軽めのメニューを注文した。それからみなとみらい線に乗り、日本大通り駅で偶然shinchanさんと合流しつつ、午後1時過ぎに会場に到着。

入り口前で案内していたnoimiさんを始めJAGスタッフには結構知り合いがいるが、明日のコンテストが終わるまで話しかけることはできない。参加者はもうわからない人ばかりだったため、このタイミングでの交流は全くせず、Tシャツを着てチームの写真を撮った後は配布物を読んでいた。

今年はチーム紹介ドキュメントでアスキーアートQuineをしているところがあり、大変感心した。ちゃんと変数名やコメントにメッセージが仕込んである。おそらく運営のミスでダブルクオーテーションが2倍になるなど表示が少し崩れてしまったが、チーム紹介スライドのほうではideoneのリンクも用意されていた。しかし残念ながらREになっている。

vYsfTL - Online JavaScript Interpreter & Debugging Tool - Ideone.com

このコードの作成者とコンテスト後の懇親会で話す機会があった。どうやら手元では動くらしく、ideoneの環境が問題のようだ。別のコード共有サービスを聞かれたので「Attempt This Online」をお伝えしたら、そちらでは無事動いたとのことである。ただリンクは信じられないくらい長くなっていた。

Attempt This Online

開会のあいさつといくつかの説明を聞いた後、リハーサル。当然やることはないので椅子で寝ていた。突っ伏す机がない状態で寝るのはかなり無理があり、体がぐらぐらしたりしてまともに休めなかった。昨年は寝ていたらうしさんに起こされたものだが、今年はスタッフとして来ていないようだ。

印刷物配布に来たうしさんに起こされてかなりびっくりした

週記（2023/11/20-2023/11/26） - kotatsugameの日記

チーム紹介では「HokkaidoDekkaido」の文字をはみ出させる演出、「TORA NI TSUBASA」のゴールドタイガー（英訳付き）、「SPJ」のキラキラ陽キャな雰囲気、前述のアスキーアートQuineを載せた「OSMA」、チーム名だけで面白い「I_do_understand_the_danger_of_overflow_and_really_want_to_use_32bit_integer」、丁寧に「にょ」の説明をしていた「tcknyo」が印象に残っている。

suzukaze_Aobayamaは、スライドに思いきり日本語が書いてあってあれあれと思っていたら、とりゐさんが日本語を話しだしてビビった。TUPCオンサイトの紹介を英語でしてもしょうがないというのは理解するが、スライドにくらい英訳を載せておいてもよかったのではないか。

午後5時半には解散。夕食は東北大勢揃って中華街に行った。今年はホスフィンがおらず、適切な店を選ぶ方法がよくわからない。適当に練り歩いて、店舗が大きそうな「福臨閣」という店に入った。時間が少し早いので8人でもすぐ入ることができた。

ターンテーブルがあって興奮したが、全員定食を注文してしまいシェアを行わなかったのでほぼ邪魔なだけだった。支払いもかなり安く済んだのでコーチ二人で出した。店を出るとき別の競プロerの集団を発見。kotamanegiさんを筆頭とした阪大勢に加え、別大学の方も少し混じっていた。

解散してホテルに移動。suzukaze_Aobayamaと自分は二俣川駅の東横インに泊まることになっている。毎年会場近くのスーパーホテルを使っていたが、今年は高すぎた。全員バラバラのホテルを取ったAobayama_Marinesにはスーパーホテルに泊まる人もおり、聞いてみたら2万円くらいしたらしい。

二俣川駅への移動は1時間ほどかかった。特に横浜駅でみなとみらい線のホームから相鉄線のホームに移動する際、非常に長い距離を歩かされた。明日はかなり早くホテルを出る必要がありそう。

午後8時くらいにチェックイン。二人部屋を二つ取っており、自分は仮の人さんと同室になった。ノーパソをセットし、順にシャワーを浴びて、午後9時からABC385に参加した。

UNIQUE VISION Programming Contest 2024 Christmas (AtCoder Beginner Contest 385) - AtCoder

Aは二グループに分けることだけ考えていたらサンプル2を見てびっくり。Bは面倒。Cは間隔を1\dots N-1で全探索したらN=1のときにループが回らず1WA。Dは(x,y)と(y,x)をsetで管理するとよい。Eは中心の頂点を全探索する。y=0を許さないように注意。

Fはまず何も考えずに二分探索を書いた。視点位置からビルの天辺までのベクトルを考えると、その向きたちが適切な順序で並んでいるのが条件。よって隣り合うベクトルの外積を計算すればよい。答えがピッタリ0になるケースと-1を出力すべきケースの区別が難しいと思い、そこだけは先に整数で処理した。ところがWA。

答えが大きくなるケースを用意して二分探索の範囲を変え何度か実行すると、誤差が結構大きいことが分かった。精度が足りないらしい。判定の式をよく見ると直接求まることが分かったので、それに書き直した。しょうもないオーバーフローで追加1WAしつつ何とかAC。

GはまずP_i=Nとなる位置を境に左右に分割してそれぞれ考えた。挿入dpが簡単に多項式になったが、よく見ると左右でマージすることができない。ここで両側一気に挿入dpで扱えることに気づき、\prod_i(1+ix+x^2)を求める解法を得た。

41分で全完し、3ペナで4位。Aのコードゴルフをしていたら、a\le b\le cとしてa+b=c,2cで判定できることに気づき、これを発展させて((a+b+c)\bmod{\max(a,b,c)})=0にたどり着いた。対称な式を得られたので、ソートする必要がない。

日記を書いてコンテスト終了を待ち、仮の人さんと問題について少し話して、午後11時就寝。

12/22(日)

今日はICPCのコンテスト当日。自分はコーチのゲストとして公式実況放送に出演することになっている。

午前6時半起床。ホテルで朝食を摂った。スープ・味噌汁の器が紙コップだったり、納豆が袋に入っていたりして、コスト削減にかける熱意を感じた。

午前7時半出発。今日の横浜駅での乗り換えは距離が非常に短かった。どうやら昨日は相鉄線から遠い改札から出てみなとみらい線から遠い改札に入ってしまったらしい。会場へは午後8時半過ぎに到着して、コンテストエリアに向かう人々を見送った。

今年のコーチ控室は同じ建物の302号室。参加者が全員揃うのが早く、コンテスト開始が15分前倒しされたようで、荷物を置いて一息ついたらもうコンテストが始まっていた。問題文もすぐ届いた。

30分くらいして配信部屋まで案内された。特に段取りなどは決まっておらず、時間があるときここに来て出演すれば良いらしい。自分は気合い十分だったのでそれからずっと配信部屋にいたが、最初の紹介のときド緊張してしまい、またICPCに関してあんまり話せることがないことに気づいたので、ほとんどの時間はカメラの裏で問題を解いていた。

www.youtube.com

以下、各問題について。

A、Bはよい。Cは実は10分くらい考えても解けず、先にnoimiさんが解説しているのを聞いてしまった。まあ入力がしっかり大きめで変なことはできないから、そもそも全域木を作れる方針というのに限りがある。Dは結構しっかり考えたのに最初の一歩すら踏み出せず、これも解説を聞いた。Eはやればできそう。

Fはかなり嫌。chokudaiさんが山登りで解けるということを主張しており、自分はそれに対して誤差がまずいのではと言ったが、そもそもコスト関数が変な形をしており運がよくないと通らないらしい。結局配信中は誰も考えなかった様子。しかし表彰式のときにtatyamさんがササッと通しており感動した。

Gはtatyamさんがかなり早期に解決した。自分は解法を聞いてフンフン言うだけで、実装が死ぬほど面倒であることに気づいていなかった。Hは概要だけ。Iは典型的だが、ライブラリがない状況だと少し面倒。自分だったらセグ木を写経するのを嫌がり、mapで単調増加列を管理するかなと思う。

Jも概要だけ。謎のYokohama Yellowが出てくるしY.Y.さん作問かな？と話していたが、懇親会で「自分が作った問題でそういうことはしない」と仰っておられ、確かにとなった。Kは概要を理解したあたりで配信席から「Kってなんだっけ」「あのゼータ変換みたいなやつ」という会話が聞こえてきて終了。しかしすべてYのケースがまずいことには気づけなかった。

Lはnoimiさん、potatoさんと考えた。まず解法は区間dp一択。区間をdisjointに取って残った部分をまとめることを考えると、lごとにrをインクリメントしながらもう一つdpを行うタイプの遷移かなと思ったが、計算量が全然ダメ。最終的にはnoimiさんが、操作できる回数の最大値を持てば分割位置を全探索する簡単な遷移でよいと気づいた。potatoさんが実装して無事AC。

Lがあまり解かれていないのは順位表マジックだ、と話していた。実際オープンのほうではDとどっこいどっこいの解かれ具合であった。

https://onlinejudge.u-aizu.ac.jp/services/room.html#ICPCOOC2024/ranking

凍結後の配信はすることがないから問題解説になるだろう、と聞いていたのに、順位表と選手の画面を見つつ話しているだけで終わってしまった。午後2時くらいにコンテスト終了より少し早く配信を締め、表彰式の会場に向かった。例年はそのままコンテストエリアで行われるが、今年は建物9階にある「横浜シンポジア」というホールで行われた。

今年もYes/Noは盛り上がった。「tcknyo」のNoがNyoになっており、丁寧。Objective-KUB1の凍結後3完の大躍進とScreenwalkersのJ単独ACは会場がざわついていた。suzukaze_AobayamaはちゃんとLが可能であることに気づいて通し、8完最速の7位となった。Aobayama_Marinesも前半6問をちゃんと揃えて24位。

午後5時前に1階に降りてきて懇親会開始。HUAWEIがかなりしっかりしたトートバッグとデカいぬいぐるみのついたキーホルダーを配っていた。

食事は今年も油っこいものだらけだった。夕食を別のところで取る予定はなく、またうっかり昼食を食べ損ねていたので自分も手を付けたが、一部のポテトが暖められておらず度肝を抜かれた。

あとはひたすら懇親。個人識別のためアイコンの描かれた名札としてTUPC2023のものを持ってきていた。それが功を奏したのかこちらに気づいて声をかけてくださる参加者の方がたくさんおり、動画や週記を読んでいると言ってもらえて非常に嬉しかった。また2ショットを依頼されることも多く、たぶん10回くらいは撮ったはず。有名人になった気分だった。

夏の学生最強コンでお会いしたテナガザルさんとも話せた。あの日のサイン色紙は、1枚を飾り、もう1枚を持ち歩いているらしく、今日もお守りとして持ってきたと聞いて感動した。

テナガザルさんに依頼され、色紙にサインを書かせてもらった。

週記（2024/08/19-2024/08/25） - kotatsugameの日記

午後8時前に会場を離脱し、ひとまず全員で横浜駅まで移動。そこからもう1泊する3人が別れ、5人で東京駅へ向かった。全員午後9時半のはやぶさに乗る。東京駅では30分くらい暇になって、改札を出て駅前広場に行ったり、駅構内の本屋に行ったりした。「ありふれた職業で世界最強」14巻を入手しようとしたが、そもそもラノベがほとんど置いてなかった。

新幹線車内では爆睡だった。仙台に到着するとわき目もふらずに地下鉄に乗り換え、午後11時半に帰宅。先週と同じ移動だが思ったより余裕がない。ともかくCF #995 div.3にはなんとか間に合った。

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

A、B、Cはよい。Dはaをソートしてiごとに二分探索。Eは値段としてaやbのみ考えればよい。全部まとめてソートし、適当に更新しながら計算。Fはジョーカーの位置がprefix、真ん中、suffixと高々三つの区間になるようだ。それらを愚直に更新。Gはヘビiの後ろにヘビjをどれだけ詰めて置けるかO(n^2 q)かけて計算し、その後O(n^2 2^n)のbitDPをする。

全完8位。

www.youtube.com

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