読書記録(2024)

kotatsugame.hatenablog.com

1月

  • 12日
    推しにささげるダンジョングルメ01
  • 14日
    性別不詳VTuberたちがオフ会したら俺以外全員女子だった

2月

  • 2日
    放課後、ファミレスで、クラスのあの子と。
  • 21日
    一生働きたくない俺が、クラスメイトの大人気アイドルに懐かれたら5
    双子まとめて『カノジョ』にしない?2

3月

  • 20日
    アルゴリズムの乙女たち
  • 22日
    玄関前で顔の良すぎるダウナー系美少女を拾ったら
  • 23日
    物語に一切関係ないタイプの強キャラに転生しました

4月

  • 10日
    迷宮狂走曲2
  • 11日
    凡人転生の努力無双
  • 14日
    凶乱令嬢ニア・リストン4
  • 15日
    凶乱令嬢ニア・リストン5
  • 16日
    S級冒険者が歩む道2
  • 20日
    無能と言われ続けた魔導師、実は世界最強なのに幽閉されていたので自覚なし4
  • 21日
    家事代行のアルバイトを始めたら学園一の美少女の家族に気に入られちゃいました。
  • 23日
    国歌を作った男
  • 24日
    怠惰な悪辱貴族に転生した俺、シナリオをぶっ壊したら規格外の魔力で最凶になった
  • 27日
    スクール=パラベラム2
  • 28日
    魔王の元側近は勇者に転生しても忠誠を捧ぐ
    許嫁が出来たと思ったら、その許嫁が学校で有名な『悪役令嬢』だったんだけど、どうすればいい?4
    ツンな女神さまと、誰にも言えない秘密の関係。
  • 29日
    バスタード・ソードマン3
  • 30日
    やる気なし天才王子と氷の魔女の花嫁授業
    依存したがる彼女は僕の部屋に入り浸る2

5月

  • 1日
    現実離れした美少女転校生が、親の決めた同居相手で困る
  • 2日
    平民出身の帝国将官、無能な貴族上官を蹂躙して成り上がる
    戦地から帰ってきたタカシ君。普通に高校生活を送りたい1
  • 4日
    冬季限定ボンボンショコラ事件
    最強魔法師の隠遁計画18
  • 5日
    VTuberの幼なじみと声優の幼なじみが険悪すぎる
  • 7日
    クラスで2番目に可愛い女の子と友だちになった6
    ネトゲの嫁が人気アイドルだった4
    才女のお世話7,8
  • 14日
    凡人転生の努力無双2
    幼馴染のVTuber配信に出たら超神回で人生変わった
    キグナスの乙女たち2
  • 16日
    メイジアン・カンパニー3,4
    キグナスの乙女たち3
  • 17日
    キグナスの乙女たち4
    メイジアン・カンパニー5
  • 18日
    キグナスの乙女たち5
    メイジアン・カンパニー6
  • 19日
    夜の帳に闇は閃く
  • 23日
    メイジアン・カンパニー7,8
    キグナスの乙女たち6
  • 25日
    俺は星間国家の悪徳領主!8
  • 28日
    煽り煽られしてたネトゲ仲間が品行方正な美人先輩だった話
    異能学園の最強は平穏に潜む2

6月

  • 7日
    異能学園の最強は平穏に潜む3
    孤高の華と呼ばれる英国美少女、義妹になったら不器用に甘えてきた1
  • 8日
    極めて傲慢たる悪役貴族の所業III
  • 9日
    血の繋がらない私たちが家族になるたった一つの方法1,2
  • 10日
    美少女フィギュアのお医者さんは青春を治せるか
  • 11日
    あんたで日常を彩りたい
  • 12日
    永遠についての証明
    煽り系ゲーム配信者(20歳)、配信の切り忘れによりいい人バレする。1,2
  • 13日
    異端な彼らの機密教室1,2
  • 14日
    非科学的な犯罪事件を解決するために必要なものは何ですか?
    現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変5
  • 18日
    彼とカノジョの事業戦略1,2
  • 19日
    恋愛魔法学院1
  • 20日
    社畜剣聖、配信者になる1
    生放送!TSエルフ姫ちゃんねる

週記(2024/06/10-2024/06/16)

06/10(月)

午後3時起床。半からインターン先定例会に出席した。先週もほぼ進捗はなく、ポツポツと連絡を取っているくらい。

勉強会はGoogle検索のランキングアルゴリズムについてだった。そういえばSEO対策ではページの表示が速いのもポイントの一つらしいが、最近のアニメ公式サイトはどれも過剰にグラフィカルで、その観点からは良くなさそう。ただ考えてみると、そういうサイトへのアクセス経路は作品名を直接検索するとかどこかの広告から飛んでくるのがメインだろうから、ずれたワードの検索結果で上位に来る必要はないのかもしれない。

解散後大学生協に行き、ラノベ受け取りと夕食を済ませた。帰宅してからはずっと先週の週記を書き進め、日付が変わる直前に投稿。相変わらず週末のあたりは穴だらけでスカスカ。

先月の家飲みで余ったほろよいを開け、ラノベを読み始めた。

明日は数学科の友人を自宅に招いて遊ぶ予定。

週記(2024/05/20-2024/05/26) - kotatsugameの日記

「美少女フィギュアのお医者さんは青春を治せるか」を読了。非常に面白かった。クリエイターをメインに据えた話は「Vのガワの裏ガワ」あたりから注目しているジャンルで、これもその一環として買ったが、期待以上のものだった。実のところ、主人公が創作のトラウマと向き合うストーリー展開については特に思うところがないかもしれない。それでも間違いなく面白かったと言えるくらいキャラクターがどストライクだった。

もう一冊読もうとしたが、酔いが回り非常に眠い。椅子で寝そうになったので慌てて布団に倒れこんだ。午前5時半ごろだった。

06/11(火)

午後1時半起床。布団でハーメルンの「身長2m28cmの大男、平成元年の日本に転生する」を読了した。転生特典の高身長を活かしてバスケで活躍する話。もう一つの特典としてイケメンにしてもらっているが、設定としてどう生きてくるのかわからない。他の作品だと、話の途中でしれっと「顔が良い」程度に言及されるだけのことが多い気がする。

syosetu.org

布団に横たわったままラノベを読んでいたら夕方になった。シャワーを浴びて原付で学食に行こうとしたら、原付に鍵が入らない。よく見ると鍵の先のほうがほんの少し圧し潰されたようになっていた。そういえば原付にこびりついた鳥のフンを鍵の先でこそげ落とした記憶がある。「鍵ってそれだけで変形してしまうのか」「ほんのちょっとの変形でも入らなくなるのか」という二つの驚きがあった。仕方なくスペアの鍵を使って出発。

鍵の潰れて出っ張った部分を削ればまた使えるようになるのではと思い、大学の駐輪場に転がっていた石に擦り付けてみることにした。数分ほど格闘すると見事スムーズに入るようになったため、帰りは元の鍵を使えた。

帰宅してラノベ。「あんたで日常を彩りたい」を読了した。これもクリエイター系の話。主人公がアートの天才と関わっていく話と言えばいくつか思い当たるものはあるが、この作品では主人公にはアートに対する熱意も目標もなく、結果その苦悩も他の作品とは異なり才能の比較には由来しなかった。まあその独自性が面白かったかというと別の話になってしまう。

昨日今日とクリエイターを題材にしたラノベを読んだ。しかしその系統は、才能に焦点が当たるか当たらないかという点で全く異なる。考えてみれば当たらないほうが特殊だろう。昨日は「Vのガワの裏ガワ」と「美少女フィギュアのお医者さんは青春を治せるか」を同じ扱いにしたが、ストーリーに一致する点は見出せず、ただキャラが好みだった点が共通している。単に設定として好きなだけらしい。

もう一冊読み進め、午後11時半からはCF #952 div.4に出た。

Dashboard - Codeforces Round 952 (Div. 4) - Codeforces

Aはよい。Bは真面目に考える必要はなく愚直での全探索が可能。Cは最大値と和を持てば判定できる。Dは円に含まれるマスの座標の平均値が中心。Eは二つの軸を全探索。Fは典型的な二分探索。Gはknの計算で繰り上がりが発生してはいけない。つまりnに出現する数字がすべて9/k以下であればよい。H1は操作を全探索して繋がる連結成分を数えることができる。

H2にはかなり手間取った。選ぶ行を決め打ったとき、それぞれの列についてそこを選んだ時に連結成分のサイズがどれだけ増えるかを一気に求めたい。行を選ばない状態から初めて、選んだ行によってキャンセルされる分を適切に処理できればよいが、これは各連結成分について関係する列が区間をなすことから区間ADDで可能。遅延セグ木を使えば最大値の取得も可能になって解けた。

全完、H1までが速かったのか6位。H2は各連結成分についてどの行を、またはどの列を選んだら答えに加算されるか考えればよかったらしい。先ほども述べたようにこれは区間になるため、累積和で処理できる。また2重にカウントする分は二次元累積和でキャンセルできる。これでセグ木の\logが落ちた。実行時間は703ms→437msであまり変わらない。またUFでサボっていた部分をBFSに変えたら逆に少し伸びた。

www.youtube.com

朝方まで論文に手を加え、少し日記を書いて午前7時就寝。今週のセミナーは木曜ではなく水曜、それも正午からの予定である。

06/12(水)

午前11時過ぎ起床。慌て気味に登校し、購買で買ったパンを食べて正午からのセミナーに参加した。

まず2時間は後輩の発表。教科書のうちセミナーでは飛ばした部分にある定義や定理を使う話からスタートしたら、即座にツッコミが入り、そこを説明しているうちに時間切れとなった。準備してきた部分に踏み入る余裕がなくて残念という気持ちと、案外重要そうな定義だったからしっかり確認出来てよかったという気持ちがある。

その後は久しぶりに先生の発表。毎回のセミナーで話すはずが、なんだかんだ我々の発表が長引いてばかりでなんと4月以来である。部分問題で\sum|x_i-y|を最小化するyの性質が出てきた。この形ならyx_iたちの中央値とすればよいのは競プロでは有名事実。今回はxが確率変数であり、正確には|x-y|積分値を最小化することになった。中央値をうまいこと定めれば結論は同じらしい。

次の2時間は先生が最近の研究内容について発表。予定されている学会発表に向け、この先数回は先生も話すらしい。

週記(2024/04/08-2024/04/14) - kotatsugameの日記

少しの議論も含め午後6時までかかった。学食で夕食を摂り下山。そういえば今日はサークルの活動日だったと思い出して教室に行ってみたら、ICPC向け3hバチャの終盤だった。最終問題に取り組んでみるも何もわからず終了。

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

午後8時頃帰宅し、サークルから出場するICPCチームの登録を行った。今年はmilkcoffeeさんと分担し、自分は3チーム担当する予定。

チュウニズムからツユ曲が消えるようだ。コナミは事件が報道されてすぐ削除したが、セガは微妙に時間がかかった。おそらく来週の大型アップデートで対応されるのだろう。理論値も出しているので心残りはない。少し増えた消える称号についてはまた集めに行く。

チュウニズムに収録されているツユの楽曲は全部理論値で揃えている

週記(2024/05/20-2024/05/26) - kotatsugameの日記

本を読んでいたら、AtCoderの企業対抗チームバトルが始まり、終わっていた。THIRDは見事優勝。先週の勉強会で短期AHCの戦略について詳しく議論されたが、こんなにすぐ成果に結びつくものかと感動した。

勉強会は短期AHCにおける戦略の話だった。

週記(2024/06/03-2024/06/09) - kotatsugameの日記

読んでいる本のクライマックスに差し掛かったところで午後11時半。せっかくのセミナーを控えていない水曜夜なので、3月以来久しぶりにCodechefに出た。Starters 138。

https://www.codechef.com/START138A

DISTSUBは長さ1,\dots,Kのislandの間を区切れればよいから、N\ge K(K+1)/2+K-1を判定。APOWBMODCは軽いギャグ。A^B\equiv 0\pmod CよりBが偶数かつCA^2だと嬉しい。このときにもう一つの合同式を満たそうとすると(B,C)=(2A,A^2)が考えられる。これでダメなのはA=2のケースのみなので、それだけ手で構築。

PREFSUFFもギャグ寄りか。prefixのbitwise ANDを大きくしたいので、同じ値を並べたい。そこで最初1,\dots,1,0を提出したが、これはA\ge 1の条件を満たさない。少し弄って3,\dots,3,1とした。TRIPRIは偶奇を見ればa=2と固定できる。あとは\sqrt N以下の素数の2乗を前計算しておいてチェック。

MODE_PROBLEMは各値の1個目を並べ、次に2個目を並べ、……とするのがよさそう。このとき必ず最後に置いた要素が最頻値となっているため、出現回数c回の値は答えへ1+\dots+cだけ寄与することになる。こうやってバラバラにすると差分更新が非常に簡単。KPRODSUMは最初部分列だと思い込んで畳み込みを持ち出してしまった。冷静になると尺取りで……は除算ができないため不可能。無理せず遅延セグ木で殴った。

CCLPEDは重みを固定して各辺を何回使うか考える。各頂点がflipする回数が偶数であること、また使う辺だけ集めたときの連結成分がそれぞれ2色持っていることが必要。手でいくらか試すと十分な気がしてきた。この場合重みとしては\min w_iから\min w_i-2までの3種類試せばよく、出したら通った。

48分で全完、2位。下のdivisionの2問も解いておいた。

コンテスト前に読んでいた本を読み切り、立て続けにもう2冊読んだ。

「永遠についての証明」。非常に面白かった。前半の数学科の描写はかなり真に迫っていると感じた。ただし学部入学から3年で研究テーマを決めたり取り組む問題を見出したりするのは現実離れしていると思う。またそういう様子が普通のこととして描かれるから、自分の現状と比較してつらい気持ちになったりもした。

しかし後半からは怒涛の展開。主人公の一人がどん底に向かって一直線に転げ落ちる様子にどんどん引き込まれていった。亡くなる理由はてっきり事故みたいなものだと思っていたのだが、まさかこういう展開だったとは……。そしてクライマックスに繋がる。ここの高揚感は物凄かった。オチは鉄板の手法ではあるものの、フラクタルを扱った作品であることを振り返ると感慨深いものがある。

以上、数学を扱う小説としては数学の扱いも正確だし、小説としての話の面白さもあるし、非常に良いと思った。ただ文庫本のカバーがいただけない。降ってくる数式が全部三角関数とはいったいどういうことか。しかも自分の買ったものは大きな帯が巻かれていて、そこには手書き風フォントで「数学知識必要度……星一つ」みたいなおせっかいが書いてある。余韻が台無し。

「煽り系ゲーム配信者(20歳)、配信の切り忘れによりいい人バレする。」。カクヨムで読んだ作品の書籍化。この作者は現在、同様のカクヨムラノベシリーズを複数抱えている。正直なことを言えば、自分が触れた他の2作品はどちらも主人公を持ち上げる向きが強引すぎてあまり好みでなかった。ではなぜ買ったかというと、この作品は面白かったという記憶が残っていたからである。実際今挙げた点については気にならなかった。おそらく副ヒロインと主人公の距離が少し遠いのが良かったのではないか。

続いて「煽り系ゲーム配信者(20歳)、配信の切り忘れによりいい人バレする。」2巻。だいたいここからカクヨムで読んでいない部分。そういえば1巻を読んでいるときには全く注意していなかったが、主人公は声だけの配信者、ヒロインはVTuber、2巻で登場したキャラは顔出し配信者らしい。声だけというのはちょっと想像がつかないなと思った。

Twitterで他人のいいね欄が見られなくなった。「今週中に~」みたいな話だったはずだが対応が早すぎる。

シャワーを浴びて午前6時半就寝。

06/13(木)

午後5時起床。しばらく布団でゴロゴロしてから学食に行って夕食を摂った。

帰宅してまた布団に戻り、ラノベ。途中寝落ちしたりネット小説にうつつを抜かしたりしながら昼前までずっと読み続けていた。「異端な彼らの機密教室」1巻と2巻を読了。

