06/24(月)
午後3時過ぎ起床。昨夜開催されたUniversal Cup Semifinalsの順位表凍結が解除されており、我々のチームは全体10位・Finals未進出チーム内6位だった。8位までは確実にFinalsへ行けるはずだから、これはもう確定と言っていいだろう。やった！！！ちなみに決勝がいつどこで行われるかについては、まだ一切のアナウンスがない。
The 2nd Universal Cup Semifinals - Standings - Contest - Universal Cup Judging System
午後3時半からインターン 先定例会に出席。進捗がないので、やろうとしていることを具体的に書いてお茶を濁した。勉強会は時系列データの圧縮アルゴリズム について。時系列データは例えば一定時間ごとに取得されたりしており、差分を取るとほぼ定数、かつ値もあまり大きくならない。それを活用すると高い圧縮率が実現できるようだ。bitに詰め込んだり、差分のさらに差分を取ったりしていた。
解散後は大学生協 でラノベ を受け取り、夕食。帰宅してからはずっと先週の週記を書いていた。普段はUCまで手が回っていないが、今回は時間に少し余裕があったし、Semifinalsという特別な大会なのでちゃんと書くことにした。日付が変わる直前に投稿。その後しばらく追記してUCについては完成させ、灘の有志コンだけ穴あきで残っている状態となった。
ラノベ 「冒険者 酒場の料理人」を読了。面白かった。迷宮産の素材を試行錯誤して調理していく過程は丁寧さとテンポの良さが両立していて小気味よい。また合間合間に描かれる街や酒場の様子は人情味があって、味わい深かった。異世界 での日常を描くという点で「バスタード・ソードマン」を思い浮かべたが、こちらは主人公が貧弱なため少しヒヤヒヤする場面がある。しばらくすると戦闘力がヒロインに外注されて一安心。
午前9時就寝。明日は午後1時からホスフィンと二人で集まり、進捗を産む会を開催する。
06/25(火)
午後1時起床。遅刻である。曇り空が怪しかったので地下鉄で登校し、さらに学食で食事していたら最終的には1時間遅れでの到着になってしまった。
夜までずっと集中講義の課題に取り組んでいた。5月末に受講したものだが案外記憶が残っていて助かった。課題は10問ある演習問題をできるだけ解いてレポートにせよというもの。講義に最後の最後までついていけたこともあってか、問題はこれまで受講した集中講義に比べると非常に簡単に感じた。ただ時間はかなりかかって、これだけで一日が終わってしまった。
ホスフィンに無職転生 第2期の22話を見せてもらった。なろうで読んだ時の記憶がはっきり残っているわけではないが、再会できそうでギリギリできなかったこのタイミングの悪さが非常に辛かったことを思い出した。そのまま23話の冒頭もチラ見。昨日TLに流れてきたイラストが記憶に焼き付いていたので、そのセリフを確認した。
明日は午後5時から集まることにして午後11時過ぎ帰宅。半からCF #955 div.2に出た。
Dashboard - Codeforces Round 955 (Div. 2, with prizes from NEAR!) - Codeforces
Aは逆転が起こらなければよい。Bは
Dは冠雪している・していないで高さに
Eは区間 内でpopcountが最も大きな数を考える。
Fは大変。ソートしなくてよいprefix/suffixを求める。列をreverseすることによりprefixだけ考えれば十分。列の要素がdistinctならば、あるべき位置に存在しない最小値を求め、それ未満の数がいくつあるか数えることによって達成される。ここで求める最小値は、列において直前の要素より小さい値の最小値として特徴付けられるから、これを管理した。distinctでない場合もインデックスとペアにして考えればよい。
VIDEO www.youtube.com
日記を書いて午前7時就寝。
06/26(水)
午後5時起床。また集合予定時刻に起きてしまった。天気が良かったので昨日とは違って原付を使えたが、代わりにガソリンスタンドに寄ったため相変わらず1時間遅れでの到着となった。数日前に夏至 を迎えてこの時間でも非常に明るく、まるで昼下がりのよう。
今日は先週書いて動かした実験コードが正しいか検証していた。本当は手計算と比較するつもりだったが、それが可能なサイズではあまり情報が得られない。とりあえず文献に載っていた例をいくつか試し、正しい結果が出ていることは確認した。また午後10時くらいからはセミ ナーで読んでいる論文の行間を、ホスフィンにも考えてもらって埋めた。
夜中のCFもないし終電も気にしなくていいしで日付が変わってからもしばらく話続け、午前1時半くらいに解散。コンビニに寄りつつ帰宅した。メールでABC355の賞品アマギフ15000円分が届いていた。
実験コードの話。デスクトップPCで動かしているとあっという間にメモリ使用量が増えていき、64GBあっても数時間で食い尽くされるため、進捗をファイルに書き出すようにして、起きては再開し帰宅しては再開しを繰り返す羽目になっていた。Python あるいはJupyterの書き方が悪くて不要な変数が生きているものと思っていたが、今日ノートPCで実行してみると全く問題なく動いてびっくりした。環境の違いらしい。
手始めにバージョンを調べると、デスクトップPCのPython が古いことが判明した。aptでは更新できず首を傾げたが、そもそもまだUbuntu 20.04にいるのが悪いようだ。ということでUbuntu 22.04へのアップグレードを開始。機械学習 用に入れたNVIDIA ドライバーの更新をしてからdo-release-upgradeを実行し、1時間ほど待っていたら何事もなく完了した。実はOSのバージョンアップをするのは初めてなので感動した。
同時にパッケージもバージョンアップされた結果、メモリをバカ食いするのは解消された。しかし、安心して実験を回していたら、今度はログ出力が100MB近く溜まってChrome が耐え切れなくなってしまった。これまでちょくちょく再起動していたので顕在化しなかったらしい。どうせ正しく動いているのでバッサリ全部取り除いて実行しなおした。
そんなことをしながらラノベ を読み進め、午前8時就寝。
06/27(木)
午後0時半起床。原付で登校し、パンを買って食べて午後1時から後輩のセミ ナー。
今日は結構詰まって大変そうだった。教科書で「簡単な」とか「明らかに」と言われている事実は、確かに感覚として明らかに見えるものも多い。しかし、では示してくださいと言われると途端によくわからなくなることは、まあなくはない。万全を期すなら準備段階で少し考えておきたいところではあった。あとは、そのような言葉はセミ ナー資料に書かないとか……。
午後3時からは後輩の院生室仲間を招き、自分の修論 や最近の研究について説明した。知識が非常に広い人で、知らない分野との関連性を指摘された自分はタジタジになりつつ曖昧な顔をして頷いていた。興味はあるらしく、進展があったらまた聞かせてほしいと言ってくれたのは非常にありがたいこと。普段のセミ ナーに人を巻き込むのは難しいからいい機会だった。
セミ ナーは午後5時に終了。その後後輩と今日のセミ ナーで詰まった箇所について議論し、学食で夕食を摂った後はいつものように立ち話をして別れた。午後8時過ぎ帰宅。
ラノベ 「最強守護者と叡智の魔導姫」を読了。表紙イラストを見て清楚なヒロインだと思っていたら冒頭から真逆の行動ばかりでびっくりした。明け透けに迫ってくるヒロインは苦手かもしれない。一方能力の強力さは好み。敵を倒す直前に遠隔で割り込まれ取り逃がしかけたところで、ヒロインが能力を使って隠れていた敵の名前を暴き、動揺させたのが特に良かった。安全圏にいる相手に一矢報いる展開は、直前までのフラストレーションが解消されて好きである。
午後11時半からはECR167に出た。
Dashboard - Educational Codeforces Round 167 (Rated for Div. 2) - Codeforces
Aは
Cは
Eは区間 はほとんど区間 が二つあるのか長さ2の区間 が一つあるのかわからない。よってこれは前者に固定することとした。最初と最後の区間 も合わせ、FPS 関連を拾ってきて通した。
Fは制約を、行と列のどちらを後から塗るかという制約に書き換え、そこから作った有向グラフの強連結成分ごとに操作していくことになる。つまりオフラインで辺の追加と強連結成分のサイズの取得ができればよい。ググって記事を見つけたはいいが読解に失敗し、実装できなかった。
My own algorithm — offline incremental strongly connected components in O(m*log(m)) - Codeforces
5完15位。Fはupsolveしておいた。分割していく時系列と考慮すべき辺が別物であるということに気づいておらず、持っている辺の前半だけ使ってSCCを計算してみるなど寝ぼけたことをしていた。SCCを計算するためには最初のほうからほとんどすべての辺を管理しておく必要がありそうだが、頂点の適切な圧縮によってdisjointに分けられ再帰 していく様は見事。
VIDEO www.youtube.com
動画をアップロードしたのち、公開作業をする前に布団に倒れこんで寝落ちした。午前3時半くらい。
06/28(金)
午後1時に目を覚ました。今日は床屋とゲーセンに行きたいが、とりあえず寝そべったままラノベ を開いた。
「魔法警察ファンシー☆マリリン」を読了。ヒロインが魔法でフーダニットだけ行い、主人公が推理でハウダニット を補足するミステリ。それをかなりラノベ に近づけたようなものだと思った。一つ一つの事件が非常にスピーディに解決していく。容疑者や証拠はほとんど最初から提示されており、推理シーンが始まれば犯人はすぐ取り乱して馬脚を露す。さらにホワイダニット についてはほぼ自供頼りだった。とまあミステリ部分についていろいろ言ったが、とにかくテンポが良かったので、ラノベ として面白かったと思う。
一瞬布団から出て昨日のECRの動画を公開した後、再度布団に戻って別のラノベ を読み続けていた。午後5時くらいになってようやく行動する気になり、シャワーを浴びて大学生協 へ。床屋の前に購買でラノベ を買ったところ、顔なじみの店員さんに学年を聞かれた。そういえばここで本を大量に買うようになったのは2020年だから、もう4年経ったのか。
床屋では散髪後に「ワックスは付けないんですか？」「ワックス付けるといいですよ！」と猛プッシュされて困惑した。実は前回もほとんど同じことを言われている。「急に結婚式に呼ばれたらどうするんですか！」みたいな話をされたが、そのようなイベントが自分の身に起こるとは考えたこともなく、愛想笑いしかできなかった。
学食で食事して帰宅し、再度シャワーを浴びた。食事中に自分の院試体験記を読んだ外部受験生から連絡が来ていたので、自分が当時作成した過去問の解答を整理して送った。院試ゼミのメンバーで分担して解いたため、自分の解答だけではカバー率が非常に低い。本当に参考になるのか不安である。
kotatsugame.hatenablog.com
今日買ってきたラノベ をチェックしたら、予約したものと違うことに気づいた。生協への入荷メールまでは正しいため、おそらく他の人が注文した本と入れ替わってしまったのだろう。会計の際、電子マネー にチャージすることに気を取られて、商品の確認をおざなりにしてしまった。幸い明日も購買は開いているので、行って確認してみたいと思う。
もう夜も遅く、残念ながらゲーセンに行くような時間ではなくなってしまった。yukicoderに参加することとする。サイトを開いたら先週のコンテストのE問題がチャレンジで落ちていた。指数部の
yukicoder contest 435 - yukicoder
Aは埋め込み。お誕生日コンテストと聞いていたので、この問題を見て「そういう」ことだと思ったのだが、以降は普通の問題が続いてびっくりした。Bは操作Bでできるようになることがちょうど二つのマトリョーシカ を組み合わせることだけなので、最初に操作Aをできるだけやっておきたい。
Cはサンプル出力でお絵描きをし、
DはNyaanさんのライブラリから拝借した高速素因数分解 を貼った後、素因数分解 するよりオーダーが落ちてライブラリなしでも解けるらしい。
高速素因数分解(Miller Rabin/Pollard’s Rho) | Nyaan’s Library
Eは勘。ケーキを切る側は弱そうというところから考察を開始した。このことから、お互いまず
Fは案外簡単。部分木のGrundy 数をすべて求めたい。ある頂点Grundy 数は、操作したパスから1歩外に出た頂点たちのGrundy 数のXORだから、パスを
Gには手も足も出ず。ただしABCEでFA、さらにFが2ACしか出なかったこともあって完数も点数も断トツの優勝となった。
「双子探偵ムツキの先廻り」を読了。これもミステリラノベ 。双子の兄が常時異様なまでの警戒心で監視カメラを設置したり録音を行ったりしており、この「先廻り」によって得られた証拠で事件を立ちどころに解決するという話。ホワイダニット だけは担当できないので、双子の妹が代わりに暴く。証拠を出す前に丁寧に推理を行うものの、最終的にはポンポン出てくる証拠で押しつぶすような解決。ミステリとしては身も蓋もないが、爽快だった。
午前2時に寝落ち。
06/29(土)
午前4時に目を覚まし、ラノベ を開いた。
「地味なおじさん、実は英雄でした。」を読了。ダンジョン配信モノ。面白かった。主人公がネットに疎く、また配信も姪が勝手にやっているだけなので、コメントやネットの反応の描写が薄め。この距離感が読みやすかった。そもそも主人公はダンジョン攻略自体に興味がないらしく、自身の強さや能力を把握していないようだ。他の冒険者 より圧倒的に強いことだけはわかっているので、具体的な差がどれくらいで、今後どのように明らかになるのかが楽しみ。
しばらく日記を書き、午前9時から4時間ほど寝た。無事起床し購買に昨日間違って買ったラノベ を持って行ったところ、書籍担当の店員がいないため来週月曜日に確認するということになったので、店に預けてきた。ちなみに自分が注文したラノベ は棚に陳列されていた。およそ2年ぶりで2回目。まあ積んでいるシリーズの2巻なので、前回とは異なりほとんど気にならなかった。正しいほうも確認の必要があるため今日は買えなかった。
なんと店の棚に並べられていた。
週記（2022/10/03-2022/10/09） - kotatsugameの日記 思ったより時間が取られて学食で食事する暇がなくなった。慌てて帰宅し午後2時からUniversal Cup。今日は第3回目、Ukraineセット。
https://qoj.ac/contest/1714
書く
シャワーを浴びて食事し、午後9時からARC180に出た。これはオンサイトコンテストの予選でもある。
AtCoder Regular Contest 180 - AtCoder
Aは簡単。AAやBBはどうやっても消せないので、AとBが交互に現れる区間 に区切ることができる。これらは長さを2ずつ減らせるだけなので答えが簡単に求まる。あとは掛け合わせれば元の問題も解けた。
Bで大変な目にあった。サンプル4の出力を手で試したところ、どうやら
単に優先度付きキューを使う場合
Cは順当に解けた。操作後の
これで、現在選んだ要素の和を持つdpが可能になっている。コンテスト中はなぜか最初から
Dも見覚えのある考察。区間 ADD区間 MINの遅延セグ木を管理することで取得できる。
何とか4完を確保し34位。無事決勝に進出できた。Bの想定解はわかってしまえばあっけなく、なぜ逆順列を考えなかったのか不思議でならない。600点だから観察から力押しで解けるだろうと考え、あんまり腰を据えて考察していなかった気がする。ランダムケースも非常に小さい範囲でしか試せていなかったので、もし勘を外していたら悪夢だったろう。
コードゴルフ としてAをNibblesで解いておいた。一つ置きにAとBを反転しランレングス圧縮する方法。反転の代わりに列
VIDEO www.youtube.com
「カミガカリ 不自然言語処理 殺人事件」を読了。「AIのべりすと文学賞 」の受賞作。神託された犯罪事件の真相をもとに、人が詳しい経緯を調べたり証拠を集めたりするミステリで、神様の役割はAIのべりすとが担う。試みとして興味深いしAIの活用方法も非常に好みだった。生成された文章を一言一句正しいものとする事件が組み立ててあり、一見不自然な箇所にも非常に合理的な背景が用意されている。文章の細部まで大切に扱われていて良かった。
小説としても面白かった。中盤くらいまではとにかく陰鬱で、登場するキャラがみんな不気味で好きになれず、主人公に味方がいないように思えて窮屈だったが、そのあたりの事情も最終的には回収される。また後半で扱われた事件は設定の根幹にも絡んできて、ストーリーの構築に唸らされた。単なるアイディアだけの話ではないということ。
相変わらずSageMathで実験を回している。要素が
しばらくラノベ を読んで午前9時前に寝た。
06/30(日)
午後6時起床。「英雄ブランの人生計画」1巻と2巻を読了した。これで6月は1日1冊ペースで本を読めたことになる。
最強の冒険者 の一角だった主人公が引退し、正体を隠して別名義で再度冒険者 をする話。正体の隠し方が徹底されていて、雑用依頼ばかり受けているから戦闘能力は一切知られておらず、他の冒険者 に絡まれて返り討ちにするといったテンプレシーンすら存在しない。一方で、周囲に雑用依頼を布教している部分はスローライフ 的で良いなと思った。
急いで食事して午後9時からABC360。
AtCoder Beginner Contest 360 - AtCoder
Aはsed 。Bは言われたとおりに実装。Cは各箱に対し最も重い荷物を管理して計算する。Dは左向きの蟻それぞれについて幅区間 に入っている右向きの蟻を数える。
Fは区間 に対して区間 ADD区間 MAX・argmax取得の遅延セグ木で逐一
Gは通常のLISに加え操作を行ったかどうかを持ってdpする。操作する際はLISにおける直後の要素とまとめて遷移することにし、dpの更新タイミングを少し遅らせることで一つ前のdp配列の値を計算に使えるようにした。最初はLISの長さに対して末尾の値の最小値を持つdpを書いたが、これはdp配列の値が単調増加になることを使うから、操作を行った後のdpでも成り立つかわからない。
そこでmapを使い、末尾の値に対してLISの長さを持つことにした。最適でない値は逐一探して消していくことにする。このあたりの実装に手こずりつつ何とか書き上げるも、最初の提出はWA。よく見たら操作しないケースだったり操作する値がLISの末尾に来るケースだったりを考えていなかったので修正し、通した。実はまだ嘘解法で、dpの初期値的に
全完7位。ただしFもGもテストケースが弱いだけだった。コードゴルフ としては、sed で書いたAがそのまま最短になっている。
VIDEO www.youtube.com
午後11時半からはCF combined、EPIC Institute of Technology Round Summer 2024。
Dashboard - EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2) - Codeforces
書く
VIDEO www.youtube.com
食事・シャワーを済ませ日記を書いて午前10時くらいに布団に入ったら、大学生協 から電話がかかってきた。ラノベ の件。結局、自分が間違えて買ったラノベ は他の誰かが注文したわけではなかったらしい。返金してくれるとのことだったが、誰のものでもないならとせっかくだからそのまま買い取ることにした。
しばらくハーメルン を漁って午前11時半就寝。
