Weekly Report 2025/01/05〜2025/01/11

01/05(日)

微妙な時間に起きたため月曜日学校に行くまでを日曜日とする．

指導教員から冬休み中に卒論の序論と準備を書くように言われており，明日から学校が始まるわけだがもちろんやっていない．やる気が全く起きないので典型90の灰diff埋めをして，埋め終わった．あとは，Xで「数字を使わずに2025を出力するコードを書け」という問題を見つけたので取り組み，時間を溶かした．

逃げ道も無くなったところで卒論に取り掛かる．LLMの力を借りて5時間くらいで準備まで書いた．同種写像暗号については正直完璧に理解してるわけではないので，準備の章はかなり指摘が飛んでくると思う．

やることが終わって学校に行くまで典型90の茶diff埋めをする．自分の苦手分野として計算誤差や小数の絡む問題が挙げられるが，最近のabcの傾向を見るに精進の必要はあまりないのではないかと思う．遭遇したら解く程度にして，自分から解きに行くことはしないことにした．

定期券を買う必要があるため早めに家を出て駅に向かう．濃霧の影響で電車が遅延していたのでこの時間を使ってDBゼミの復習をしておいた．B木の章は二分探索木を知っていれば読みやすく，すいすい読み進めたのだが，こういう読み方をすると内容を忘れがちである．

01/06(月)

1時間目は情報理論の授業を受け，2時間目の授業でDatabase Internalsのゼミをやった．資料作りをサボっているため早くやらなければならない．

1時間目が始まる前に春から一緒の大学に進学する友人と話してかなり不安が払拭された．春から暮らしていくためにバイトを探さなければいけなければならず，できれば技術系の仕事がしたいという希望があるが，叶うかはわからない．

ゼミのあと図書館に行き組合せ論の本を春休み中に読む決意をした．今借りている本の延長申請をして研究室に戻った．

部活で買った本が届いたので取りに行き裁断まで済ませた． jax/flaxの本とゼロつくの3を買った．関数型っぽいディープラーニングのフレームワークを自作してみたい気持ちがある．

放課後はビジコンの開発のためアプリケーションの設計をした．どういう流れで処理を行うかすべて決めてしまい後輩に仕事を割り振ったのだが，みんな忙しそうであったためスムーズに進むかはわからない．DBにあるデータの概要とプロンプトをLLMに投げてPythonのコードを生成させ，適当なグラフを描画したいのだが，フロントとバックのやり取りのベストなやり方がわからない．

前のabcのc問題が界隈を騒がせていたこともあり，帰りの電車の中では桁dpの解説を読んでいた．理解した気になったが多分書けないので類題を解きまくる時間を作りたい．

空き時間はAtcoderの典型90茶diff埋めをやっており，22時位にやっと全て埋め終わった．24時間で全部埋めたいと思ってたので目標が達成できて良かった．

01/07(火)

眠すぎて2時間目の哲学の授業に遅れたが，先生の慈悲により出席にしてもらった．授業中は典型90の緑埋めをしていた．難易度的には茶diffと変わらない気がしており，アルゴリズムのお勉強感が強く感じられる．変なところで詰まってしまい時間を浪費したせいで2問しか解けなかった．詰まったものを書いておく．

026 - Independent Set on a Tree（★4）

木の重心から行き掛け順に出力すれば良いと思って取り組んでいたがバグが取れない．おそらくこの方法でも解けるが実装が重くなりそうな気がしたため再考察をしたところ，2部グラフを考える方法が思い浮かんだ．木は二部グラフなのでまず2色で塗って，白と黒のうち多い方を $\frac{N}{2}$ 出力すれば良い．実はこんなことをしなくても，適当な点からdfsをして到達した順番の偶奇を見るだけで解くことができる．

028 - Cluttered Paper（★4）

配列をint G[1010][1010]で定義した上でループの終了条件をi<=1010としてしまいREになった．自分のローカル環境だと正しく動作してしまうせいでデバッグに時間がかかった．コンパイルオプションを色々いじっても改善されず，そこまで致命的な問題というわけでもないので解決を保留にした．