戦場帰りの主人公が学園に入学する話ということだったが、学生らしいシーンがほとんどなく訓練一辺倒。また任務で学園外に赴いての実戦シーンだったから、期待していた学園モノらしさというのは一切感じられなかった。2巻で完結らしい。話を回収し、締めのシーンも用意してきちんと終わっている点は好印象だった。

午前10時就寝。

06/14(金)

午後4時に目を覚ました。なろうを読み始めたら歯止めが利かなくなり、3時間ほど経過。購買は閉まったし今から学食に行くのも面倒。ゲーセンに行くかどうか検討しているうちに寝落ちした。起きたら午後10時半。仕方ないのでラノベを読んだ。

「非科学的な犯罪事件を解決するために必要なものは何ですか?」を読了。ハーメルンで読んでいる非常に好きな作品の書籍化。気合いを入れて読みたかったのでタイミングを計っていたら刊行から4か月以上経ってしまった。自分はWebで先を読んだから、1巻時点での主人公の自分語りが全く信用ならないことを知っており、かつそれがこの作品の特に好きな点になっている。しかし1巻だけでは伝わらないだろう。まだ続刊するとの情報がないが、どうだろうか。

続いて「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」5巻を読了。これは気合いを入れて読みたいというより読むのに気合いが必要で、先ほどのラノベと同じくらいの期間積んでしまった。案の定読み終えると疲労困憊だったが、面白さは健在。この巻は経済以外の分野における主人公の活躍が多めだったと思う。そして後半ではいよいよ中学生に進級。側近団が入学してきて、校内でも派閥に気を遣った行動が求められ、これから大変そう。

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

06/15(土)

目覚ましで目を覚ましたら午後1時55分だった。飛び起きてUniversal Cupに参加。今日は第2回目、Zielona Góraセット。

https://qoj.ac/contest/1699

書く

食事して午後9時からABC358。

AtCoder Beginner Contest 358 - AtCoder

書く

www.youtube.com

明後日に迫った勉強会の準備を開始。朝まで取り組んで午前8時半に寝た。

06/16(日)

午後3時起床。AHC034に参加した。

Toyota Programming Contest 2024#6(AtCoder Heuristic Contest 034) - AtCoder

書く

AHCを離脱して午後6時からCF #953 div.2へ。

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

書く

www.youtube.com

勉強会の準備をした。スライドの体裁にこだわりすぎたり、後半の内容がうまくまとまらなかったりして、非常に長い時間をかけてしまった。何とか形になったころには正午を回っていた。

午後0時半就寝。

週記(2024/06/03-2024/06/09)

06/03(月)

午前6時半、緊急地震速報で目を覚ました。スマホを見たら富山湾で発生したとのことで、仙台でも速報が出るくらい大きな地震なのかと震え上がったが、結局ここは揺れなかったし、実家の揺れもさほどではなかったようだ。また寝た。

午前11時起床。しばらく週記を書き、昼休みが終わった頃合いを見計らって学食に行った。食後にラノベを受け取って帰宅。来るときは青空が見えていたのに食べている間に一気に曇ってきて、一雨降るかと焦った。

午後3時半からインターン先定例会に出席。進捗はない。待ちのフェーズではあるものの、できること・やっておいたほうが良いことは当然あるので、そういうものを進めていきたいところ。

勉強会は短期AHCにおける戦略の話だった。聞きながら自分の戦績を振り返ってみて、貪欲でうまく行った回がほとんどだということを改めて認識した。しかも強い貪欲を作れた先のマラソンテク、例えばプレイアウトやビームサーチで負けているようだ。自分はその間貪欲の些細な改善に固執し続けていた。だからまあ、まずはマラソンを頑張りましょうということになってしまう。

解散後は週記を書いていたが、途中で少しハーメルンに手を出した。先週から読んでいた「最強の魔法使い(自称)が暴れるそうです。RE:」を読了。リメイク前後で文章の質がガクッと下がり失速してしまったものの、何とか読み進めていくと徐々に改善されてきた。あるいは自分が慣れただけかもしれない。とにかく無事最終話までたどり着くことができた。

その最終話で主人公が死んでしまった!ありとあらゆる能力が剥奪され、苦しみながら死んでいった!まさかチートオリ主ものがバッドエンドになるとは思いもせず、まったく身構えていなかったので深い衝撃を受けた。救いを求めて続編をチラ見しても状況は変わらず、しかもエタっている。絶望。能力元の「東方異形郷」も悲惨な話らしいが、わざわざ再現してくれなくてもよかったのに……。

syosetu.org

落ち込みながら週記の執筆に戻り、午後11時過ぎに投稿。半からCF #950 div.3に出た。

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

Aはよい。Bは出力の説明を読まないと正確な問題がわからない。コードを書き上げてから読んだらMAYBEも判定する必要があってひっくり返った。Cは上書きなので後ろから見る典型。最後の操作以外はキャンセルできると思ってよいため、最後の操作が行えるかと、必要なだけの操作があるかをそれぞれチェックすればよい。Dは削除した位置の周りだけ真面目に計算し、残りは前計算した結果を使って判定する。

Eは行を値の集合と見て揃えた後、列の並び替えを求めてすべての行で一致しているか調べた。FはF1を飛ばし、直接F2を解いた。cの昇順に並べてrの累積MAXを取ると経路が求まる。累積MAXの更新点を一つ消したとき、新たに更新点となるのがどこかわかればよく、候補がdisjointなので線形時間で解いても合計O(k)で十分高速。F1とF2は微妙に異なる問題だが、F2のコードをそのままF1に出しても通るようにしてくれていてありがたい。

Gは適当に決めた根からのパスのXORとして管理すると、深さが奇数の点に対するXOR更新と、定数をXORしたときの最大値の取得になる。深さの偶奇で分ければbinary trieで対応可能。ライブラリが空集合のMAXを取ろうとすると壊れる実装で、手元では動いたため気づかず提出してしまったが、幸いサンプル1で落ちてくれたためペナを逃れた。

1時間で全完して4位。

www.youtube.com

森見登美彦さんも参加されているアンソロジー小説が近く発売されるらしい。慌てて注文した。

tomio.hatenablog.com

ところで、大学生協で受け取るための注文サイトが「大学生協のオンライン書籍注文サイト」から「オンライン書店Honya Club.com」に変わる。すでにアカウントがあって何事かと思ったが、メールを掘り返してみると2020年の9月くらいまで使っていた形跡があった。サイトが変わって、4年越しにまた戻ったということらしい。注文履歴は消えていて残念。「書籍注文サイト」があり得ないくらい重かったので、快適になってシンプルにありがたい。

オンライン書店Honya Club.com

シャワーを浴び、洗濯して午前5時就寝。

06/04(火)

午前9時半起床。降水確率40%だが原付で登校した。

午前10時半からZoomでオンラインセミナー。4月にお越しいただいた先生に、再度セミナーをしていただいた。前回紹介していただいた論文を指導教員以外の先生も交えてセミナーで精読しているため、話の内容もよくわかり、多少の議論もできて有益だった。特に大局的な話、他研究と比較しての位置付けについて話していただけたのが非常にありがたい。

午前10時から2時間弱は招いた先生によるセミナー。

週記(2024/04/08-2024/04/14) - kotatsugameの日記

解散後、指導教員の先生と教室で話していたら、次の利用者の先生が来たので退散した。この先生には自分がB2の頃、群論の講義と演習でお世話になったことがある。今日、自分の顔を見てすぐ演習で解いた問題を言い当てられ、本当にびっくりした。5年前のことなのによく覚えていらっしゃるものだ。当時発表で炎上してしまい苦い思い出となっているのだが、それを理由に覚えているという雰囲気ではなかったので救いになった。

セミナーで紹介していただいた本を資料室で借り出した後、学食で食事。ICPCの国内予選ルールが変更されたのを知った。特に事前準備の許可が大きいと思った。多分ライブラリのコピペがOKになったということだろう。

午後2時過ぎに帰宅。ひとまずPCの前に座ったものの、なんとなく眠くて何かする気にならず、布団に戻った。午後3時半から午後7時くらいまで寝ていた。目を覚ましてからもPixiv小説を読んだりYouTubeを見たりで、さらに3時間くらいダラダラ過ごしていた。

再来週の月曜日にインターン先勉強会での発表を控えているため、題材を探し始めた。最近解いた問題から何かないかと調べてみたものの、どれもピンと来ない。前回の2次元遅延セグ木は同様の考え方で決めたテーマだった。それがTwitterで少し話題になって嬉しかったから、今回も興味深いものを……と思っているものの、暗雲が漂う。

日付が変わり、TCBの2024/05回が終了した。3位。

https://techful-programming.com/techful/event/5706

5問目まではよい。6問目は冷静になるとkとしてNの約数だけ考えれば十分なので、愚直にチェックできる。7問目は各行各列のpopcountだけ覚えていれば総和の差分更新が可能。10分かかってギリギリではあったものの、何とかここまで理論値で通せた。

8問目は問題文がカス。まずスタートマスが定義されていない。(a,b)(c,d)が入力で与えられて片方がゴールならもう片方がスタートだろうとは分かるものの……。また、氷の床みたいな設定で移動できるか聞くのだからそのマスにピッタリ停止できるか判定するものだと思ったが、違うらしい。ここの定義が曖昧なのはどうしようもなく、解釈に失敗して1WA。時間ボーナスも少し削られて-12ptとなった。

9問目は操作が可逆なので、それぞれ辞書順最小になるよう操作して比較した。実験から見出した規則を頑張って実装しても全然合わなかったが、改めて考えると2連続の1を作って削除・挿入する方針で説明がつくことに気づき、そこそこシンプルな実装に落ち着いた。実は削除し切った段階で比較しても同じであり、辞書順最小の列を作ることに固執する必要はなかったらしい。ランダムケースで試して提出。WAこそ出なかったものの73分かかってタイムボーナスが消え、-42pt。

10問目は行列累乗。Nがクソデカ整数だが、2分の1のために毎回桁数に対する線形時間をかけても間に合うので適当に実装してよい。これは20分で実装が終わり、理論値だった。

11問目はbitを別の数の同じ桁に移すことが可能なので、増やせるか考える。{00}_{(2)},{10}_{(2)}{11}_{(2)},{01}_{(2)}にできるので、最上位bit以外ならかなり自由に扱えそう。最上位bitは一度減らすと戻せないので、全部の数でそこが立った状態を保ちたいなら一つ下の桁以降を見て解くことにし、そうでないなら先ほどの議論からほとんど何でもできるということになった。愚直と比較して提出。27分かかって-6pt。

12問目はとんでもない時間がかかってしまったが、結論はシンプル。aa...abb...bを取り除けるだけ取り除いて残る文字列が同じものをすべて作れるので、逆に残った文字列に挿入する方法を考えて数え上げる。重複して数えないようにするため、ある文字の前に挿入する際は、それと異なる文字が来るようにした。

あとは削除できる文字列の数え上げとなる。FPSで立式するとf=x\left(\frac{1}{1-f}\right)^{K-1}になって、収束が遅すぎるしニュートン法もうまくいかなかったものの、小さいKに対してOEISで検索したらそれぞれ一般項が出てきて、Kに関しても一般化できる形だったためうまくいった。[x^i]f=\binom{Ki-2}{i-1}/iらしい。

ちなみにその後g:=\frac{1}{1-f}を計算しており、こちらで式を書き直すとg=1+xg^Kとよりシンプルな形が出てくる。まあ一般項は大して変わらない。K=2では意味的にもカタラン数だとわかるが、その一般化として研究対象になっているようだ。

fが計算できるようになった段階で、それを使ってdp遷移するコードを提出したものの、TLEしてしまった。冷静になって見直すと、やっていることはg^c(1+(g-1)+(g-1)^2+\dots)の計算に他ならない。ここでcは残った文字列の長さに1足したもの。二分累乗法を使って出しなおしたら通った。3時間と1ペナで-68pt。タイムボーナスもないのになぜ焦って提出したのか理解不能

potato167さんの解説ブログも貼っておく。

potato167.hatenablog.com

午前1時頃に寝てしまった。

06/05(水)

午前8時起床。しばらく布団でゴロゴロした後、セミナー準備に取り掛かった。今日の夜は競プロサークルの確定新歓があるため、それまでに完成させたいところ。

……のはずが、完成間近で論文の証明にミスがあるのを発見し、修正が間に合わなかった。仕方ないので中途半端な資料を、夜中に更新するかもと言いつつセミナー参加者に送信。シャワーを浴びて午後6時頃に家を出た。

確定新歓は昨年と同じ店の同じ焼肉食べ放題。ただし今年はホスフィンが来ておらず、ほかのM2も軒並み不在にしていて、自分だけちょっと歳が離れていた。調子に乗って昔話、それこそコロナ以前の体験談を喋ってしまったが、良くない老人仕草なので控えめにするべきだったかも。競プロの実装に関して質問されて嬉しかった。

今日はサークルの確定新歓の日だった。

週記(2023/05/22-2023/05/28) - kotatsugameの日記

特に二次会もなく解散。その足でゲーセンに行き、閉店まで18クレプレイした。未プレイだったLv.15 4譜面を触り、LUMINUSバージョン稼働以来およそ半年ぶりにレーティングポゼッションが復活した。オーバーパワーが99%をギリギリ超えるくらいで、今の基準だとプラチナらしい。

特に「Makear」と「ラストピースに祝福と栄光を」が体力譜面で大変だった。前者は前半がうまくいった回で後半耐えたスコアであり、伸びしろがない。後者は最初の数回だけ大宇宙ステージ地帯の両手トリル餡蜜がうまくいったのだが、後半が振るわなかった。逆に後半が慣れてきたころには前半でポロポロ失点するようになってしまい、なんとも噛み合わない結果に。

満腹なので食事はせず、ドンキにも寄らずに帰宅した。シャワーを浴びようとしたものの眠気に負け、しばらくカーペットに横たわって寝ていたらしい。午前2時くらいに目覚め、何とかシャワーを浴びて再度就寝。結局セミナー準備の続きはできなかった。

06/06(木)

午前11時起床。昨日できなかったセミナー準備を行い、ミスのあった証明にも代わりの正しいものを用意できた。午後1時過ぎ原付で登校。夕方から降水確率40%らしい。

学食で食事して、半からセミナー開始。前回準備した分の残りを話そうとしたら内容をあまり覚えておらず、頻繁に資料を確認してしまった。また細部はいくらか飛ばそうと思っていたのに、どこを飛ばすべきか考えておらず、結局全部丁寧に話してしまった。今週準備していた部分は丸々残ってしまって次回話すことに。証明のテクニックはもう出尽くして、残りは面倒な計算パートが多いので、どう説明するか考えておかなければならない。

曇り空が怪しくなってきたので帰ろうとしたが、この後後輩と先生が話し合いをすると聞いて、興味本位で同席することにした。ただし話し合いといっても次回のセミナーの確認だけだったようだ。先生が去ったあとは後輩が読んでいる教科書についてしばらく二人で議論した。一段落して学食に行ったら今度は雑談に花が咲き、午後8時前になって解散した。

帰宅後、COSS2024への参加申し込みを行った。セミナーの合間に先生に相談したところ、問題なく許可が出た。何かが起こる気配も今のところないため、冬のLAシンポジウムみたいにキャンセルすることにはならないはず。

COSS2024 Home

午後11時半からCF #951 div.2に出た。

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

Aは、Bobはできるだけ短い区間を選ぶべきなので、隣接項のMAXのMIN引く1が答え。Bはi\oplus j=x\oplus yに加えi\oplus(i+1)=j\oplus(j+1),(i+1)\oplus(i+2)=(j+1)\oplus(j+2),\dotsが条件となるので、ijともに下のほうのbitは一致し、特に全部0になっていてほしい。つまりx\oplus yを割り切る最大の2べきが答え。

Cは整数性を忘れると\sum 1/k\lt 1が条件。判定を考えるとA:=\mathrm{lcm}(1,\dots,20)を使って\sum A/k\lt Aか見る方法が思い浮かび、よくよく観察するとこれがそのまま答えにもなっている。つまりx:=A/k。Dはpを全探索する。先頭からp-1文字とp文字目以降がそれぞれk-properになっていて、かつ操作後に繋がる部分にも少し条件があるが、チェックは簡単。Eは45度回転すると必ず2点が軸に並行な直線に乗る。

Fは有向完全DAGのハミルトンパスを作るのと同様に再帰を考えたら解けた。補グラフで説明すると見通しが良いので、そうする。次数の条件も反転していることに注意。d=1で聞いて、もしu\ne 0が返ってきたなら、頂点vは次数1で辺(v,u)と接続している。つまりvが削除された今、n-1頂点n-3辺となっている。そのハミルトンパスを再帰的に作ると、どちらかの端点にはvを繋ぐことができるため、元のグラフのハミルトンパスが得られる。

ではu=0が返ってきた場合はどうするか。この場合孤立点vを削除しており他の頂点の次数は一切変化していないから、次にd=2で聞いたとき返ってくる頂点は次数が0または2となっている。それぞれu=0u\ne 0に対応するため、u\ne 0だった場合はn-2頂点n-4辺のグラフが得られており、先ほどと同様再帰的にハミルトンパスが構成できる。以下u=0の間d=3,4,\dotsと聞いていけばよい。

全完3位。Fでd=1を聞いてu=0が返ってきた後は、dを最大値にして次数最大の頂点を削除するという方法もあるらしい。この場合辺の数がn-2本「以下」の状態で再帰することになるが、確かに特に問題なく構築できる。

www.youtube.com

「冬季限定ボンボンショコラ事件」で描かれた中学生時代の小佐内さんは、挨拶で何度か「おわあ、こんばんは」と言っている。何の意味があるのかわからなかったのだが、萩原朔太郎の詩に由来することを知った。

ラノベを読んで午前8時半就寝。

06/07(金)

午後2時半起床。CHUNITHMのバージョンアップ情報が流れてきた。ここ最近のイベントが全部06/19に終了するところから何となく予想はついていたが、削除される楽曲については予想外。ボカロジャンルに属していても人間が歌っていればポプアニジャンルと同じ感じで消えていくのだろうか……。ただしこの理論では「FREELY TOMORROW」が消える理由がよくわからない。

info-chunithm.sega.jp

ラノベを2冊読んだ。1冊目、「異能学園の最強は平穏に潜む」3巻。今回は主人公が最初から大きく動いていて楽しかった。読んでいる最中はあいまいな描写に動揺したものの、振り返ってみると全編無双シーンと言える。2巻3巻で主人公の能力が加速度的に明らかになっているが、言っていることが本当なのか怪しいので底はまだ見えない。

2冊目、「孤高の華と呼ばれる英国美少女、義妹になったら不器用に甘えてきた」。主人公がスポーツ熱心な好青年で非常に印象が良い。ヒロインの隣にいても違和感がないというのは重要だと思う。野暮ったかった見た目を整え、努力して違和感を消す主人公もいるが、最初から評価が高いほうが振る舞いにも自信を感じられて好み。

午後7時くらいになって外出。歩きながらハーメルンの「天才TS美少女はわからされたい!」を読み切った。自分はチート主人公で才能に満ち溢れている、だからなんでもやってみればできる、という自信の持ち方が少し危なっかしいと思った。地に足がついていなくて怖い。

syosetu.org

立ち食いそばを食べ、本屋で本を買ってからゲーセンに向かった。今日は金曜日なので金曜奴の集まりを避け、GiGO仙台へ。閉店まで18クレプレイした。家を出る前にバージョンアップで消える楽曲の称号を調べてきており、もっぱらそれらを集める作業をしていた。