授業の後は髪を切りに行った．歩いて行ったため体力が底をつき，家に帰ったら寝てしまった．一度布団に入ったが最後，起きたあともそのまま布団の上でダラダラしていたが，Youtubeで最大フロー問題のアルゴリズム(Ford-Fulkersonのアルゴリズム)を勉強した．ACLに実装されているようなのでライブラリ化はしないが，一度はソラで書いてみたいと思う．

01/08(水)

朝はしっかり起きて2時間目の英語の授業に出席した．授業中は区間dp，ビットdp，Ford-Fulkersonの実装をした．授業後はすぐに帰宅し，妹の算数を見ていた．夜は家族と外食をした．

書くことがない．27時入眠

01/09(木)

可燃ゴミを出すように頼まれていたので一度6時に起きたが，授業はなかったので夜まで寝ていた．家族が外出していたので夕食は出前を頼むことにした．

見たいと思ってウォッチリストに入れていたアニメや映画を見きってしまったため見るものがなくなった．代わりに吉田製作所を見ている．

競プロはAtcoderのC埋めをやっていたが緑diffにぶち当たって時間を溶かし，3問程度しか解くことができなかった．400点のDよりも350点のCが解けない．夜まで寝ていたためうっすら眠気がしており，全く集中できないため朝までスマホをいじり，30時入眠．

01/10(金)

13時半起床．父のパソコン作業を手伝った．作業後に牛丼を食べたら眠くなってしまったため入眠．18時に起床して入浴． 19時から後輩とミーティングをした．ビジコンが終わったらプロジェクトから離れてしまうらしく，少し悲しい気持ちになった．夕食はラーメン屋でラーメンを食べ，回転寿司で期間限定のデザートを食べた．最近外食が多い．

そろそろ卒業研究を終わらせなければならないため重い腰を上げて机に向かった．とりあえずSIDHアルゴリズムのフローを書こうと思ったが全く進めることができなかった．エルガマル暗号の正当性証明を読んでSIDHも軽く証明できるだろうと思っていたが，自分で記述しなければいけないものが多すぎて終わりそうにない．本気でテーマ変更を考え，指導教員にお願いする文章を考えた．29時入眠．

01/11(土)

18時起床．

ABC388はHHKBの抽選に応募したかったためUnratedで参加．少しでも詰まったら撤退しようと考えていたが，得意セットで人生初の5完をきめた．

D問題は遅延セグ木で殴った．宇宙人 $i$ は $i+1$ から $N$ までの $N-i$ 人に配るため，自分が持ってる分とのminを区間addした．

Eは大きい方からみて先頭の要素と末尾の要素がペアを組めるなら組むという貪欲を尺取りで実装したが嘘だった．落ちるケースとしては，

6
1 1 1 2 2 4

のようなものがあり，上記のアルゴリズムだと $(4,2), (2,1)$ の2ペアが答えとなってしまうが， $(4,1), (2,1), (2,1)$ と3ペア組むことができる．

最終的には二分探索で通した．

$f(x):=x$ 個のペアを作ることはできるか？

とすると $f$ は単調となる．判定について述べる．まず， $x$ 個それぞれのペアの下側は餅を大きい順に $x$ 個取ってきたものとして良い．なぜならば，下側に選んだ餅 $i$ よりも小さい餅を下側にしたペアが最適となるならば，それを $i$ と交換しても答えは悪化しないからである．

よって，大きい方から $x$ 個取ってきたものを下側の餅として固定し，それ以外の餅を大きい順に見て固定した餅とペアを組んでいけば， $x$ 個のペアが組めるか判定することができる．

初の5完で浮かれていたがなんとか切り替えて卒研に着手．同種写像暗号について取り組むのは困難であると判断し，比較的簡単なLWE暗号について調べ始めた．

とりあえず鍵共有のアルゴリズムと証明は理解したが，誤差を落とす部分の証明がわからない．一旦その部分だけオラクルとしてLeanで証明を書こうと思ったが，体力的に限界がきてしまい30時入眠．明日は成人式．