特に14+の「紅」と「]-[|/34<#!」はAJを出していなかったので、曲名称号を取得するため頑張って詰めた。「]-[|/34<#!」の最後のフリックが全然入らなくて気が狂いそうになった。腕はボロボロになったものの、最終的にはどちらも出せたので、楽曲追加当時からの成長を感じた。

別のゲーセンのトイレを使ったら店員と目が合ったので、申し訳程度にもう2クレプレイ。立ち食いそばを食べた後ドンキに寄った。税抜100円の「つぶつぶチョコ」という商品を発見し、安さに惹かれて5袋買ったのだが、帰ってきて食べてみたらチョコの糖衣部分のケミカルな味が舌に合わなかった。まさかこの世に不味いチョコ菓子があるとは。5袋もあるのにどうすればいいんだ。

今日買ってきた本のうち1冊は、予約に失敗したSAOの28巻。

SAOの新刊が2年弱ぶりに出るが、すでに予約が品切れとなっていて残念。

週記(2024/05/20-2024/05/26) - kotatsugameの日記

ところで現在、hontoというサイトのMy本棚機能を使って本の購入記録をつけている。こうしておくとhontoの商品ページに表示が出て、買った本かが判別しやすいのだ。ところが今日登録しようとしたらできなくて焦った。どうやら紙の本に関してはサービス全般が終了し、電子書籍だけのサイトに変わったらしい。しょうがないので電子書籍として登録しておいた。紙の本の登録は最終的に703冊に上った。

シャワーを浴びて午前3時半就寝。

06/08(土)

午後1時半起床。午後2時からUniversal Cupに参加した。先週トライアルコンテストを終え、いよいよシーズン3が本格始動する。今日は第1回目のSt. Petersburgセットだった。

https://qoj.ac/contest/1696

書く

動画準備を整えた後はラノベを読んで過ごし、午後9時からABC357に出た。

SuntoryProgrammingContest2024(AtCoder Beginner Contest 357) - AtCoder

書く

www.youtube.com

「極めて傲慢たる悪役貴族の所業」3巻を読了。語り手の切り替えがかなり頻繁にあって読みにくかった。語り手となるキャラも多いし、別々の場所の出来事が並列して描かれるのでなおさら。特にラストは視点を切り替えまくって風呂敷を広げるだけ広げ、回収はすべて次巻以降に丸投げという印象で、今のところ何が起こっているのかよくわからず混乱中。ただ中盤までは話もそれぞれ一区切りついて面白かったということを明言しておく。

午前5時就寝。

06/09(日)

午後1時起床。昨日今日とアーケードのあたりで「東北絆まつり」という祭りが開催されているらしい。東北6県の有名な祭りが一堂に会するということを数学科の友人から聞いて、ちょっと行ってみようかなという気になっていたのだが、調べたら昨日の人出がものすごかったらしくて萎えた。

布団でラノベを読んでいた。「血の繋がらない私たちが家族になるたった一つの方法」を読了。ヒロイン二人の導入から恋愛トラブル、偽カップル成立までがテンポ良く描かれて面白かった。恋愛トラブルの発端となった男子は、最初の描写だけだと根暗なオタクくんに見えて少し苦い気持ちになったが、実際は見た目良し・頭良し・運動神経良しのかなりの好青年でびっくり。主人公とヒロインの偽カップルに対し正々堂々と向き合っており、こじれるような気配がなくてよかった。

午後6時くらいに寝落ちした。次に起きたのは午後10時。シャワーを浴び、食事して午後11時半からCGR26に出た。

Dashboard - Codeforces Global Round 26 - Codeforces

書く

www.youtube.com

ラノベ「血の繋がらない私たちが家族になるたった一つの方法」2巻を読了。この巻も面白かった。ヒロイン二人の過去についての話がメイン。主人公にも何かあるようだが、まだほとんど何も明かされていない。ラストの体育祭のシーンはなかなか過激でよかった。そういえば、ヒロイン二人を侍らせる主人公に対する周囲の嫉妬というのはほぼ描かれていない気がする。体育祭での行動にはどんな反応が来るだろうか、3巻冒頭が楽しみ。

日記を書いて午前10時過ぎ就寝。

週記(2024/05/27-2024/06/02)

05/27(月)

午後3時起床。今日から集中講義である。登校し、購買で買った総菜パンを食べて教室に向かった。

数学科の集中講義は、初日だけ談話会という独立した内容になっていて、講義に関連する話題について1時間程度の発表を聞くことになっている。擬似ランダムネスや脱乱択化など去年のCOSSで見聞きしたものに再会し懐かしい気持ちになった。ただそういう応用が重点的に紹介された一方で、明日から何を学ぶのかについてはピンとこなかった。談話会の性質上仕方のないことだとは思う。

1時間で終了。講義に来ていたホスフィンと学食に行って、夕食を摂りつつしばらく話した。食べ始める前から満腹で、完食まで非常に苦労したが、よく考えるとパンを食べてから2時間も経過していなかった。午後6時半くらいに解散して帰宅。

先週のAHC033が終了した。結局先々週の1回しか提出しなかった。全部のクレーンを使って限界までコンテナを搬入した後、大クレーンだけ使って一つずつ搬出していく解法。操作回数は大体250回から300回となっていた。最初は搬入から大クレーンだけで行おうとしていたが、複数のクレーンを同時に使うと思った以上に操作回数が減ることに気づいたため、並び順が悪くてもとりあえず搬入してしまうことに。ただそれ以上を実装するにはやる気が足りなかった。

TLの感想戦で、途中ほぼ満点を取っていた人の失点をうまく分数で表現することにより、最適な操作回数が70回弱であるということを見積もった話が流れてきた。相対スコアの順位表でもそうやって情報が取り出せるのだなあと感動。

Toyota Programming Contest 2024#5(AtCoder Heuristic Contest 033) - AtCoder

日付が変わる前に週記を投稿。その後30分ほどしたら眠気に耐えられなくなり、布団に倒れこんで寝た。

05/28(火)

午前5時起床。

ラノベ「煽り煽られしてたネトゲ仲間が品行方正な美人先輩だった話」を読了。思ったより「煽り煽られ」していて、ノリについていけなかった。なじみのないネトゲ用語が飛び交うのも苦しかったが、これはこちらの問題だろう。最近のラノベにおいてはバトルロイヤルゲームは前提知識。

先週の週記をいくらか書き足し、シャワーを浴びて午前9時頃布団に戻った。そこからまたラノベを開き、うっかり読み切ってしまった。

「異能学園の最強は平穏に潜む」2巻。面白かった。1巻と同じく、主人公がまず敵に負けて警戒を外し、その後裏から手を回して勝利するという流れ。負けるのが策の一部であるということを何度も念押しされており、読んでいてストレスを感じなかったのが非常に良い点。暗躍することとバトルで存在感を示すことが高いレベルで両立されていた。

1巻を読んでから1年以上間を開けてしまったため、設定や人間関係をすっかり忘れてしまったのが痛い。能力のランク付け4段階のうち、上から3番目が「王」系統、2番目が「加護」系統らしい。自分が単語に対して抱く印象としては逆だったので、途中までそのつもりで読み進めており、しっくりこなかった。

いくらか仮眠しようと思ったものの、結局眠れずにYouTubeを眺めていた。午後1時頃に登校。今日は雨が降っているので地下鉄を使う。山に登る前に川内の購買で食事し、ラノベを受け取っておいた。午後2時半ごろ教室に到着し、しばらくハーメルンを読んで開始を待っていた。

午後3時から集中講義一日目。昨日の談話会はスライド発表だったが、今日からは板書らしい。書く手間があってゆったりとしたスピードの講義となり、内容がまだ講義資料を読めばわかる範疇だったので、少し退屈さを感じていた。ただ、途中途中で別の先生と議論しているのに耳を澄ませると、証明手法や式の解釈についてさらなる知見を得ることができて非常に有益だった。こういうのは講義資料にないし、板書もされない。

午後6時終了。ホスフィンが用事があるとのことで、一人で学食に行った。今日も満腹だったので主菜と副菜だけ時間をかけて食べた。午後7時半くらいに帰宅するとすぐ着替えて布団に入り、それから眠くなるまでずっとハーメルンを読んでいた。

最近読んでいるのは「最強の魔法使い(自称)が暴れるそうです。RE:」。能力てんこ盛りのチートオリ主だが、文章はなかなか抑制が効いていてそこまではっちゃけておらず、寒いノリもないため読みやすい。しかしこれはリメイク後だからだったようで、まだリメイクされていない第四章に突入すると……お察し。設定は好みなので頑張って読み進めていきたいとは思うものの、耐えられるだろうか。

syosetu.org

午後11時過ぎに寝落ち。布団に入ってからなぜか腰と足に痒みが生じ、掻けば掻くほど悪化してなかなか辛かった。

05/29(水)

午前10時起床。ハーメルンを読み、シャワーを浴び、少しだけ日記を書き進めて午後2時半に出発した。今日は晴れたので原付。ここ二日の反省から、夕食時に満腹とならないよう昼は菓子パンで済ませた。

午後3時から集中講義二日目。前半までは昨日と同じく楽。しかし後半で講義資料の2章に入ってからは、資料の順番から外れ、また説明でも感覚的な話が加わってきたため、ちゃんと聞いていると面白くて退屈さはなくなった。そういう資料にない話の中で演習問題の解法について触れていたが、問題の状況にそぐわず、質問したところ仮定が足りないということになった。こういうところは集中講義後のレポートで苦しむより、対面で質問できるうちに潰しておきたい。

今日は午後7時までかかった。ホスフィンと食事して午後8時過ぎ帰宅。PCの前に座ってみたがうっかりスマホハーメルンを開いてしまい、また寒さからそのスマホを握りしめたまま布団に引っ込んだところ、すぐ寝落ちした。午後9時。

05/30(木)

午前6時起床。ハーメルンYouTubeを見ていたら二度寝できる雰囲気ではなくなったため布団を出た。少し日記を書き、指導教員の先生に出された課題を解いたら午前11時になったので、シャワーを浴びて登校。今日は集中講義の前にセミナーがある。夕方から降水確率40%だが原付で向かった。

学食で食事し、正午からセミナー開始。後輩の発表。これまでずっと離散的なものを扱っていたから\sumさえ扱えればよかったのだが、今日は連続なものに一般化する話だったので積分が登場して大変だった。慣れていないし学部時代の知識も抜けてしまい、何ができて何ができないのか曖昧である。

午後3時になって教室を移動し、集中講義三日目。資料の1章を二日目前半までかけて全部きっちり話していたから、2章の昨日触れなかった分も今日やると思っていたが、すぐ3章に入ってしまった。順番を変えたのではなく、単に飛ばしていたらしい。さて、3章はいよいよ講義のメインテーマに近づく章であった。登場する式は添え字が大盤振る舞いされていて手ごわいものの、今日もイメージの説明がふんだんに含まれていて、気持ちの上では十全に理解できたものと思う。

今日も午後7時まで延長し、3章の内容が終了。この章はどこも飛ばされなかった。ホスフィンと食事して午後7時半ごろ帰宅し、荷物を整理してまたすぐ出かけた。ゲーセンに行く。一昨日から痒みに悩まされているため、途中のドラッグストアで痒み止めのクリームを購入した。

ゲーセンには午後11時くらいまでいて、15クレ遊んだ。先週始まったMuse Dashコラボの新曲埋め。「それはもうらぶちゅ」は周央サンゴさん歌唱ということで、こういう形でVTuber曲が入ることには驚いた。ポプアニではなくVARIETYジャンルだが、バージョンアップで削除されないと思ってよいだろうか。曲はかなり好みだったので理論値を狙った。

ドンキで買い物して帰宅。急いでシャワーを浴び、午後11時半からECR166に出た。

Dashboard - Educational Codeforces Round 166 (Rated for Div. 2) - Codeforces

Aはパスワードがソートされているか判定すればよい。Bはコピーする要素を固定すると、どれだけインクリメント・デクリメントしてからコピーすればよいかは算数でわかる。Cはどちらかのポジションが埋まる位置を二分探索で求める。取り除いた人の寄与は適切にキャンセルする。

Dはかっこ列の累積和グラフにおいて上下反転するような操作になっている。よって高さが同じかつその間に高すぎる山がないのが条件。高さを固定し、含んではいけない山で区切って数えた。Eはlまたはrとして出現する要素の順序が決まるので、その間に未確定の要素を詰めることで数え上げられる。左または右の値以下なら詰められるので、大きな値から順に入れられる隙間を数えていくとよい。

Fはよくわからないが、直感的に良さそうなものが通った。まず根付き木を貪欲に葉からのパスへと分解していく。これは子から伸びてきたパスのうち最も長いもの以外を切ることで行える。その後、パスの長いものから2k-1本に対応する葉と根を適切に繋ぐことで、パス上の辺が橋でなくなり、また条件を満たすようになる。これが最適らしい。

全完2位。

www.youtube.com

いつの間にか布団に吸い込まれており、午前3時半ごろ寝落ち。

05/31(金)

午前10時起床。2時間ほど布団でYouTubeを見てから起き上がった。一本メール返信をして、今日は地下鉄で登校。学食で食事して教室に向かった。

ここ二日の講義時間延長を鑑みて、集中講義最終日の今日は1時間早い午後2時開始。資料の4章が全部解説された。これまでの講義で培った知識やイメージを総動員して、ついに講義の最終目標だった定理の理解までたどり着けて感動。初日は板書が遅くて退屈とか言っていたが、終盤は逆にそうでないと途中で置いて行かれたと思う。最近セミナーで復習した線形代数も非常に役立った。最後の余談では自分が今まさにセミナーで扱っていることに触れられて、大変興奮した。

実はこれまでの講義で結構質問を飛ばしていて、たいていは些細なミスの指摘だったのだが、今日は証明における本質的なミスを発見した。期待値の記法によってパッケージ化し、確率変数の意味を考えることで等式を示すのは、イメージとして把握しやすいもののミスが怖い。総和記号での厳密な計算もできると安心。

今日もしっかり4時間かかり、午後6時終了。ホスフィンと食事して帰宅した。ちんたら歩いていたら午後7時からCFがあることを思い出し、早歩きでギリギリ帰宅に成功。CF #949 div.2に出た。

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

Aは数の大きさに対するスコアとして2べきが最適で、制約の範囲内に必ず存在する。Bは[n-m,n+m]のbitwise ORで、bitごとに考える。Cは2進数表示したときの桁数が\pm 1で遷移していく形になっている。上限があるので、途中の値はできるだけ小さくしておく。

Dはまずaとして素数を選ぶのが良い。すると積の一致が2数の選び方の一致になる。そこで使う素数を頂点、2数の選び方を無向辺だと思うと、数列は長さn-1のパスになる。正確には頂点の共有のみを許すウォークか。また自己ループも可。そして、使う素数の種類数つまり頂点数をできるだけ少なくしたいので、完全グラフの辺をできるだけ使いたい。k頂点使うとすれば、kが奇数ならそのまま、偶数ならk/2-1本取り除くことで一筆書きが可能になる。よってkに対し可能なnが求まるので、あとは気合いでパスを構築。

Eはaの値を横軸に、区間を縦軸にして考えると、ある区間から左右を向いて「見えている」区間、つまりa_i\lt a_j\lt a_kかつ[l_i,r_i]\cap[l_k,r_k]\subseteq[l_j,r_j]なるjが存在しないような辺(i,k)だけ考えればクラスカル法が行える。aタイブレークは適当にやってよい。区間setを使って実装した。

FはO(n^2)が間に合うと信じたが16secかかって全然ダメ。自分の書いたコードにおいてMEXを計算する集合からの削除操作がundoのみであることを利用し、双方向連結リストでMEX関連の操作を全部定数時間にできたのは楽しかった。

5完7位。振り返りをしている間にyukicoderが始まりそうになったので、録画を続けたまま参加した。yukicoder 431。

yukicoder contest 431 - yukicoder

Aは丁寧に式を写す。BはNからdfsで全探索。メモ化しなくても通ったのはよくわからない。Cはかなり時間がかかってしまった。k\times(A+X)=B+XとおくとX=\frac{B-kA}{k-1}となるので、kXをそれぞれ\sqrt B以下で全探索すればよい。Dは1文字につき25回聞けるから、全部違ったら最後の1文字にすればよい。ただしその部分でバグらせてしまった。

Eはひし形の条件を対角線が中点で直角に交わることとし、その対角線を全列挙して数えた。FはAのうち安いものk個を購入し、その際高いたこ焼き器に割引率の高いクーポンを使いたい。つまりABをソートし、適当にずらしながら積和が計算できればよいが、これは片方を反転して畳み込む典型問題。

Gは、次に使われる椅子の候補として、人が座っていない椅子の区間に対しその真ん中の椅子だけ考えればよい。これらを気合いで管理する。HはbitDP。

全完、CとDで手間取ったのが響いて7位。CFの振り返りを終わらせ、追加でyukicoderの振り返りも撮った。

www.youtube.com

午前3時過ぎ就寝。

06/01(土)

午前8時に目が覚めてしまい、ニコニコ動画を見ていた。「The Game of Sisyphus」という苦行系ゲームの淫夢実況。適切な倍速・カットがないと見ていられない苦しさだった。調べたら最近VTuberの配信でもちょくちょく扱われていたらしいが、こういうゲームの配信が人気とはいったいどうなっているんだ……。

www.nicovideo.jp

二度寝するのを諦めたつもりだったが、布団に横たわったままでいたら正午くらいに寝落ちしてしまったらしい。起きたら午後1時45分だった。慌てて飛び起き午後2時からUniversal Cup。シーズン3の第0回目、トライアルコンテスト・Americaセットに出た。

https://qoj.ac/contest/1695

書く

急いでシャワーを浴びて、午後9時からABC356。

AtCoder Beginner Contest 356 - AtCoder

Cまではよい。Dはbitごとに数えればよく、あとは算数。10進数での似たような計算は最近のSRM855Medで苦しんだ記憶がある。Eは同じ値をまとめて処理することにして商を固定すると調和級数。Fは値の大小関係で隣り合う、差がKより大きいペアを列挙した。

Eまで10分弱、Fもそこから9分で解いてなかなか調子が良かったのに、Gが解けなかった。575点だからといって舐めていたつもりはないのだが……。苦しんでいる最中に順位表を見るとみんな解けていなかったのでちょっと安心した。

1m泳ぐときの体力消費率A/Bの昇順に並べたとき、Bが累積MAXを更新する泳ぎ方以外は不要。それらを取り除いた中からA/Bの昇順(これは同時にBの昇順にもなっている)に三つ泳ぎ方を取り、二つ目の泳ぎ方を一つ目と三つ目の泳ぎ方で再現したとき、必要な秒数がどうなるかを考えた。

計算を進めると常に二つ目の泳ぎ方のほうが良いという結論に至ったため、最適解は並べた泳ぎ方から隣り合う二種類を組み合わせるものに絞られる。特にA/B\times DCをギリギリ超える泳ぎ方と超えない泳ぎ方を選ぶべき。このようにして解いたところ12ケース落ちで、適当に探索範囲を増やして少しACするテストケースを増やしたところでコンテストが終了した。

解説を読んで自分がどこでミスしたかに気付いた。ある泳ぎ方を別の泳ぎ方で再現する部分で、自分はベクトル(1,A/B)を考えていたが、ベクトル(B,A)で考えなければならなかった。言葉で言えば、1mあたりの体力消費「率」を揃えるはずだったのに、実際に1m泳いだときの「量」を揃えてしまった……とでも言えるだろうか?

ベクトル(B,A)をピッタリ再現できるとは限らないものの、「率」つまり傾きを一致させることはできて、そのときより大きなBが得られるなら元の泳ぎ方を無視してもよい。この操作が凸包を取ることに対応する。前提の部分で躓いているように見えるのに後の議論は正しかったらしく、凸包に含まれる泳ぎ方だけ残して投げなおしたら通った。

Fまでの6完最速で17位。AとBをNibblesで実装しておいた。Aはピンとくる書き方がない。Bはfoldrで先頭要素から残りを引こうとしたが、全然短くならなかった。まずリストを反転する必要がある。さらに引き算のオペランドの順序も重要だから、special foldsが使えない。

www.youtube.com

午前2時頃布団に倒れこんで就寝。

06/02(日)

午前7時頃目を覚まし、寝たり起きたりしつつハーメルンを読み進めていた。

正午くらいに「私が白亜の神鳥と呼ばれるまで」を読了。勝手に祀り上げ救いを求める人間の様子に少しイライラしてしまったが、神鳥は罰することなく、もちろん応えることもなく無関心を決め込む。上位存在としては完全に正しい反応なのだろう。自分はそこまで高い視座を持つことができなかった。

syosetu.org

布団を出て、TCBの2024/05回に参加した。来週火曜日までなので、感想は来週の週記に回す。

https://techful-programming.com/techful/event/5706

論文を読んでいたら午後8時を回っていたため慌ててシャワーを浴び、午後9時からARC179に参加した。

AtCoder Regular Contest 179 - AtCoder

AはAをソートすればよさそうだが、そんな簡単なわけがない。制約を確認したら負の数があったので、K\le 0が問題。この場合は累積和のすべての点でK以上になっていてほしいから、逆に降順ソートが最適ということになる。\sum A\lt Kなら不可能。

BはbitDP。一瞬、各Bに対しどの数が出現したか全部持とうとしたが、冷静になるとX_Bだけ見ればよい。状態数N2^Mで遷移がM通りなので、遷移先の計算は定数時間で行いたい。これにはX_B=AなるBを集めたbitを計算しておくとよい。

Cは最大値と最小値なら必ず足せるらしい。もっと一般化して小さいほうからk個目と大きいほうからk個目が足せると思い込んだが、それは正しくない。これに気づかず、また実装ミスも相まってペナを二つ出してしまった。冷静になると、最大値と最小値を足すたびに挿入位置を二分探索することで、常にソート済みの列が手に入る。最初のソートも合わせて比較回数は2N\log_2 Nと見積もることができ、足りる。

Dは解けなかった。ゲートの移動まで一緒に考えるのが辛かったので、まずゲートが設置されたことのある頂点集合を決めて考えてみた。するとそれは部分木をなすこと、操作の始点と終点として葉を含むことが分かった。よって決め打った頂点集合の外側を木dpで、内側をゲート移動を使用しない通常の木上の巡回で考えれば良さそう。

ここで後者は有名問題であり、最遠点対を始点と終点にすることで経路長を最小化できる。ここから頂点集合が直径を含むだろう、つまり木dpの根として木の中心を選んでよいだろうと考え、実装。しかし3ケース落ちてしまった。残り時間は14分しかなかったので、修正を諦めて根をランダムに試していた。1ケース落ちまで減らしたものの時間切れ。

結局、直径を含むというのが嘘だった。よって全方位木dpで根をすべて試さなければならない。自分は頂点集合の外側について考える際、何度もゲートに戻ってくると考えて面倒なことをしていたが、実は2回以上戻ってくるならゲートをもう少し遠くまで持っていったほうが良いらしい。この考察ができていると、全方位木dpに拡張できるような実装が手に入る。

3完140位。

www.youtube.com

5月の読書記録をツイートした。良いペースで読み進めていたが、下旬はハーメルンに負けてしまい、結局一日一冊ペースには届かなかった。また積読の増分も残念ながら正。ちなみに今、購買に受け取っていないラノベ新刊が10冊溜まっている。6月も積読は増える一方になりそうだ。

しばらく日記を書いて午前4時前に寝た。

週記(2024/05/20-2024/05/26)

05/20(月)

午後3時過ぎに気合いで起床。半からインターン先定例会に出席した。祝日で2週連続休みとなり、さらに学振の申請書を書いていてもう1週休んだため、実に4週間ぶりとなる。しかも来週は集中講義があってまた休むことが確定している。

進捗報告では今朝方数時間稼働した分の話をした。最近タスクもふわふわしていて、いよいよヤバい。3月末に何度か行われたミーティングが相手ボールのまま途切れているので、今後のタスクを明確化するためこれに関して連絡を取ってみると述べた。

勉強会はキャリアプランの話。ストレート進学とは少し異なる経緯で博士号をお持ちの方なので、そのあたりを突っ込んで質問させてもらった。自分は一度アカデミアから離れると仕事の方に流されて二度と戻ってこられないだろうなあと思っているので、参考にはできないものの、興味深い話だった。

先週の週記を書き進め、午後11時過ぎに先々週の分と同時に投稿した。そして半からCF #946 div.3に参加。

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

Aはまず2x2を配置して、残りのマス数を考える。Bは2回変換すると元に戻る。Cは2か所一致するケースを、3か所目が一致するかしないかを問わずに数え上げ、そこから3か所一致するケースを引いた。Dは文字列sに従って移動した先が(x,y)だとすると、(x/2,y/2)に移動する文字列を取り出せばよい。空の操作列は許されていないため(x,y)=(0,0)がコーナーケース。

Eは現在のhappinessを状態として所持金の最大値を管理するdp。Fはチップの座標を(x,y)で保持するsetと(y,x)で保持するsetを同時に管理し、端から削除していった。

Gはかなり苦しんで、最終的には後ろから貪欲を行った。それまで出現したcを優先度付きキューで管理し、x円稼ぐたびに買えるだけ買っていく。残り金額的に買いきれない場合は、c\leftarrow c-xとして中途半端に支払ったことにする。優先度付きキューを使う貪欲はUniversal Cupでは自分がよく担当するが、チームメイトがしばらく取り組んで貪欲っぽいという結論になっていないとなかなか見えないらしい。

Fまでがまあまあ早かったので、全完に1時間かかっていても11位に滑り込めた。

www.youtube.com

ハーメルンを漁ったりネットの記事を読んだりしていたはず。ゴミ出しをするつもりだったが、その前に眠気に負けて布団に倒れこんでしまった。午前4時半ごろだろうか。

05/21(火)

午後2時起床。先週土曜日に頂いたメールに、今更ながらお礼のメールを送った。まだ来ていないフィードバックには触れるかどうか迷ったが、ふんわり催促するつもりで少しだけ言及しておいた。

昨日出したメールにも返信が届いており、また別の論文が紹介された。ありがたい話。別便で詳細なフィードバックまで頂けるとのことだが、そうなるとお礼のメールをどのタイミングですればよいか迷う。

週記(2024/05/13-2024/05/19) - kotatsugameの日記

外出し、大学生協で食事とラノベ受け取りを済ませてきた。郵便受けを覗いたら海外にいるたいぺーから絵葉書が届いていた。

昨日の定例会で宣言した通りミーティングに関して連絡を取ってみたら、この2か月向こうでいろいろ議論されていたらしく、思ったより大きな話になっていてびっくりした。そうして手間暇かかったものが降ってくるわけだが、果たして自分がそれに見合った働きをできるのか。

夜までセミナー準備をして、午後9時過ぎにゲーセンに向かった。この時間からだと閉店までいても10クレしかプレイできなかった。ただし成果は新曲を埋めて理論値三つとなかなか満足できるもの。チュウニズムに収録されているツユの楽曲は全部理論値で揃えているので、「アンダーキッズ」も出せてよかった。台をひたすらど突く譜面。

油そばを食べ、ドンキに寄って帰宅。シャワーを浴びずに布団に入りたくない気持ちが眠気と衝突した結果、カーペットの上で横になっていた。そのうちさすがに寒くなったので諦めて布団に入り、改めて就寝。午前2時くらいだったと思う。

05/22(水)

午前7時半起床。しばらく横たわったままハーメルンを読んでいたが、あんまり二度寝できる気配がないので、起き上がってセミナー準備を終わらせてしまうことにした。昨日浴び損ねたシャワーを済ませ、午前10時くらいから取り組んでいた。

昼前にABC354の学生2位賞品としてアマギフ5万円が届いた。

12時台の混雑を避け、午後1時を回ってから学食に行った。昨日もそうだったが今日も非常に天気が良く、雲一つない青空が気持ちいい。気温もパーカーとTシャツで原付に乗れるくらいでちょうど良い。まさに理想的な初夏という感じだった。

帰宅してセミナー準備を続け午後4時過ぎに完成。セミナー参加者にメールで送った後、再度大学に向かった。今日のサークル活動は対面で行われる。

活動内容は普段と変わらずバチャ。今週から赤diffが追加されたとのことで、後ろから解こうとした自分はその問題にやられてしまって0完太陽に終わった。解説をチラッと読んだら超シンプルな不変量が書いてあってひっくり返った。自分はもっと条件が必要だと思っていて、複雑化したものをどうにか扱おうとずっと苦しんでいた。

https://kenkoooo.com/atcoder/#/contest/show/49f799ce-d508-4d25-ac3a-393b4eb7861a

ひとしきり駄弁って午後8時頃解散。帰宅した後、今日の問題と改めて向き合った。不変量を定めた後の解説は読んでいないので、そこを自力で埋めることを目標にする。ところがTLEのつもりで投げたコードがWAになってしまった。

実はよく覚えていないのだが、状況から考えるとこの後すぐふて寝したらしい。時刻は午後9時過ぎ。

05/23(木)

午前2時起床。自分が昨日どのような経緯で布団に入ったのか思い出せず、ちょっとした恐怖体験だった。

寝る前に投げたコードを確認したら考え違いを見つけた。修正するとWAが消えてTLEだけになり、そこから探索範囲を絞ってACした。この計算量改善はほとんど自明みたいなもので、考え違いが影響してうまく見えなかったようだ。振り返るとシンプルできれいな問題だった。扱いやすい形の不変量を発見するのが難しい。

atcoder.jp

ラノベを2冊読んだ。1冊目、「メイジアン・カンパニー」7巻。「夜の帳に闇は閃く」は「キグナスの乙女たち」の枠を上書きする形で書かれたようで、これまで交互に出版されていたパターンが崩れた。冒頭で「夜の帳に闇は閃く」の案件がようやく解決したと匂わされていた。作中時間に1年のずれがあるので、長くかかったと言えるのではないか。

あらすじでは司波達也の行動がスポンサーに掣肘される不自由な巻に見えたが、結局は好き放題行動していたように見える。ただ、そちらのほうが国益に叶うという理由付けは丁寧に行われていた。久しぶりに「再生」で人を救ったり、個人の力を背景に戦争に介入したりと、満足のいく活躍ぶりだった。

2冊目、「キグナスの乙女たち」6巻。黒羽姉弟の視点がたくさん用意されており、扱う案件も同じということで内容的には半分くらい「夜の帳に闇は閃く」だった気がする。また話の流れで司波達也と主人公二人が顔を合わせるかと思ったが、司波達也側が影武者の試験運用をしたせいで叶わなかった。ただこのシリーズでは初めて司波達也のセリフがあって感動。対面も時間の問題だろう。

3時間弱仮眠して午後0時半起床、登校。学食で昼食を摂って午後1時半からセミナーを開始した。今週も追加の先生二人が来てくださった。

今回はかなりしっかり準備したつもりで、その甲斐あってか終始和やかな感じで進んだ。何の道具を使って何を解こうとするか、というモチベーションを丁寧に説明したのはかなり重要なポイントだったと思う。他の論文から学んだ背景や事例も交えて話すことができて、手ごたえがあった。ただアドリブだったためセミナー資料になく、その場で細部を再現することもできなかったので、次回少しフォローしたい。

午後4時終了。その後先生としばらく議論して午後7時半に解散し、学食で夕食を摂って帰宅した。

Amazonから荷物が届いていた。なんと先週火曜日に注文したもの。7点買ったうち一つだけ配達予定日が05/25になっているのは気づいていたが、それ以外はすぐ発送してくれるだろうと高をくくって注文。すると全部まとめて05/25到着予定と表示されひっくり返ってしまった。予定より少し早かったのだけはありがたい。

眠気に耐えつつラノベを読み、午前0時からSRM855に参加した。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19800

Easyは爆弾の配置を決めれば数字が確定するので、prefixを決めた後の場合の数が2べきで簡単に求まる。よって先頭から順に決めていくとよい。直前のマスが爆弾でない場合、爆弾を配置したほうが辞書順で大きくなることに注意。*がどの数字よりも辞書順で小さいためXを2進数表記して爆弾の配置を求めればよいと考えたが、このせいでずれてしまう。

問題文にN\le 100と書いてあったので__int128を持ち出して実装したのだが、いざテストしようとしたらvalidatorにN\le 60と言われ弾かれてびっくりした。問題文が間違っていたらしい。N\le 100でも先頭N-60文字を*で埋めればlong longで処理できるものの、SRMでそういう小手先の調整をするのは信じられない見落としで死んでしまう確率が無視できないと思っている。

Medはもう大変。A=1で2回解くことにし、桁数を決め、先頭と末尾から見て食い違う位置を決めるというのが方針。あとはひたすら頑張って数えた。桁dpで解くことも考えたが、先頭と末尾の一致する部分をどう扱ったらいいかわからなくなったので、気合いの算数で全部処理した。計算量に気を使わなくていい制約なのはありがたい。

残り10分くらいでサンプルが合ったものの、愚直と比較したらずれていて頭が真っ白になった。何とかoff-by-oneのバグを見つけて直し、提出。Hardは見る時間がなかった。チャレンジフェーズでは自分よりギリギリに提出されたMedのコードを写経していた。しかし実行するとサンプルすら合わず、写経ミスを探しているうちに時間切れ。その提出は結局システスで落ちていたのだが、サンプルが合っていなかったのかは不明。

自分は何とか2完を確保して5位、2904→2883(-21)。今日の問題は、最近のSRMの中では比較的質が良かったと感じた。ただしMedが面白かったかというとそんなわけはないので、どこから得た印象なのかは謎。

その後すぐラノベ「メイジアン・カンパニー」8巻を読了。今回の司波達也のバトルは、幻術の中で次から次へと現れる敵を魔法を使わず倒していくというもので、無双にはならないしシチュエーション的にも好みではなかった。一応前半に活躍するシーンがあるのでOKという感じ。

さて、この巻が現在の最新刊である。これまで立て続けに12巻読んできたが、本編に引き続いてやはり面白かった。佐島勤さんの今後の予定は、7月に完全新作を出してその次に「夜の帳に闇は閃く」の2巻を書くらしい。てっきり「キグナスの乙女たち」に吸収されたものだと思っていた。

6月分のラノベ新刊をチェックして24冊注文した。新作に手を出すのを控え目にした。SAOの新刊が2年弱ぶりに出るが、すでに予約が品切れとなっていて残念。

明日は数学科の友人を自宅に招いて遊ぶ予定。そこで部屋の掃除をしてゴミを出した。こうなると月曜日に出し損ねて正解な気もする。

その後すぐ寝ればいいものを、うっかり論文サーベイを初めてしまった。午前8時に布団に入り、2時間ハーメルンに溶かして就寝。

05/24(金)

午後0時半起床。今日遊ぶ友人は昨年夏に遊んだのと同じ人である。

北京餃子で食事。ドンキに寄ってお菓子とお酒を買い午後2時くらいから家飲みを開始した。今日の相手はホスフィンではなく一昨年院試ゼミを一緒にやった数学科の友人の一人。

週記(2023/08/14-2023/08/20) - kotatsugameの日記

眠気に負けそうになっていたら、その友人からLINEが来た。昼食に出かける前に荷物を置きたいから部屋に行っていいか、とのこと。承諾の返事をして布団から這い出した。これがなかったら、もしかしたら二度寝からの遅刻をかましてしまったかもしれない。

合流して出かけ、今日も北京餃子で食事。店がフォーラス地下から移転して以来だった。食後にドンキでお酒とお菓子を買い、帰宅。午後3時くらいに部屋について遊び始めた。

まず「Blade Rondo」をプレイした。第五弾単体で遊び、次に第一弾と混ぜるルールでも遊んだ。後者では低コストの物理攻撃を連打して初勝利……のはずが、とどめに使用した「羽ばたきの刃」の追加効果にコストがあるのを完全に見落としておりノーゲームとなった。申し訳ない。そういえば、調べてみると前回遊んだ際には第三弾までしかもっていなかったようだ。次の機会には第四弾でも遊びたい。

次にデュエマをプレイした。友人は未経験だったらしく、大まかにルールを説明した後、カードの束から文明だけ揃えて40枚抜き出したデッキで対戦した。自分はデュエマというだけで楽しかったものの、デッキが弱すぎる点はよろしくなかった。構築済みデッキを買ってきたほうが良かったかもしれない。最近「攻めの王道」「守りの王道」というおあつらえ向きの商品が出たのだが、町のカードショップにはもう「攻めの王道」しか残っていなかった。

カードゲームはこのくらいにして、友人が持ってきてくれたSwitchで桃鉄ワールドをプレイした。以下のツイートにあるようなミラクルのほかにも、ピッタリの出目を出して目的地マスにたどり着くことが何度かあったりして、全体的に運が良かった。最後に急激な追い上げを受けつつ、3年決戦で無事勝利。

午後8時頃解散。眠気と闘いながら片づけをして、午後10時に寝た。

05/25(土)

午前4時半起床。

ハーメルンで「浅野学秀の双子の妹がエンドのE組に入った話」を読んだ。享楽的なキャラはあんまり好きではないが、浅野学秀の関係者というだけでニヤニヤしてしまう。今のところは理事長・浅野學峯ばかり登場しているので、今後の学秀との関わりに期待。

syosetu.org

その後はずっとラノベを読んでいた。「俺は星間国家の悪徳領主!」8巻を読了。面白かったが、皇子が最初からこちらの味方をしていたという展開には少し違和感があった。主人公に対して抱く鬱屈とした感情は嘘ではないようで、作品の雰囲気としてもその理由だけで利害を無視して裏切るのは不自然ではない。まあ最後に主人公が勝っていればなんでもいいか!その点は今回も大満足だった。

シャワーを浴びた後、布団でニコニコ動画桃鉄実況をいくつか見ていた。ここで世界旅行ボンビーの仕様を知ったのだが、他のプレイヤーや目的地マスの近くに行く確率は少し高いらしいから、昨日のような展開はいくぶん発生しやすいようだ。

午前11時半から2時間ほど仮眠。午後2時からUniversal Cupのチームで5hのバチャ、300iq Contest 3を走った。

Dashboard - 300iq Contest 3 - Codeforces

書く

少し日記を書いて午後9時からABC355。

Tokio Marine & Nichido Fire Insurance Programming Contest 2024(AtCoder Beginner Contest 355) - AtCoder

書く

www.youtube.com

午後11時半からCF #947 combinedに出た。

Dashboard - Codeforces Round 947 (Div. 1 + Div. 2) - Codeforces

書く

www.youtube.com

ラノベを読んでいたが寝落ちしたらしい。ブラウザの閲覧履歴が午前6時まで残っているので、それ以降ということになる。詳しい時間は不明。

05/26(日)

数十分の覚醒を数度挟みつつ、午後9時までぐうすか寝ていた。

ハーメルンで「お詫びにチート全盛りしたけど、現代日本じゃ使い道がない。」を読了。序盤は世間からひたすら隠れていくスタイルかなと思ったが、結構露出していた。いいね。

syosetu.org

午後11時半からCF #948 div.2に出た。

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

Aはn\ge mかつ偶奇が一致。Bはまず通常の2進数で展開して、1,1,a-1,0,a+1に置き換えていく。最初はn\le 30なので、繰り上がりを考えてもn\le 31で収まる。Cはまず全体のLCMがaに含まれるか判定。これは全要素が\max aの約数であることと同値である。もしそうなら、どんな部分列を取ってもLCMは\max aの約数となるため、それを全探索できる。

Dは大変だった。各列についてそこをspecialにする方法がn通りあるため、それらを全列挙して重複を数えればO(n^2m\log nm)で解ける。一方specialにする列iを一つ固定し、それ以外の列とXORを取ると、列i1にする行を決めるごとに同時にspecialになる列を数えられる。こちらの解法はO(nm^2)なので、組み合わせると何とか通った。

Eはコンテスト時間内に解けず。最初、頂点1に到達できるかどうかで分類しようとしていたが、冷静になるとこの情報は全頂点から到達できる場合に無意味となるためよくない。コンテスト終了後も考えて、2本のパスを管理する方法を思いついた。

1本目のパスの末尾がp、2本目のパスの末尾がu_1\lt u_2\lt\dots\lt u_kで、p\lt u_1かつp\not\leftarrow u_1となるようにする。v:=u_k+1を追加する際、u_k\leftarrow vならu_{k+1}:=vとして次に進む。そうでなくp\leftarrow vなら(p,u)=(u_k,(v))として次に進む。どちらでもない場合、あるインデックス1\le i\lt kが存在して、u_1,\dots,u_i\leftarrow vかつu_{i+1},\dots,u_k\not\leftarrow vが成立する。このときu_{i+1},\dots,u_kpの後ろに繋ぎ変え、再度(p,u)=(u_k,(v))とする。このアルゴリズムで2本のパスに分解できる。

4完48位。

www.youtube.com

ハーメルンで「傍に立つ君は完璧で究極のアイドル」を読了。シリアス展開になりかけるとオリ主のチートで全部吹き飛ばされるため、楽しく読めた。そういえば昨年、ハーメルンのランキング常連だった「推しガイル」をこっそり読んでいたのだが、これが時系列的に原作より前だということを初めて知った。星野アイと星野兄妹の設定がややこしすぎて二次創作を読むだけでは理解不可能。

syosetu.org

syosetu.org

シャワーを浴びて少しだけ日記を書き、午前10時に布団に入った。そこからうっかりハーメルンを読みふけり、「ピックアップガチャ(固定)スキル持ちの転生TS美少女が行く、激動昭和なお話」を読了。神様に振り回された主人公が女性特有の危険にさらされており、非常に辛い。できるだけ早く超常的な能力の扱いに習熟し、わかりやすい強さを身に着けてほしい。

syosetu.org

午後0時半就寝。

先週はラノベをたくさん読めたが、その反動だろうか、今週はかなりの時間をハーメルンに吸い取られてしまった。ネット小説からは逃れられない。このままでは一日一冊ペースが台無しになってしまう。

週記(2024/05/13-2024/05/19)

05/13(月)

徹夜状態で午後1時過ぎに登校したところから。着いてみたら集合の午後2時まで思ったより時間がなかったので、購買で総菜パンを買って詰め込んだ。

まず2時間ほど話し合いをした。内容は伏せるが学振には関係なし。締め切り当日という修羅場になぜ、と思ってしまった。インターン先定例会については昨日の時点で欠席を伝えてあった。

その後、いよいよ論文をarXivに投稿するため最後の調整を行った。留学生による校正を反映し、その他先生と相談しながらいくつか文章を変えた。アカウント登録などに手間取りつつ午後7時過ぎに無事投稿完了。主定理が既出だった上先生に英語がダメダメと言われまくって、ありとあらゆる点から自信を喪失してしまった論文だが、URLを貼っておく。

arxiv.org

食事して午後8時過ぎ帰宅。ここから学振の申請書を書き上げなければならない。文章が完成した部分については今朝方フォントなども整え終わっていたものの、そもそも文章が完成していない部分が残っているためかなりまずい。しばらくは眠気に負けそうになってうつらうつらしたりしていたが、残り時間が少なくなるとそれどころではなくなって、ひたすらWordと向き合っていた。

日付が変わる直前に何とか提出できた。昨年のものを流用しようとしていたが、今年作った研究計画との整合性が取れず、またそもそも文章量が全然足りていなかったため、結局はほとんど一から書くことになった。

ところで先週の週記はほとんど書けておらず、投稿できなかった。月曜日に投稿するstreakが2021/11以来30か月ちょっと続いていたらしいが、しょうがない。

週記(2021/10/25-2021/10/31) - kotatsugameの日記

カクヨムで「推しにささげるダンジョングルメ」の更新を読んでいたら、書籍版が続刊することを知った。好みの作品なので嬉しい。一般にネット小説は、書籍化された後に更新を追っていると後書きから売れ行きが透けて見えることがある。この作品はちょっと怪しいかもと思っていたので、続刊の知らせには驚いた。

www.kadokawa.co.jp

少し週記を書き進め、シャワーを浴びて午前3時就寝。

05/14(火)

正午のあたりは少し起きてハーメルンを読んでいた。「カードゲームで世界が滅ぶ世界に転生してカードショップを開店したら、周囲から前作主人公だと思われている」が書籍化するらしい。

午後7時くらいに目を覚まし、日付が変わるまでまたハーメルンを読んでいた。「終末世界で英雄賛歌を謳う」を読了。あらすじに「周りの奴は大体脳を焼かれてギャグ寄り」とある。特に気にせず読み始めたが、思ったより好きになれない設定だった。周りのキャラが人間より上位の存在ばかりだったのもあって、世界を救おうとする主人公の行動に見合う真剣さが感じられなかった。むしろ主人公を私情で振り回しているように見えた。

syosetu.org

そういえば健康診断の季節である。実はここ数年サボっているため今年は行きたいなと考えていた。サイトを確認したところ、来週月曜日までやっているらしい。早速明日、水曜日の午後2時半からで予約した。

布団を脱出して食事した後ラノベを開いた。すぐ寝て明日の健康診断に備えようと思っていたものの止め時を見失い、結局寝るのを諦めて昼過ぎまで読んでいた。3冊読了。

一冊目、「凡人転生の努力無双」2巻。面白かったとは言えるものの、1巻ほどではなかったため期待が空振った感じがする。新ヒロイン・新能力も登場するし敵も倒すが、どれも1巻ほど目覚ましい活躍ではなかった。主人公が少しだけ成長した結果一足飛びの強化はなくなり、一方でまだ小学一年生のため行動の自由が少ない。カクヨムでちょうどここまで読んでいたというのもあるかもしれない。3巻以降にまた期待。

二冊目、「幼馴染のVTuber配信に出たら超神回で人生変わった」。実はこれもカクヨムで読んでいた作品だが、最新話にたどり着く前に別の作品に移ってしまい日記では特に言及していなかった。当時読んだ部分がちょうど1巻の終わりまでだったようだ。ただし内容はほとんど覚えていなかった。有名VTuberであるヒロインの配信にリアルの知り合いとして出演したり、最終的に自分もVTuberデビューした上そのヒロインと恋仲になったり、ほかの作品では炎上リスクに過敏になっていた展開が特に気にならなかった点は不思議。

三冊目、「キグナスの乙女たち」2巻。「魔法科高校の劣等生」の後継シリーズ二つは1年半ほど前にほんの少しだけ読み進めていた。刊行順に読んでいたが、司波達也が活躍する「メイジアン・カンパニー」と比べるとこちらは過去キャラもほぼ出ずバトルもなく、読み進めるモチベーションが消えて2巻の途中でストップしてしまっていた。

ということで半分ほどまで読んだ記憶はあったが、内容自体は全く覚えていなかったので今日は最初から読み返した。案の定まったく引き込まれはしないものの、義務感だけでも十分読み進められるくらいには魔法科の世界観や文章に慣れており、無事読み終えることができた。やはりこの舞台でただの青春小説を書くのは無理があったのか、ラストでは陰謀の匂いが漂ってきた。

シャワーを浴びて健康診断へ。徹夜かつ空腹、しかも急ぎ足で来たため少し息が上がっていたが、血圧が多少高いくらいですべて正常だった。血圧が高いのも元からかもしれない。終わらせて外に出たら長蛇の列が出来ていてたまげた。3限終わりの混雑にギリギリ先んじていたらしい。

学食で食事しようとしたら、ピンポイントでこの日・この時間だけどこもやっていなかった。仕方がないので購買でパンを買い、コンビニにも寄りつつ帰宅した。

しばらくラノベを読んで過ごし、午後4時40分からサークルバチャに参加。今日は8問目で詰まり、O(3^N)を1要素固定するなどの定数倍高速化で無理やり通した。想定解の1頂点ずつ塗っていく方法は、普段絶対に考えないから盲点。コンテスト当時は一色だけ全探索しており、これも想定解とは異なる。

https://kenkoooo.com/atcoder/#/contest/show/61b9893f-a73b-41fe-a919-ee49707c8c67

arXivに投稿した論文がbotに捕捉されていた。それだけなら公開した以上当たり前だが、そのツイートが数RTされてTLに流れてきたのには驚いた。よく気づくものだと思う。

午後7時半就寝。

05/15(水)

消えた。

05/16(木)

午前1時頃起床。間で4時間ほど寝落ちしつつ、昼前までにラノベを2冊読んだ。

一冊目、「メイジアン・カンパニー」3巻。帯にもある通り、司波達也がマテリアル・バーストを放つ。そんなの面白くないわけないじゃん、ということで、この巻を読むのは以前からかなり楽しみにしていた。意固地になって刊行順に読んでいたため1年半越しとなったが、ついに手に取れて嬉しい。期待通りの無双っぷりだった。また後半の短編二つからは魔法大学での日常が伺えて、これも良かった。

二冊目、「キグナスの乙女たち」3巻。2巻で垣間見えた陰謀がさらに活発化し、主人公二人をじわじわ囲い込んでいる様子だったが、いかんせん二人には司波達也のような能力・立場がないため、蚊帳の外という感じが否めない。彼女たちが交流を深めているキャラは、読者からすれば工作員。非常にもどかしかった。

シャワーを浴びて登校。今日は時間に余裕があったため、学食で食事した。

午後1時半からセミナー開始のところ30分前に教室に到着。すでに先生がいたので、相談しつつ月曜日に出した論文の更新を行ったり、関係が深い論文の著者にメールを送ったりした。30分で切り上げるつもりがなんだかんだ一段落するまで続けてしまい、その間後輩は先生から数列の極限に関する問題を出されて黒板で解いていた。先生のそういう指導には自分も覚えがある。

午後4時も近づいてから後輩のセミナーが開始。今日は一時間半であっさり終わった。今日話された命題はもともと別の定義の下で扱ったことがあるので、ちゃんと一致しているか確かめようとしたが、混乱してうまくいかなかった。

後輩と二人で学食に行き、今日出されていた問題について話したり、学振の書類を見せたりした。閉店時間の午後8時になって解散。

昼間一通メールを出したが、もう一通出す予定である。帰宅後はこの文面を作成し、先生に確認を取っていた。またついでにいくつか論文を眺めたりしていた。

日付が変わってからラノベを開いた。「メイジアン・カンパニー」4巻を読了。司波達也がちょっとした策を打って監視の目を誤魔化す様子は、スパイ小説を読んでいるような感覚で楽しい。一挙手一投足を国内外から監視されていると思うと窮屈に見えるが、司波達也が最強かつ万能であるため特に緊張感はなく、ちょっとしたギミック程度にしかなっていないのが圧倒的。

健康診断で貰ってきたデンタルフロスを使ってみた。子供のころ親が使っているのを見て興味を持ったことを覚えている。歯垢がいい感じに取れて楽しいが、歯に隙間が空いたような感覚が残り、まだ慣れない。

昼間出したメールにもう返信が届いていた。高名な先生かつすでに退職済みということで、正直返ってくるとは思っていなかったため驚き。さらに研究対象のバリエーションや論文をいくつか紹介していただけたのは望外のことだった。

午前6時前就寝。

05/17(金)

正午前に1時間ほど目を覚ましていた以外はずっと寝続け、午後8時に起床した。昨日文面を作成したメールを送信した。

午後9時20分からyukicoder 430に参加。

yukicoder contest 430 - yukicoder

AはK以下と誤読してちょっと困っていたが、冷静になると以上でも以下でも簡単。BはすべてのKについてその倍数をいちいち見た。BITを使って数えたためdを約数の個数としてO((\sum d(A)+Q)\log N)。Cは勝手に105オーダーの入力だと思い込んでしばらく唸っていた。O(NQ)が通るなら簡単。

Dはお互い一直線に近づいて行って、ぶつかったところから左右をそれぞれ取ることになりそう。よってNの偶奇で決まる。EはロリハをBITに乗せてO(QN\log L)。Fは熨斗袋さんのブログを読み、dpを3x3の行列積で表現する。下の桁から作るようにすれば1で終わるものが答えになる。

noshi91.hatenablog.com

Gは母関数が\prod_{i=1}^N(1-x^{(K+1)i})/(1-x^i)。分母は五角数定理だが、よく見るとその次数をK+1倍するだけで分子も得られる。Hは始点と終点から各頂点への最短経路を求めた後、ワープ移動を考える。移動前後の頂点のうち片方を固定し、もう片方をCHTで処理すればよい。面倒なのでライブラリを窃盗してきた。

Convex Hull Trick Add Monotone | Luzhiled’s Library

1時間ちょっとで全完して3位。

3月に参加したDDCC2024の動画が公開されていた。インタビューが使われたほか結構映り込んでいて嬉しい。

special.discoveryjapan.jp

昨日届いたメールに対してお礼の返信をし、午後11時半からCF #945 div.2に出た。

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

Aは3種類の引き分けが起こる回数を全探索した後dpしたが、冷静になると最初からdpするだけで十分。しかも全探索を再帰関数で書いており、明らかに頭が回っていない。Bは区間のbitwise ORが全体のbitwise ORと一致すればよい。尺取り法で各iに対して必要なkの最小値を求め、その最大を答えとした。

Cは最大であるn/2-1が必ず達成可能。インデックスの偶奇で分け、nを含む方にはn/2+1\dots nを、含まないほうには1\dots n/2を足す。足す際は小さな値と大きな値をマッチングさせると、前者はすべてn+1以上、後者はすべてn以下となる。直感的な貪欲だが実際にうまくいくことを確認するのに少し手間取った。

Dはクエリからまともに情報が得られない。かろうじて(l,x)=(1,n^2),(1,n(n-1)),\dotsと聞くことでaの最大値Aは分かるが……と思ったらこれで十分だった。mとしてありうるのはAの倍数のみで、かつm=iAとすればik\le nである必要がある。よってm=A,2A,\dots,\lfloor n/k\rfloor Aを調べればよく、一つ調べるのはクエリk回以下で可能。

Eはswap可能な要素に辺を張って交換すべき要素を連結にできればよい。uv\gt uを連結にするならl\le u+v\le rであるか、l\lt rかつl\le u+nかつv+1\le rが必要。後者はuvが孤立点でないこととl=rであってはならないことからすぐ出るが、実は十分条件にもなっている。3要素以上を連結にする場合は前者が使えなくなるだけであとは同じ。lに対するrの最小値を区間chminで管理した。1点取得しかしないので遅延セグ木で十分。

Fはa_1b_1の約数を決め打てば解けるが低速。(a,b)をdistinctにしたり、先にa_1の約数を決めて枝刈りしたりすれば間に合うんじゃないかと思ったものの、やっぱりTLEだった。5完11位。

www.youtube.com

ハーメルンから「サイバーパンク居酒屋『郷』~チート持ちで転生したけどやることないのでまったり過ごしたい~」を読了。描写も展開もギャグ寄りすぎるかなと思いながら読み進めていたが、主人公の無双シーンは非常に良かった。サイバーパンク設定に転生という要素を結びつけて主人公の無敵っぷりを補強しているのは上手い。

syosetu.org

このくらいの時間に、AHC033に初提出を行った。思いがけず20位台を記録できて嬉しい。

Toyota Programming Contest 2024#5(AtCoder Heuristic Contest 033) - AtCoder

ラノベを2冊読了。一冊目、「キグナスの乙女たち」4巻。本当に刊行順に読もうとすればこの前にAppendixという外伝があるが、分厚いしまったく別の話だしでさすがに飛ばした。九校戦編ということで、過去の伝説として司波達也ご一行のエピソードがちょくちょく語られたため、かなり満足感があった。陰謀はこの巻では控え目。

二冊目、「メイジアン・カンパニー」5巻。このシリーズは単に魔法科シリーズの後日譚として捉えていたが、4巻ラストから古代の遺物を巡るバトル・宝探しが始まってびっくりした。前の巻では秘密裡に外国へ行くため細工をしていたのに、急を要する状況になると高千穂を経由し完全フリーで移動し始めるのが面白い。誰も司波達也を止められない。

ここまでは本棚を増設した際に整理してあったが、以降は積読に埋もれている。本棚を漁ってみると見事に最新刊まですべて見つかった。ちゃんと買ってあって偉い。

昼になったのでシャワーを浴びて大学生協に向かった。まずラノベを受け取った後、大混雑している学食はいったんスルーして散髪。その後少し空いた学食で悠々食事して帰ってきた。

髪の毛を切ったためもう一度シャワーを浴び、1時間ほど布団でハーメルンを読んで午後3時半就寝。

05/18(土)

午後8時に目覚ましで起床。ひとしきりうだうだした後頑張って身を起こし、午後9時からABC354に出た。久しぶりのスポンサードABC。

Panasonic Programming Contest 2024(AtCoder Beginner Contest 354) - AtCoder

Aは2^d-1\gt Hとなる最小のd。Bは入力のインデックスを答えるものと勘違いして面倒なことをしてしまった。CはAの降順に見てCの累積MINだけ取る。インデックスを答えるのが面倒。Dは2x4の長方形領域が繰り返されるパターン。適当にずらして2次元累積和のように分解し、(A,B)=(0,0)で4回解けばよい。Eは自明。Fは左右に伸ばせる長さを計算して足りるかチェック。

GはSをdistinctにしておくと推移律の成り立つDAGにおける重み最大独立集合(反鎖)を求める問題だから、Dilworthの定理を使って何かできそう。ただしDAGから二部グラフを作ると頂点が倍になるから、どこに重みを割り当てればよいのかよくわからなくなる。

以下のブログを読んでいると、「DAGの独立集合と二部グラフの点カバーは対応する」「二部グラフの点カバーが頂点iと頂点i'を両方含むならどちらか片方は取り除ける」という事実を見つけた。後者によって頂点を重みごとコピーしてよいことがわかり、二部グラフの重み最小点カバーを求める問題になる。もう少しステップがあるかと思ったが、よく見るとフローの最大カットだった。実装したら通った。

miscalc.hatenablog.com

52分で全完し5位。賞品の額が結構大きく嬉しい。コードゴルフはAとBをNibblesで書いておいた。Bでは文字列と数値が入り混じった入力を初めて扱ったが、数列においては数値部分だけうまく取り出してくれており、あまりの便利さに感動した。

www.youtube.com

昨日出したメールにも返信が届いており、また別の論文が紹介された。ありがたい話。別便で詳細なフィードバックまで頂けるとのことだが、そうなるとお礼のメールをどのタイミングですればよいか迷う。

朝までかけてラノベを2冊読んだ。一冊目、「キグナスの乙女たち」5巻。これまで原作キャラの名前だけならいくつも出てきたが、この巻ではついにエリカとレオが登場した。最高。一方で陰謀のほうは影も形もなく、シリーズとしては迷走気味という印象を受ける。

二冊目、「メイジアン・カンパニー」6巻。5巻ラストで遺物に繋がる重要な鍵の一つを見つけたと思ったら、この巻の冒頭で立て続けにもう二つ発見し、あっという間に探し求めていた遺跡までたどり着いてしまった。急ぎ足の展開に驚いたが、実は同様の遺跡が世界各地に散らばっているらしい。それらを訪ねていくストーリーだったようだ。

実は先週の週記は今週を通してちまちま書き進めており、午前8時くらいにひとまず投稿できる状態となった。ただし2回の5hバチャは穴あき。今度は今週の日記を書き、午後1時就寝。

05/19(日)

午後7時起床。来週のセミナー準備のためしばらく布団で論文を読んでいた。

布団を脱出して食事し午後9時からARC178。

AtCoder Regular Contest 178 - AtCoder

書く

www.youtube.com

ラノベ「夜の帳に闇は閃く」を読了。刊行順でここに位置する。また新しいシリーズだが時系列は「キグナスの乙女たち」とほぼ一緒なので飛ばさず読むことにした。4年以上前に読んだ「司波達也暗殺計画」シリーズのキャラがサブ主人公的立ち位置にいてびっくり。記憶はまだ結構残っていた。そのシリーズと同様、司波達也を中心に動く人々の話であり、周囲から見た司波達也が念入りに描かれるのも同じだった。好み。

そういえば電撃文庫の装丁は最近ちょっと変化し、あらすじがカバー袖から裏表紙に移動した。手元の本で確認した限りではおそらく2023年から。この変更はそれ以前から続いているシリーズには適用されていないのだが、「夜の帳に闇は閃く」はちゃんと新シリーズ扱いされ、新しい装丁になっていた。

しばらく日記を書いた後、午前7時から久しぶりにインターンの作業を開始した。現在サービスとして動いているコードを読み、やりたいことの実現可能性を探るのが現在のタスク。使ったことがないとは言わないがほとんどない言語にまったく知らないフレームワークでかなり大変だったものの、粘っているうちにだんだん読めるようになってきてワクワクした。

必死に読んでいた部分は残念ながら見当違いだったが、そこで得た知識をもとに適切にコードを検索するなどして、無事目的に合致しそうなものを発見することに成功した。Chromeの検証ツールがかなり便利。ただし一月ほど前に眺めた時は何もわからなかったはずなので、ここにも先ほど得た知識が効いているのだろう。

そうしているうちに昼間になっていた。定例会まで2時間ちょっとしかないが徹夜よりはマシなので、目覚ましをたくさんかけて寝ることにした。午後1時就寝。

今週は全力で現実逃避した結果ラノベを11冊読めた。5月は今のところ一日一冊ペースを上回っている。しかし数えてみると、買うペースはさらに速かったらしい。ラノベの出版ラッシュは月末にもあるから、残念ながら今月も積読の増分は正になりそう。

週記(2024/05/06-2024/05/12)

05/06(月)

午後1時45分、執念で起床。午後2時からUniversal Cupのチームで5hのバチャを走った。今日は300iq Contest 1とやら。

Dashboard - 300iq Contest 1 - Codeforces

書く

先生からまたメールが来ていた。今度は2010年の論文の主結果が自分の結果を包含しているらしい。確認しに行ったところ、もう一目見て同じだと確信できるくらいの一致具合だった。主定理、爆破……。南無。

今更どこからこの論文を見つけてきたんだ、と思いつつ先週土曜日に見つかった論文の後ろのほうを読んでみたら、「主定理はこの論文の式〇から従う」と書いてあった。なんじゃそりゃ。ただconclusionの章を読むと「登場する変数が減ってシンプルになった」と言い訳していて、これには思わず納得してしまった。

翻って自分の主定理はどうかというと、登場する変数の数は変わらない。一方2式の間の双対性みたいな話は二つの論文のどちらにも見当たらなかったから、これが新規性だと強弁する余地はまだ残されていそう。もしかしたら現実が受け入れがたくてまともに論文を読めていないだけかもしれないが。

まあメインの結果が消えてしまったことに違いはない。先週と異なりなぜか今回は特にショックも受けず、日付が変わるまで淡々と週記を書き、投稿した。

その後セミナー準備。2010年の論文はいったん放置して、先週末から準備を進めていたものの続きに取り組んでいた。シャワーを浴びて午前4時くらいに布団に入り、3時間ほどラノベを読んで就寝。

05/07(火)

午後1時に三菱UFJ銀行から電話がかかってきた。Yandex Cupの賞金振り込みに関する確認で、何のお金か聞かれ大会賞金だと答えると、額(米ドル)・適用される為替レート・手数料が通達された。少ししてアプリで残高を確認したらもう入金されていてびっくり。レートは1ドル153.11円だったが、一週間前に一瞬160円を突破したのを考えるとちょっと惜しい気もする。まあ大会当日のレートと比較すると1万円以上上乗せされているので十分ラッキーか。

ちなみに、次の月曜日にはこの送金について書かれた書類が、銀行に登録しておいた住所つまり実家へと届いた。メッセージ欄にPAYMENT OF PRIZEとあったから、おそらく電話での質問はこれとの整合性を確認していたのではないかと思う。

もう一度寝直して、起きたら午後8時だった。しばらくスマホを触ってゴロゴロした後、コンビニに出向いてパンやおにぎりを買い漁ってきた。

さて、論文が崩壊してしまったわけだが、一方で学振の学内締め切りが来週月曜日に迫っている。今更システムにログインして申請書の作成を開始した。昨年の申請書は内容部分しか残していなかったものの、先生の研究者番号など調べなければならない情報がブラウザのオートフィル機能に結構残っていて、ホイホイ埋めていくことができた。

埋めたところでやる気が尽きた。申請書の内容は……先月別の支援プロジェクトのために書いたものがあるし、それを流用すれば何とかなるんじゃないだろうか。少し休憩と言い訳しつつラノベを手に取ったら、そのまま朝まで止められず4冊読了した。

「クラスで2番目に可愛い女の子と友だちになった」6巻。主人公のハーレム状態を嫉妬するモブ視点から始まり、トラブルの予感から陰鬱な気持ちに。しかしいざ変な噂を流されても主人公が周囲の目をあまり気にしていないため辛い話にはならなかった。最後に噂の元凶と話し合うシーンで性格の醜さを一方的に糾弾していたところにも、そういう身内以外への興味のなさが表れていると思う。なかなか苛烈だったが、なあなあで和解するよりは良かった。トラブル以外のシーンは相変わらず面白かった。

ネトゲの嫁が人気アイドルだった」4巻。3巻発売から丸2年空き、まさか続刊するとは思いもしなかった。内容は……怒涛のようにイベントが押し寄せてきて個々の印象があまり残っていない。文化祭のライブで失敗するとか、舐めていた相手にネトゲの対戦でボロ負けするとか、よく考えると好きではない展開があったように思う。読んでいるときはすぐ次のシーンに移るからあまり深く考えていなかった。

このシリーズは1年近く新刊がないので打ち切りになってしまったのだろうと考えている。

週記(2023/02/20-2023/02/26) - kotatsugameの日記

「才女のお世話」7巻。マネジメント・ゲーム後編は完全に主人公が無双していた。最高に面白かった。学園を飛び出して現実の企業・ビジネスマンとやり取りし、その中で存在感を示すシーンや、メイド長が主人公の才能の開花を見守るシーンは、あまりにも好物すぎて大興奮だった。ビジネス系の話だと大財閥を動かしたりする話を好んできたが、このくらいの規模の話もまた楽しいものだと気づくことができた。

続けて「才女のお世話」8巻。前の巻のピリピリした感じから一転しての日常回で、主人公の休日の生活を垣間見るのは楽しかった。途中で屋敷の護衛と組み手を行い、ここでもほぼ無双していたのが特に面白かった。そういう話ではないはずだが……。1巻ラストの護衛を倒し屋敷に侵入する展開は、ヒロインと結ばれることの困難さを示すだけだったはずなのに、いつの間にか格闘技の才能の証左となっていたようだ。詳しい描写まではもう覚えておらず残念。

午前9時半くらいから3時間ほどセミナー準備をして就寝。途中でABC346の賞品、アマギフ1万円が届いた。

05/08(水)

午後4時半起床。40分からサークルバチャに出た。今回は特に問題なく全完。10問目がマトロイドになることは知らなかったし気づいてもいなかったが、貪欲でいいだろうという直感で突き進んだ。

https://kenkoooo.com/atcoder/#/contest/show/be79177d-f3e6-41f4-8f07-93f8aa03b4e6

感想戦後、学食に行って夕食を摂った。帰宅後セミナー準備に向き合おうとするも、強烈な眠気に襲われて机に突っ伏し、2時間ほど寝ていた。まだまだ眠り続けそうな勢いだったが惰性でYouTubeやTLを眺めていたら目がさえてきた。

午後11時からようやくセミナー準備を始めた。今日は2010年の論文について読んで、整理。改めて自分の主定理が包含されていることも確認した。準備を終えたらシャワーを浴びて午前5時半就寝。

05/09(木)

午前9時起床。

富山県TopCoderのイベントが行われるらしい。今日。運営側の人が富山に住んでいるとやらで、そこでオンサイトイベントを開催したいという話は半年ほど前に公式Discordで出ていたのだが、その後今日まで一切のアナウンスがなかった。まあこの内容なら事前に知っていてもわざわざ行きはしなかったのでOK。

朝は曇りだが昼からは快晴の予定。パンを食べて原付で山に登った。

午前10時からセミナー。先々週の先生二人のうち一人は午前の部から、もう一人も午後の部から参加してくださった。内容は見つかった論文2本についてで、先々週からだと連続性がないのにありがたい話。自分の結果と関連する部分を話した。

学内の別の先生が二人いらっしゃってかなり緊張した。

週記(2024/04/22-2024/04/28) - kotatsugameの日記

午後1時前後の1時間食事休憩を挟み、午後4時までやっていた。解散直前に指導教員が学生の質問対応に行ったため、先生二人を見送った後は後輩と二人雑談していた。午後6時頃戻ってきたので今度こそ解散。

ホスフィンと連絡を取って学食で落ち合い、食事した後ホスフィンの研究室にお邪魔して学振の書類作成に取り掛かった。ホスフィンが先月書いた申請書にコメントをくれたので、それに沿って文面を考えていたが、調べものをしてばかりでまともに進まなかった。

日付が変わってから解散し、コンビニに寄りつつ午前1時前帰宅。だらけてかなり長い時間TLを眺め続けていた。シャワーを浴びて少し日記を書き午前5時半就寝。

05/10(金)

午前11時半に目を覚ましたら先生からメールが来ていた。2010年の論文の著者がさらに関係の深そうな論文を書いていたという話で冷や汗を書きながら読んだが、自分の研究とは方向性が違ったためセーフだった。

布団でしばらくゴロゴロした後、午後2時くらいに大学生協へ向かった。ラノベを買って食事し帰宅。その後午後5時まで論文原稿に手を加えていた。昨年度来た留学生に英語を校正してもらえたので、それを今反映し、今度は今年度来る留学生に送った。

昨日はホスフィンの研究室にお邪魔したため、今日は自室にホスフィンを読んで学振合宿を行う。このためにまず部屋をサッと掃除した。ホスフィンは午後7時頃到着。基本的には二人別々にPCに向かっていたが、途中1時間くらい研究計画について相談に乗ってもらった。

詳細は述べないが、信じられないくらい有意義な議論だった。研究対象が多少被っているからという理由だけでは説明がつかない。何か研究テーマを見出す汎用的なテクニックを実践しているような感覚を得た。修士のころからそういうものがあると聞いてはいたものの、それはもっと具体的なシチュエーションのもので、今みたいに「博士課程における研究」というロングスパンの話を考える際にも適用できるとは思っていなかった。

午後11時半からはCF #944 div.4に出た。部屋にホスフィンがいるので録画はなし。

Dashboard - Codeforces Round 944 (Div. 4) - Codeforces

Aはよい。Bはソートしたりそれをリバースしたりしてみた。Cは3月のパ件合宿1日目で見た。Dは/0*1*/に対してその左右にある01の連結成分を数えたが、冷静になると連結成分数から/01/がある場合1引くだけでよい。Eは二分探索で区間を求めて算数。Fは、整数の平方根の計算は怖いので避け、x=0,\dots,rに対しy区間をずらしながら求めた。

Gは4で割った商で分類するとその間は自由に交換可能だからソートするのが良い。Hは(x\land y)\lor(y\land z)\lor(z\land x)=(x\lor y)\land(y\lor z)\land(z\lor x)なので2-SATになる。この等式はわざわざ分配法則で示したが、そもそも意味を考えて右辺を見出したのだからそのまま突き進んでもよかった。

30分弱で全完し2位。

午前1時過ぎに連れ立って外出し、飲み屋街近辺の中華料理屋で食事した。華金ということでこの時間でもまだ人通りは多い。店については、料理の味は普通だが後ろにうるさい団体客がいたのでその分マイナスの印象を受けた。

部屋に戻り、帰宅するホスフィンを見送った後さらに書類作成を続けた。午前10時頃に切り上げて先生に送ったら、内容の添削ではなく自分の研究態度に対するダメ出しが返ってきた。言っていることは正論だがかなり強い言葉だったので最悪の気分になった。

寝て起きたら気が持ち直していることを祈り、午前10時半就寝。

05/11(土)

午後1時半起床。自分が寝たあとさらに一通メールが届いており、その文面はこれまでに増して強烈な言葉遣いだった。気分はどん底のまま、午後2時からUniversal Cupのチームで5hのバチャ。今日は月曜日に続いて300iq Contest 2を走った。

Dashboard - 2019 Summer Petrozavodsk Camp, Day 2: 300iq Contest 2 (XX Open Cup, Grand Prix of Kazan) - Codeforces

書く

ありえないくらい眠いが頑張って起きていた。午後9時からABC353に参加。

AtCoder Beginner Contest 353 - AtCoder

Aはよい。Bは頑張って問題文を読む。CはA_i+A_j\ge 10^8となる組を数える問題。DはA_jの寄与はすぐ求まり、A_iの寄与は下の桁数を全探索して計算する。Eは文字列をソートして隣接文字列のLCPを計算しておくと、二つの文字列のLCPがその間のLCPの最小値になる。つまり求めるものはすべての区間に対する最小値の総和であり、スタックを使う典型。

Fは見た目が面倒すぎてしばらく唸っていたが、最終的には綺麗に整理できた。答えの初期値を|S_x-T_x|+|S_y-T_y|として小タイルしか踏まない場合をケアした後、最初に踏む大タイルと最後に踏む大タイルを固定して考える。大タイル間の移動は、コスト2で斜めに飛び移っていくのが良い。ただしK=2のケースのみコスト3で二つ先の大タイルに行ける。これに気づけたのは、手で試した例が良かったのだろう。

Gは実家。\mathrm{dp}_i\pm C\times iをセグ木に乗せる。

29分でノーペナ全完、ペナ差で優勝した。コードゴルフはAをNibblesで書いたのみ。見つからなかったときに-1を出力するのが微妙に面倒だった。後から見たらfoldrでリストの先頭要素を取得するテクに初期値-1を渡すことで実現されておりびっくり。初期値を渡したらそれが先頭要素の代わりに出てくるだろうと思い込んでいたが、コードゴルフ用に調整された言語がそんな融通の利かない仕様である訳がなかった。

www.youtube.com

シャワーを浴び、日記を書いて午前4時半就寝。

05/12(日)

昼前に2時間ほど起きてハーメルンを読んでいたらしい。次に起きたのは午後8時。これも目覚ましによるものであり、起き抜けはまだ寝足りない感じがしていた。最近睡眠負債がたまっていたので、むべなるかな。

しばらくTLを眺めて眠気を振り払い、午後9時からARC177。

AtCoder Regular Contest 177 - AtCoder

Aは貪欲に使うのが良い。貪欲でない方法で支払うならその一部を額面が高い硬貨で置き換えることが可能である、ということから言える。Bは右の豆電球から順にi回Aを押し、i-1回Bを押すことで1にできる。Cはよく考えると、条件1のために青を紫にするのと条件2のために赤を紫にするのが完全に独立であるから、それぞれで最短距離を求めればよい。01BFSでO(N^2)となる。

Dは連鎖的に倒れた電柱の区間に分割するなど考えていたが、この方針はよくない。幅H以内の連結成分に分割して考えるのが正解。各連結成分は最終的に、ある電柱を境に左右に割れるように倒れる。そしてその境それぞれに対して確率を計算することも可能なので、あとはこれを成分ごとに整理し、適切に掛け合わせればよい。1点加算と全体積が必要で、ゼロ除算が面倒だったためセグ木を使った。

Eは配点を全探索して、得点が同じになるグループとグループ間の順序を列挙した。配点の最大値を30点までとしたところで4672通り見つかり、70点まで上げても増えなかったので、これで全部だろう。あとは列挙したグループ分けを全探索する。同じグループ内ではRが小さいほうに高い順位を割り当てることで誤差を最小化できる。ところが間に合わない。

グループに対しては属する人間が決まっているため、誤差は割り当てる順位の最小値に対する2次式で書ける。これを利用するとグループごとに毎回ソートしていた時間を削減できたが、Tが大きいケースで20sec弱かかりどうしてもダメだった。倍速になれば通ると思うと惜しい気もして、小手先の高速化に粘着してしまった。

4完30位。BとCは解法に比べて制約が小さく、本当に合っているのか疑心暗鬼に陥っていた。Eはグループ分けの間に包含関係が存在するケースがあり、細分化された方は考慮しなくてよい。このことを利用すると解説の通り113通りまで絞れて、余裕で間に合った。

コードゴルフはBのみ。Nibbles。Ai回、Bi-1回replicateして繋げるのではなく、ABi回replicateしてソートしinitを取ることにすると短かった。

www.youtube.com

その後は昼まで申請書を書き進めていた。先生に呼び出されていたので、シャワーを浴びて午後1時過ぎに登校。徹夜したため日曜日と月曜日の境目がないが週記はここで切っておく。

週記(2024/04/29-2024/05/05)

04/29(月)

午後7時起床。今日は休日のためインターン先定例会が休みだった。先週の週記を書いて午後11時半に投稿し、直後からECR165に出た。

Dashboard - Educational Codeforces Round 165 (Rated for Div. 2) - Codeforces

Aはp_{p_i}=iなるiが存在すれば2、そうでなければ3が答え。Bは左の0から順にすべての1より左に持ってくるのが最適。1の個数をカウントしながら見ていくとコストがわかる。Cは区間を選びその左右どちらかの値で置き換える操作だと思うことができる。dp。

DはbでソートしてBobにとっての無料と有料の境界を全探索。境界の上は下位k個を優先度付きキューで持ち、下は\max(b-a,0)の総和を持った。Eはuniqueでない区間のうち右端が最も左にあるものを見つけ、その右端を置き換えることを繰り返す。区間を見つけるためには右端を固定した状況で各値がカバーできる左端を管理すればよく、区間ADD区間MINでカバーされていない点を探すテクで処理できる。

Fは手札に揃ったカードがあれば貪欲に出してよい。そうでないなら手札に全種類のカードが1枚ずつ揃っているから、それがどのタイミングで発生するかを考えてdpした。例えばa_iを引いて手札が一杯になったとする。a_{i+1},\dots,a_jのうち奇数回登場したタイプがuvの二つのみ、かつそのようなj区間(i,j)に存在しないとき、uvを捨てると次に手札が一杯になるのはa_jを引いたタイミングだとわかる。3乗だが定数倍が非常に軽いため全く問題なかった。

全完3位。Eのテクは最近やたら見る気がする。

www.youtube.com

ラノベ「バスタード・ソードマン」3巻を読了。信じられないくらい面白かった。ただの日常の積み重ねなのに相変わらずやたら面白いなと思いながら読み進めていたら、ラストでぶっ飛ばされた。これまで読者にすら隠されてきた主人公の本当の実力が一部明かされたのだ。シーンとしては危機が迫るなどの大きなイベントがあったわけではないが、これまで3巻分の積み重ねがあったこその魅せ方で、最高に強烈だった。

ゴミ出しをするつもりだったのに、とりあえずもう一冊と手を出したら途中で眠気に耐えられなくなり、そのまま寝た。午前9時。

04/30(火)

午後7時起床。夜中までラノベを読んでいた。

「やる気なし天才王子と氷の魔女の花嫁授業」を読了。能力の代償が重すぎるように見えて辛い。ネタバレになるが主人公の代償はやる気のなさに繋がっており、そのせいでヒロインへの気持ちが表れにくく、代わりにヒロインと関わる理由として契約・約束が何度も強調され、窮屈に感じた。

午後11時半からCF #942 div.1に出た。

Dashboard - Codeforces Round 942 (Div. 1) - Codeforces

Aは最終的なaに対するn\times\min(a)-n+1+\#\{a_i\gt\min(a)\}が答えなので、\min(a)を大きくするのがよい。最大いくつを達成できるか二分探索し、余ったものは最後の項を大きくするように割り振った。

B1とB2はあまり関係がない。B1はabの倍数になるから、あとは算数。bの全探索によりO(m)になる。B2はg:=\gcd(a,b)とするとg(a+b)/gの倍数になるため、a/g\le\sqrt nb/g\le\sqrt mの範囲を調べればよい。全探索でO(\sqrt{nm})

Cは先頭から順に決めていった。f^k(a)_ikに関する多項式で表示し、i乗和の公式をi\lt 20くらいまで求め、それを使って計算。多項式の扱いに慣れていなかったが一発で合って良かった。しかしそうやってべき乗和の公式によって計算した値は、寄与を考えるとBITを表す木のパスに沿った累積和k回だから2項係数で求まってしまうようだ。

Dは二分探索を考えると、先頭から順に、functional graph上で移動可能な範囲にあるできるだけ小さい値を取っていくのが良い。これだとHLDやセグ木が乱れ飛んで計算量に大量に\logがつくので見方を変える。目的の値をどんどんインクリメントしつつ、そこに到達可能かを判定することにすれば、ただ2点間の距離を求めるクエリになって、部分木判定などによりO(1)で実行できる。

E1が上限と下限付きランダムウォークになることには気づいたが、計算できずコンテスト終了。5完41位でレートは2807→2856(+49)となった。

www.youtube.com

E1をupsolveした。mが小さいときはO(nm)のdp、mが大きいときは鏡像法で解けるらしい。鏡像法はうまい具合に\dots,+1,-1,+1,-1,+1,\dotsを配置するタイプのもので、ゴールにたどり着ける始点がO(n/m)個しかないため計算量O(n^2/m)となる。

TCB 2024/03回2位の賞品、アマギフ7000円分が届いた。

ラノベ「依存したがる彼女は僕の部屋に入り浸る」2巻を読了。相変わらず面白かった。ハーメルンと突き合わせてみると、やっぱり今回も書き下ろしの章が複数あるらしい。ストーリーも時系列も、主人公の印象すら崩さずにうまくラブコメ色を強めたものだと感心する。また挿絵もよい。特に、1巻でもチラッと見えていたが、主人公が本当に納得感のある容姿をしていて素晴らしい。

届いていた外付けSSDに過去の動画をいくらか移した。2023年までのCFの動画を移動させたところ60GBほど空いたので、熱を持ってきたこともあり一旦終わり。外付けSSDは思ったよりコンパクトだったからなんだか信用できない気がしたのだが、小ささは技術の発展の現れであり、信用すべきでないのは6年以上使っているPCのほう。

過去の動画がPCストレージを圧迫しており、そろそろ何とかする必要がある。消すのもなんだか良くない気がしたので、外付けSSDを買ってそちらに溜め込むことにした。

週記(2024/04/22-2024/04/28) - kotatsugameの日記

修論英訳の作業をして午前11時半就寝。

05/01(水)

目覚ましで午後4時に起床。サークルバチャに参加するつもりだったが眠すぎて二度寝……しかけたその時、後輩からセミナー発表資料が送られてきた。読んでいたら目が冴えた。

午後4時40分からサークルバチャ。ARC088Cに取り組んだら、順列pの転倒数が\sum_i|i-p_i|で求まると思い込んでとんでもないことになってしまった。今日は大学の教室の予約がいっぱいで取れなかったらしく、Google Meetで感想戦をして終わり。

https://kenkoooo.com/atcoder/#/contest/show/b33dceb0-9699-47c4-bc41-63776efe9a31

E - Papple Sort

後輩のセミナー発表資料を読み切っていくつかコメントを送り、4月分の読書記録をツイート。買った冊数が少し控えめ、さらに後半頑張っていたので3月までよりはマシといった感じ。それでも増分が正なのは変わらず、今年に入ってからだけで積読が100冊超増えたらしい。

ラノベ「現実離れした美少女転校生が、親の決めた同居相手で困る」を読了。ヒロインが献身的すぎて読んでいるだけで申し訳なくなってくる。過去に主人公の言葉で救われたという話だが、そのエピソードと現在の主人公へ向ける愛情にバランスが取れていないと感じた。

午前2時くらいまで日記を書いた後修論英訳に取り組み、シャワーを浴びて午前7時就寝。

05/02(木)

05/01発売のラノベを10冊注文していたらしいので混んでいない時間を狙って受け取りに行く必要がある。ということで頑張って午前11時に起きて大学に向かった。無事受け取った後は学食で食事。この時間にすでに牛乳が売り切れていて愕然とした。購買にもなかったし、販売を停止してしまったのだろうか。

いったん帰宅して荷物を整理し、今度は山に登って午後1時から後輩のセミナー。予備知識として必要になった閉曲面の分類の話だったが、難しかった……。すべての補題を証明しきることはできず、いくつかの補題を認めた上での議論。また展開図の上でグラフを描くのにも慣れていないようで手こずっていた。あまりに苦しいので次回はまた別の論文を読むことになった。

論文の話をしたり、秋から新たに受け入れる留学生に何をしてもらうか相談したりして午後6時過ぎ解散。学食で後輩と夕食を摂った。APG4bを少しずつ進めてくれているそうで、取り組んでいるのを見守った後コードを少し手直しさせてもらった。アルゴリズム小話として素数判定をO(\sqrt N)で行う話をし、午後8時帰宅。

Webページをいくつか読んで時間を過ごし、シャワーを浴びて午後11時半からCF #943 div.3。

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

Aは\gcd(x,y)\le x-yなのでy=x-1とすれば最適。Bは部分列判定で失敗した位置を答える。Cはa_n=10^9から降順にa_{i-1}=a_i-x_iと決めていった。Dはn回以下移動した後そこに留まり続ける。始点n通りすべてに対してスコアを求めようとしてしまったが、P_BP_Sからだけで十分。それぞれO(n)かけてよい。

Eは(1,1),\dots,(1,N-2),(2,N),(N,N)。Fはk=2またはk=3で、累積XORを見て判定。Gはhard versionを直接解いた。LCPの長さfを決め打つと、suffix arrayを見ながら貪欲に分割していくことでf\le f_kなるkの最大値が求まる。これはN/f以下なので、貪欲に分割する部分を1回あたりO(\log n)でできればあとはそれを繰り返すだけでよい。

全完7位。

www.youtube.com

ゴミを出し、寝るまでラノベを読んでいた。2冊読了。

1冊目、「平民出身の帝国将官、無能な貴族上官を蹂躙して成り上がる」。規則と証拠をもとに相手を言い負かす行為、これに憧れたことがないと言えば嘘になる。ただ現実では無理だろう。規則の文面や相手の発言を一言一句覚えきるのも、日頃の行動から瑕疵をなくすのも不可能。というわけで、主人公がやって見せたのは読んでいて楽しかった。ただしその対象となった敵キャラが周りに多すぎて、足を引っ張られまくっているのが辛い。

2冊目、「戦地から帰ってきたタカシ君。普通に高校生活を送りたい」。面白かった。向かうところ敵なしの主人公たちがドタバタしていて楽しい。紙幅が足りなかったようで肝心の高校生活については次巻以降。ただ一点、作品の軽快さに比べ、徴兵されて生還した主人公に対する家族の反応が重すぎると思った。それは重いのが当然の反応とは言え、そこまでニヤニヤしながら読んでいたのが申し訳ないような気持ちになってしまった。

午前7時半寝落ち。

05/03(金)

午後7時起床。本を読んでいた。午前3時ごろ寝落ち。

05/04(土)

午前6時半起床。昨日に引き続き本を読み進め、午後1時ごろ「冬季限定ボンボンショコラ事件」を読了した。大満足!自分はいかなるネタバレも踏まないようにと早めに読んだので、そういう配慮をここでもしておこう。普段書いているような感想は下に隠しておいた。

感想(ネタバレ注意)今作はほとんどの部分が小鳩君による、小佐内さんと出会うきっかけとなった過去の事件についての回想だった。あらかじめ良い終わり方をしないとの前振りがあった上では読むのにも気合いが必要だったが、頻繁に現在のシーンが挟まれて一息つけたため、あまり負担にはならなかった。

過去の事件の終わり方は確かに最悪と呼べるものだった。しかしその直後から始まる現在の事件の解決編が強烈で、全体としての印象はそちらが目立つ。良い結末と言えるかは微妙なところかもしれないが、二人らしいものだったことは確か。またそれとは別にシリーズとしての締めもあって、そちらははっきりと良かった。

伏線はどれも明確に指摘できなかったが、知ってから振り返れば確かに違和感を覚えた箇所はあった。具体的に挙げるのはよしておく。ただどれも(どれもと言うほど数はない)、詳細な描写がなかったので勝手に解釈してしまったらしい。そういう伏線は明かされないと気づけないのに、明かされると悔しい思いをする。

小鳩君が最初に日坂くんを見舞った際、日坂くんの姉らしき人物とすれ違ったのには気づけた。わざわざ描くくらいだから何かあるのだろうと思って覚えておいて、後半で姉の特徴と一致することを知ったため興奮。しかし結局本文中で触れられることはなかった。そういう明かされないままの伏線が他にもあるのだと思う。

しばらく仮眠して午後3時半にまた起床。急いでシャワーを浴び、午後4時からUniversal CupのチームでCFの謎4.5hに参加した。

Dashboard - Helvetic Coding Contest 2024 online mirror (teams allowed, unrated) - Codeforces

書く

G問題はCodechef Lunchtimeからの剽窃だったらしい。

https://codeforces.com/blog/entry/129149?#comment-1146461

先生からメールが来ていた。修論でも引用した論文の著者が4月に新しく論文を出しており、やっていることが自分の修論と非常に似ているらしい。ヤバすぎる!来週木曜日のセミナーは先々週の続きではなくその論文を読むことにした。

これまでチンタラ準備してきた論文が紙くずになってしまったかもしれず動揺を隠せないが、とりあえず今はコンテストに向き合う。パックご飯を腹に詰め込んで午後9時からABC352。

AtCoder Beginner Contest 352 - AtCoder

Aは\min(X,Y)\lt Z\lt\max(X,Y)か判定。Bは問題文が読みにくいが部分列判定と同じことをすればよさそう。Cは\sum A+\max(B-A)。Dはaを全探索し、インデックスをsetで管理して最大・最小を求めた。Eは(A_{i,j},A_{i,j+1})という辺だけ取り出してクラスカル法。Fは連結成分を一つ取り出して残りをbitDPすることを繰り返した。O(N^3 2^N)

GはABC331Gと似ていると思い、S\subseteq{1,\dots,N}に対して取り出した靴下の多重集合がSになる確率を求め足し合わせた。ただ、n回以上操作する確率をn\ge 0で足し合わせるほうがよほど自然だし、結局計算はn=|S|でまとめて行うためそちらを経由することになる。

G - Collect Them All

29分弱で全完し6位。かなり調子良く解き進められたと思ったものの、周りはもっと速かった。コードゴルフはAをdc、CをNibblesで。Aは(Y-Z)(Z-X)が正か負かで判定したがNibblesに負け。入力をソートしてZの位置を検索するのはかなり上手い。

www.youtube.com

コンテストを終えてもまだ精神の安定は戻っていなかった。今更じたばたしてもしょうがないと開き直り、ラノベを開いた。

「最強魔法師の隠遁計画」18巻を読了。ようやくテンブラムが開幕したかと思ったら本の前半しか使わず早々に終了してしまった。あまりにあっけないし主人公もほぼ活躍せず残念……と思ったら見せ場は後半に待っていた。久しぶりの主人公の全力バトル。最高だった。あとがきによれば次巻は舞台が変わるらしい。なろうと照らし合わせると、もしかしたら第5部冒頭のルサールカ訪問のことを言っているのかも。待ちきれない!

第5部冒頭のアルスが第1魔法学院を視察する話はかなり好きなので、早く本で読めないかとかなり前から心待ちにしている。

週記(2022/12/26-2023/01/01) - kotatsugameの日記

朝になってようやく論文の確認を始めた。読んでいくと、幸い自分の結果とは異なる、どころかいくつかは自分の結果に含まれるようなものだったので一安心。自分もいい加減けりをつけてarXivにでも上げてしまわなければならない。

正午就寝。

05/05(日)

午後10時起床。

ラノベVTuberの幼なじみと声優の幼なじみが険悪すぎる」を読了。面白かった。思ったより険悪でびっくりしたが丸く収まってよかった。ヒロインたちの仕事を応援する主人公の立ち位置が、遠くはなく、近すぎもせず、ちょうど良く感じた。炎上を鎮火するくだりはちょっとうまくいきすぎかなと思った。

日付が変わったころに布団を脱出。食事して少しだけインターン関連の作業を行い、日記を書き始めた。午前7時ごろからは昨日読んでいた論文のセミナー準備に移り、シャワーを浴びて正午前に就寝。