10/31(月)

布団に転がってずっとハーメルンを読んでいた。寝るのを諦めたのは午後2時を回ったころ。そう決めたなら、夜になって力尽きてしまう前に週記を書き上げて投稿しなければならない。先を読みたい気持ちを抑えて何とか布団から脱出した。

シャワーを浴び、しばらくコードゴルフした後、一瞬大学生協に行って菓子パンとラノベを買ってきた。帰宅してからしばらく日記を書き、午後4時半からインターン先定例会へ。

木曜日にコードを書いたのが先週の進捗。そして金曜日の1on1に寝坊した。これについては改めて謝罪した。今週は改めて行われる1on1で判断を仰ぐのと書いたコードの修正を行う。修正するべき問題は、出力物だけ見れば軽微なものに見えるがまだ原因もわかっていない。もしかしたら根深いものかもしれず、どのくらい時間がかかるかとか詳しいことは見通しが立たない。

勉強会はつい最近TLで話題になっていた、ディープラーニングで行列積を高速化する話についてだった。非常に興味深かったため、眠気で頭が回っておらず聞き逃したところがいくらかあるのが残念。Strassenのアルゴリズムのようにして積を計算する回数を減らすことで高速化されており、それをディープラーニングする準備として、行列積の要素を積の和に分解して表す方法の数学的な定式化と、そこから一人ゲームに帰着するアイディアが紹介された。このゲームを学習すればよいのだ。

評価において実機上で動作する時間も用いることで、そのアーキテクチャに最適化されたアルゴリズムが得られるらしい。明示的に何かしなくても勝手にキャッシュ効率を考えたりしてくれるのと同じ効果があるものと考えられて、この汎用性には本当に驚かされた。自分が07/20の勉強会で取り上げたBLASの行列積では、アーキテクチャごとの最適化はさながら職人芸で専門性が非常に高そうだった。

内容はNumPy、というかそれが呼び出しているBLASという線形代数ライブラリにおける行列積の実装について。
週記（2022/07/18-2022/07/24） - kotatsugameの日記

いよいよもって眠気がまずい。落ちる瞼に抗って何とか週記としての体裁だけ整え、午後7時半ごろに投稿した。また今度加筆修正の必要があるが、今はとにかく眠い。布団に倒れこんで午後8時くらいに就寝。就寝報告のツイートをする間すらもなかった。

11/01(火)

午前2時起床。

それからずっとハーメルンを読み続けていた。午前8時半に1作読了。「ようこそ孔明のいる教室へ」。

syosetu.org

非常に面白かった。Aクラススタート、しかも原作キャラを差し置いてクラスのリーダーポジションになるという展開。それだけに主人公の能力は非常に高く、爽快な無双を楽しめた。特に3章はクライマックスの描写も含め非常にかっこいい。また派閥の部下を一人しか持たず、その人からズブズブに依存されているというのはどことなく退廃的で興奮する。

1時間ほどコードゴルフしてからセミナーに向け出発。教室で同級生と合流したものの、時間になっても先生が来ない。メールを送ろうとしているうちに同級生が、我々がセミナーの日時を間違えていることに気づいた。11/02に行われると認識していたのに、その日付を深く考えず二人してセミナーは毎週火曜日に行われると強固に信じ込んでしまっていたのだ。実際は明日である。

しょうがないので帰る。2限のために登校してきた友人を交えて少し話した後、山を下りた。生協に寄って食事し、ラノベを購入して帰宅。

10月分の読書記録をツイートした。先月は上旬をシャングリラ・フロンティアに費やして、その後もずっとハーメルンばかり読んでいたようだ。

10月の集計
買った：27冊
読んだ：8冊
積読：+19冊
積読（累積）：+119冊
— こたつがめ (@kotatsugame_t) 2022年11月1日

しばらくコードゴルフしてから午後1時くらいに布団に入った。ハーメルンを読み、午後2時半に寝落ち。

午後8時半起床。ひそかにゲーセンに行こうと思っていたが、当然のように失敗してしまった。また1時間ちょっとコードゴルフ。

TAも年末調整をしなければならないらしく、大学からメールが来ていた。読んでみるもほとんど意味が分からない。幸い期限までしばらくあるし、今日対応するのはすっぱり諦めることにして、布団に倒れこんで本を読んだ。ラノベを2冊読了。

1冊目、「現代ダンジョンライフの続きは異世界オープンワールドで！」。竜に寵愛を受けた主人公が何かする作品だと思って買ったが、1巻は寵愛を受けるまでの話だったので、今のところは特に好きとも嫌いとも言いにくい。とりあえず2巻を待ちたい。主人公のキャラはあまり好きではなく、ヒロインはそこそこ好き。展開については、バトルシーンが前半にしかなくあっさり終わってしまったこともあり、それほど盛り上がりはなかったと感じる。

2冊目、「無能と言われ続けた魔導師、実は世界最強なのに幽閉されていたので自覚なし」。著者に見覚えがあると思っていたが、著作リストを見て納得。「神話伝説の英雄の異世界譚」を書いた人だった。そちらは独特の格好良さ、良い意味での厨二臭さがある作品という印象だったので、長文タイトルのテンプレラノベとなかなか結び付かなかった。新作がこのようなパッケージになってしまったのは、まあ商業だから仕方ないのだろう。

中身は前作と変わらず良かった。ヒロインなのにやたら生傷を負わされるのも前作通りで、その分主人公がやってくるクライマックスでの解放感がある。主人公の世間知らず設定については、実力についての行き過ぎた謙遜がなかったのは読んでいて好印象だが、そもそも別に必要ないのではと思ってしまう。まともに展開に関わるのは大体お色気シーンで、これも商業だから仕方ないとはいえ格好良さを求めて読む身としてはノイズになっている。それはそれとしてイラストが好みのため興奮はする。

ネットで話題になっていた記事を読んだ。非常に良い。みくのしんさんは小説こそ読んだことがないものの読解力が非常に高いようで、描写に関する鋭い指摘にはちょくちょくハッとさせられた。ティッシュで時間を把握するのも上手い方法だなと思った。そうやってガヤを入れる様子も交えて読んでいくと、ただ「走れメロス」を読むより作中の雰囲気が一層感じられて、終盤は一緒になって泣いてしまった。この名作を改めて丁寧に読む機会が得られたのが嬉しい。

omocoro.jp

ハーメルンの更新を確認して午前7時就寝。

11/02(水)

午前9時15分起床。準備して山に登った。今日こそセミナーである。

今日は午前中だけで、同級生と二人で1時間ずつの予定。実際には少し伸びて1時間半ずつになった。自分の発表は前回分の残りなので、特に言うことなし。

同級生の発表を聞きながら自分の中でも証明の方針を考えるのだが、黒板で発表されるのがそれより遠回りしていると感じたら口出しせずにはいられなくなってしまう。それで実際に短くなればいいものの、実際に計算してみると大して変わらなかったり失敗したりしていてひどすぎた。途中で自覚したため、その後はどんな証明もとにかく最後まで聞くことを意識していた。

山を下りて学食で食事し、散髪も済ませた。ラノベを買って帰宅し午後3時から1on1に臨む。

先週木曜日にひとまず終わらせたコードの書き直しについて説明をした後、生じている問題、出力が以前のコードと少し違う原因を探り始めた。1行1行見ていくしかないのかな、面倒だなと思っていたら1on1のお相手にすぐ原因を見抜いていただいた。以前にも同様のことがあったが、やはり大本のコードを書かれただけあるなと感じるところである。原因は、同じだと思ってコピペした部分が実は微妙に異なっていたこと。

その周りで連鎖していくつか修正が必要になったものの、とにかく元のコードに合わせることを意識して書き直したら見事出力が一致する。しかしチェックの過程で、実はいくつか元のコードより適切な出力をしているのではないかという話になった。これまで気づいていなかったケースにたまたま対応できているらしい。なので、最終的にはそれを改善として取り入れたものが完成版となった。

ここからは思う存分リファクタリングや機能追加ができる。次に実装するものの指示を頂いて、3時間弱で終了。

疲れ果ててしばらくTLを眺めた後、日記を書き始めた。そこそこで切り上げて午後9時前に就寝。

11/03(木)

午前1時半起床。朝までかけて本を2冊読んだ。

1冊目、「ifの世界線」。SF短編アンソロジー。どの短編も面白かったが、最後のものが最も衝撃的で、他の短編の印象が少し薄れてしまうくらいだった。以下ネタバレ注意。

「うたう蜘蛛」はオチが良かった。終盤まで何が何だかわからないまま読み進めてきて、そこで何の話だったのかを理解させられる。

「パニック──一九六五年のSNS」はミステリ風味。特に短い短編なので真相もあっさり明かされるが、なかなかビターなものだった。SFという感じはあまりしない。実は本自体、この短編の著者である宮内悠介さんを目当てに買ったのだが、ちょっと期待外れという感じ。

「一一六二年のlovin' life」は設定が面白い。和歌に詠訳（＝英訳）を添えて発表するのが当たり前となった世界において、和歌の名手と詠訳の名手が出会う話。教科書で見知った和歌も英語になるとまた違った感触がある。三十一文字では徹底的に省かれていた描写が、英訳するにあたって言葉を補われることから発生するこの感触の違いについては、作中でも言及されており自分も同意するものである。

「大江戸石廓突破仕留」は時代小説の皮を被ったSF小説。冒頭の描写から異物の存在に気付くが、その時点ではまあSFだし、ちょっとした小道具だろうと飲み込んでしまう。しかしそれこそがこの作品の根幹なのであった。

「二〇〇〇一周目のジャンヌ」が最後の短編で、衝撃的だと言ったもの。タイトルの通り「周回」の話。非人道的すぎる設定からして笑い事ではないはずなのに、TAS動画を見ているようなワクワク感が自分の中にあったことを否定できない。20001周目にたどり着き、これまでの閉塞感が一気に取り払われた中でのジャンヌの行動によって強烈な読後感を得た。

またそういうインパクトだけでなく、でびでび・でびるさんのコメントを改めて読んで気づいた流れもある。つまり、ジャンヌの最後の行動はただ周回に倦んだからではなく、信心が最後の最後でループし元通りになったとも考えられるのだ。

【発売まであと5日】
『ifの世界線　改変歴史SFアンソロジー』

いかいのとびらがひらかれた……でびでび・でびるさま（ @debidebiru_sama ）より伴名練さん「二〇〇〇一周目のジャンヌ」へのコメントをいただきました。世にも恐ろしい推薦文をご覧ください。#ifの世界線 #10月14日発売予定 pic.twitter.com/jjWpqBUXDR
— 講談社タイガ (@kodansha_taiga) 2022年10月9日

2冊目、「灰原くんの強くて青春ニューゲーム」3巻。面白かった。2巻でそれとなく示唆されていたように、主人公グループの中で人間関係の矢印があちこちに向き、読んでいる側としてはやきもきさせられる。視点人物たる主人公が気付いているもの、あからさまに描写されてはいるが気付いていないもの、描写すら曖昧で本心がよくわからないもの。ただ、この巻のメインは1巻から出ているヒロインと主人公の関係についてだった。これまでは実は表面的な付き合いだったらしい。そこから急速に仲を深め、一気に主人公が好意に気付くステップまでたどり着いた。しかし次巻はまた別の騒動がありそうで、この巻みたいにストレートに進展することはなさそう。どう遠回りしていくのか楽しみ。

そこからハーメルンを読んで午前11時にまた就寝、午後3時前に起床。

午後3時からOpenCupの代理コンテスト。OpenCupと同じプラットフォームでのバチャという形式だったが、問題はQOJでも見られるようだ。そちらへのリンクを貼っておく。

2021-2022 ICPC North America Championship - Dashboard - Contest - QOJ.ac

これが今期初めてのOpenCupであり、チームが組み直されて初めてのコンテスト参加となる。新しいチームは他二人が自分より圧倒的に強いので何か貢献できるのかと不安になっていたが、終わってみると2問解いたのに加えてペアプログラミング的なことも少ししたため、何もできなかったわけではなかった。チームとしてはなんと13問すべてが解かれ、touristを擁するチームに続く2位となっている。順番はBMJDAKGCLFIHE。

自分が解いたAとGについて。Aは入力から感染タイミングとしてあり得る日付が確定するため、それを満たしながら伝播していくシミュレーションをすればよい。最初の感染者は一人ずつ試さなくても全員同時に行える。また感染タイミングが二日しかないので、自分が移した人にまた移されるケースを考えなくてよい。自分はこれに気付かず、bitsetで誰から移ってきたか管理していた。制約がやたら小さく、それでも問題ないくらい計算量的に余裕があった。

Gは水路をグラフだと思うと、木またはなもりグラフの集まりになる。実際は辺がループや根に向かう方向に向きづけられている。各観光スポットについて、それに隣接するマスがこの木の上にいくつか乗っているが、特にループに近いものだけマークすると、どのようなパスを辿ってもマークしたマスが1回しか出現しなくなる。これで重複が省けている。

自分よりループに近いマスがあるかの判定は、候補として高々 $4-1=3$ 個を全探索し、木において祖先かどうか見ればよい。自分はダブリングで求めた。グラフをちゃんと木として整理しないまま実装を進めたためバグがないか不安だったが、何とか一発で通った。

他はEFHを読んで考察していた。Eは数列の累積和を取ったものの期待値を求める問題で、期待値を求めた後累積和を取ればよいことに気づいておらずダメダメ。チームメイトが誤差に苦しんでいたので、制約が小さいことを利用し多倍長で計算することを進言してみたら通った。Fは手も足も出ず。

Hは場合分けゲーで、状態数が多すぎるため絶望。チームメイトが計算量の許す範囲でどれを全探索するか方針を示したので、それに乗っかって細かい部分のダブルチェックを行っていた。考察メモだけ確認してコードのほうはノータッチだったが、一発で通ったのには感動した。実装が上手すぎる。ボス問はこのEとHだった。

全完して解散かと思ったら、コンテストの振り返りが始まった。これは去年のチームではなかった行事。Aから順番に担当した人が問題概要と解法のポイントを述べていった。正解の道筋だけ見せられると自分でもできそうという気持ちになるが、実際は思いつけるかどうかのほかに本当に実装できるのかということも考えなければならない。

Gの自分がダブリングを使った部分についてほかの方法がないか聞き、オイラーツアーして区間の包含に帰着する方法を教えてもらった。冷静になるとそれはそう。自分の実装では根がどれかわかっていないので、計算量的にも許される以上、あの場で取る方針としてはやっぱりダブリングがよかったのかなと思う。

すべて終わって午後9時。食事し、TCO Finalsのルールを確認して、午後10時半からFinalistのミーティングに参加した。

Zoomに接続して話を聞いているだけ、そもそも英語をあまり聞き取れないので何もしていないとも言える。参加者は競技中PCの画面を監督者に共有しなければならないらしい。モニターが複数ある人は全部。自分はそれに加え別のPCのモニターも目の前に固定された状態となるが、これについてはそのPCをシャットダウンしておけばよいだろうと思っている。念のため当日に確認するつもりだ。

午前3時くらいまで日記を書いていた。途中、rating-historyがそろそろ使えなくなることを知ったので記録の意味でツイートしておいた。

というわけで https://t.co/roTjozWzPx は 11/8 くらいで死にます　使ってくれてた人々ありがとう
— beet (@beet_aizu) 2022年10月7日

Solved By kotatsugame
Topcoder: 150
Codeforces: 2085
AtCoder: 4127
AOJ: 1322
yukicoder: 1479
library-checker: 25
Sum: 9188
https://t.co/0nO54qH8aU
— こたつがめ (@kotatsugame_t) 2022年11月3日

布団に入ってハーメルンを開いたがすぐ寝落ちしてしまった。

11/04(金)

午前11時起床。

布団でハーメルンの「極めて傲慢たる悪役貴族の所業」を読了した。面白かった。転生先の体に引っ張られて傲慢な態度を取ってしまうという設定が好み。日本人的な礼儀正しい精神と拮抗した結果、ちょうどいい俺様具合になっていて、読んでいて好印象だった。やはり貴族なのだからある程度の尊大さはあってほしい。

syosetu.org

午後1時くらいに外出、ゲーセンに行く。まず腹ごしらえのため蕎麦屋に入った。天ぷらそば1杯で1700円。大盛りにすればよかったなと思いながら食べた。たまには良いものを食べようと思っての行動だが、正直な話普段食べている330円のかけそばとの違いが判らない。何なら麺の太さ・硬さ的には後者のほうが好みだったりする。海老天は巨大で良かった。

食事 pic.twitter.com/TQZuJgpJfD
— こたつがめ (@kotatsugame_t) 2022年11月4日

スーパーノバはチュウニズムが埋まっていたので、ちょっと歩いてGiGOに行った。今日も新曲をメインにちょうど30クレプレイ。14+が多めだった。低難易度から理論値が3譜面出たのと、新曲ではない14+のAJが一つ出た。

星の器～STAR OF ANDROMEDA　AJ pic.twitter.com/tLgYk4VAft
— こたつがめ (@kotatsugame_t) 2022年11月4日

途中のゴミ付きトリルが押せて感激。何回かプレイするとダメになりそうなくらいギリギリだったが、ダメになる前に出せた。真ん中にスライドを敷きながら両端でトリルする部分について、左手始動であることをちゃんと確認したのが功を奏した。ラストでスライド持ち替えをミスって一敗している。

一発で鳥出た　二度とやりたくねえ pic.twitter.com/kZJXblpQyB
— こたつがめ (@kotatsugame_t) 2022年11月4日

SON OF SUNのULT譜面。譜面動画を見た限りではSSSにも苦労しそうという印象だったが、実際にプレイしてみると終盤までSSSボーダーを超えていたので、ラストは何もかも忘れて全押し手首エアーで通した。代償として手首を少し痛めたため、二度とプレイしたくない譜面に。

今日の理論値 pic.twitter.com/lriWswP9p1
— こたつがめ (@kotatsugame_t) 2022年11月4日

前二つはやれば出る譜面。Mami Mami Zoneは急に揃ってびっくりした。端フリックでノリノリになれる譜面で結構好み。その近くにあるホールドにスライドを交差させる配置で、わざと持ち替えずに手をクロスさせるのが楽しい。

午後8時過ぎにゲーセンを離脱。つけ麺を食べて午後9時前に家にたどり着いた。準備してyukicoder 367に参加。今日のコンテストは問題文に難があった。

追記：この件についてはwriterの方とリプライでやり取りした。土曜日の日記のうち、最後のほうに書いてある。

yukicoder contest 367 - yukicoder

A。合同式の法を記述するのに独自の記号を使うのではなくちゃんと\pmodを使ってほしい。解法は全探索。式では $C$ 、 $B$ の順に出現するのに入力では逆順に与えられるため最初取り違えてしまった。

Bは再帰。必要になるのは $S_{0\dots 19}$ なのでメモ化すら必要なかった。どうせ $S$ は相異なるだろうと思ってuniqueもしていない。定義が循環していないことについては、問題文ではなく解説にでも書いておけばいいんじゃないかと思ったが、ここはまあ好みか。

C。相変わらず\pmodを使っていないうえ、なぜか入力の数列が配列の形で書かれている。しかもここで記号の衝突を起こしており本当に勘弁してくれという感じ。デカデカと場所を取って配列のindexingの説明をしているのに問題の内容には一切関係がないのも耐え難い。よく見たら入力も無駄に複雑な書き方をしている。writerもtesterも本当にこれでOKだと思ったのか？本当に？

問題文には中国剰余定理の復元をせよと書いてある。手持ちのものがgarnerのアルゴリズムしかないので、とりあえず $B$ たちを互いに素にした。ライブラリのどの部分でオーバーフローが起きうるかすぐにはわからなかったので、使用を諦めてこの段階で $n$ を全探索してみたら爆速で通った。

Dは $\binom{M}{N}\bmod{10^8}$ を答える問題。素因数分解した形を求めることで除算を回避した。階乗に含まれる素因数の個数は高速に求まる。 $M\lt N$ のケースで1WA。

E。いきなり視力検査が始まって笑ってしまった。問題文が不親切すぎる。Cで配列のindexingとかいうクソどうでもいいことをあれだけ丁寧に説明していたのに、こっちは論理式ポンと置いて終わりとは、どこをどうバランス取ったらそうなってしまうのか。 $\land$ にいちいち括弧がついているのも目がチカチカして苦しい。論理式を括弧の数を数えながら読むのは良い体験ではないので、日本語で書いてほしかった。

解法。全探索したら解けないかなと思ったが、 $|V_5|=2^{16}$ なのでここだけは真面目に解く必要がある。後ろ四つの条件から $A_2\ne A_1,A_3,A_4$ と $A_0\ne A_5$ がわかっていて、先頭の条件はたぶん $m_{A_0}\subseteq m_{A_1}$ のはず。まず $A_0=A_1$ のとき、 $m_{A_5}\in m_{A_0}=m_{A_1}\in m_{A_2}$ が得られて、この三つの集合が相異なることがわかる。逆にそうであれば集合の作り方から $m_{A_2}$ がほかのすべての集合を要素に持つためよい。

$A_0\ne A_1$ のときもやはり $m_{A_5}\in m_{A_0}\subseteq m_{A_1}\in m_{A_2}$ が成り立つが、このためには $A_5,A_0,A_1,A_2$ が相異なる必要がある。つまりどうやっても満たせない。 $N=5$ の時だけ以上のことを判定するコードを出したら通った。

Fはアハ体験。 $M$ シャッフルの遷移をすべて求めたい。各 $n$ について、 $D=n^2+4$ 、 $\alpha=\frac{n+\sqrt D}2$ となって、 $\left\lfloor\frac{\alpha^M}{\sqrt D}\right\rfloor\bmod{10^4}$ が次の値である。 $n$ と $\sqrt D=\sqrt{n^2+4}$ のような非常に近い2数について $(n+\sqrt D)^M$ の整数部分を求める問題は何度か見たことがある。絶対値の小さな数 $(n-\sqrt D)^M$ と足し合わせると整数になることを利用するのだった。

No.344 ある無理数の累乗 - yukicoder

しかし今回の場合、よく見ると分母に余計な $2^M\sqrt D$ が来ているのでうまくいかない。ここでしばらく手が止まった。どうにもならないので $n=1$ の場合を考えてみようとして、紙に $\left(\frac{1+\sqrt 5}2\right)^M$ と書いたところで、強烈な既視感に襲われた。これは……フィボナッチ数列の一般項の一部だ。

と言ったものの何もないところから降ってきたわけではなく、あらかじめ実験によって $n=1$ のときがフィボナッチ数列になることは分かっていた。ともかく、これは答えに近そう。正確を期するためググってみると、なんと分母に $\sqrt D$ もあって完璧。やはりこれが正解の方針らしい。

一般項を出す手順を利用するなら、三項間漸化式 $a_{n+2}=na_{n+1}+a_n$ を持つ数列を考えればよさそう。 $a_0=0$ 、 $a_1=1$ として計算を進めると、 $\beta=\frac{n-\sqrt D}2$ を使って $a_n=\frac{\alpha^n-\beta^n}{\sqrt D}$ となった。 $n=0$ でなければ $\beta^M$ の絶対値は十分小さいので、行列累乗で $a_M$ を求めれば答えも出る。 $n=0$ は $M$ シャッフルで変化しない。

シャワーを浴びて午後11時半からCF #832 div.2。

Dashboard - Codeforces Round #832 (Div. 2) - Codeforces

Aからちょっと難しい。 $s_1=a$ とするのが最適。どんな $S$ と $T$ についても、三角不等式 $|S+T|+|-T|\ge|S|$ から $|S+T|\ge|S|-|T|$ が導かれるため。Bは左のほうにあるAと右のほうにあるNを入れ替えた。 $\lceil n/2\rceil$ 回で可能。

Cは $a_1=1$ のとき負け、そうではなく $\min a=1$ のとき相手に $a_1=1$ の状態を押し付けられるので勝ち、そうではなく $a_2=2$ のとき……と考えていくと、 $a_1=\min a$ かどうかで定まるとわかる。

Dはちょっと難しい。まず、操作によって区間で立っているbitの個数の偶奇が変化しないため、少なくとも全体のXORが0である必要がある。この時点で取り出した列が奇数長の場合は解けている。偶数長の場合、端のどちらかが0だったらそこを無視することで奇数長のケースに帰着できる。そうでない場合、間のどこかで分割して奇数長の列を二つ作り、それぞれ1手ずつかける方法しかない。両端の値を同時にXORに含める方法がないので、独立に揃えられなければアウト。

間で分割する方法を探すのは、累積XORの値とインデックスの偶奇に対してインデックスのリストを保存しておき、取り出した区間内にちょうど良い箇所があるか探すことで行える。列全部が0である場合は答えも0となるが、これを取り出した列が偶数長のときにチェックしておらず1WA。気づくのに時間がかかった。

Eは手も足も出ず。いろいろ和の形で立式した後Wolfram|Alphaに投げていたが、うんともすんとも言わないものと超幾何関数を持ち出されるものしか作れなかった。終盤は眠気にほとんど負けていた。4完36位。

YouTubeを見つつコードゴルフし、午前4時から少し日記を書いて布団に入った。

ハーメルンの「高嶺清麿の実力至上主義の教室」を読了。主人公の能力が高いのはいいが、ツッコミ役なのはあまり好きではなかった。これについてはそもそも原作の設定がこの作品に合わないのだろう。ギャグを求めて読んでいるわけではないのだ。

syosetu.org

ほかのなろうをつらつら眺めているうち、午前7時くらいに寝落ちした。

11/05(土)

午後0時半起床。午後1時からTTPC2022に参加した。ソロ。

東京工業大学プログラミングコンテスト2022 - AtCoder

Aは $\gcd(Y-X,X-2015)$ の約数を列挙する。Bは財布の中の金額を持ってdp。魔法によって可能な遷移はあらかじめ求めておいた。Cは同じ値も適当に区別して順序付けることで中央値が一意に定まるようにした後、各値についてそれが中央値となる場合の数を数える。Dは木dp。Eは毎回 $O(|S_i|)$ かけて $a$ 、 $b$ がどこまで伸ばせるか計算する。どの文字が次に・前にどこに出現するかのテーブルを前計算しておけばよい。

Fで詰まった。最初は先頭から決めていこうとしていた。ひとつ前の要素は大きければ大きいほど良い。今の値を $x$ としたとき可能なひとつ前の要素を $f(x)$ と表して、この $f$ を更新していけると考えた。明らかに折れ線になるべきなのにうっかり一つの線分だと勘違いしたまま実装してしまい、long doubleで落ちてから有理数に書き換えてみたり無駄な時間を過ごした。勘違いに気づいて改めて考えなおし、実は $(i,R_i)$ で下側凸包を作ればいいんじゃないかと思って書いたら通った。

Gも凸包関連。 $d$ を固定したとき、 $L_i'=L_i-d\times i$ 、 $R_i'=R_i-d\times i$ とおいて $\max(\min R'-\max L'+1,0)$ 通りだけ数列が作れる。CHTを考えれば内側の $\min$ や $\max$ を折れ線グラフにできて、適切に区間を分割することで単純な一次式に $\max(\ast,0)$ をかませた値の和になる。ここまでくれば後は丁寧に場合分けすることで解ける。

より多く解かれていたLに進んだ。完全順列の拡張みたいなもの。最初に選んだ、後ろの項を固定して漸化式を作る方針は間違いだったらしくうまくいかない。包除原理を考えるとすんなり解けた。 $\lfloor i/M\rfloor=\lfloor P_i/M\rfloor$ を満たす $i$ が少なくともいくつあるか決め打って、その位置と $P_i$ の選び方を数え上げる必要がある。 $[0,M)$ 、 $[M,2M)$ 、……と $M$ 個ずつのブロックを作ると、その中でだけ入れ替えが行われるので、一つのブロックに注目して $i$ をいくつ使ったかを次数にした多項式を計算すれば、 $N$ 乗することで全体に対応するものが得られる。

Mはすんなり解けた。積の部分を $I\subseteq\{1\dots N\}$ についての $\prod_{i\in I}x_i\times\prod_{i\notin I}A_i$ の和と書き下し、和の取り方を入れ替えた上で $|I|$ についてループを回す。 $\prod_{i\notin I}A_i$ のほうは多項式 $\prod_i(A_i+x)$ を畳み込みで計算することで求まる。 $\prod_{i\in I}x_i$ は $M$ を素因数分解した後、素因数ごとにどれだけ $I$ に入れるか決めていても間に合う。

Hもすぐわかったが罠に引っかかった。SCCするとDAGをパスで被覆する問題になって、調べると二部マッチングに帰着できることがわかる。復元もマッチングを取ってくるだけらしい。しかしWA。実は「パス被覆」というと頂点がdisjointなものを指す。これはDiestelでも使われていた定義で、読んでいて謎に思った部分。今は適当に頂点を飛ばせばdisjointでなくてもよい。ではどうするかというと、ありうるパスすべてについて端点のペアを二部マッチングの辺とすればよいのだ。これで飛ばすべき箇所をスキップできる。

残り時間はIとOを考えていた。Iは $D$ を上位bitから順に見て分割しつつUFを管理することを考えた。binary trieの上でdfsしている感じで、戻るときにundoすればよさそう。しかし辺がうまく分割できないと勘違いし、深いところで何度もチェックする必要のある辺が大量にあった場合に間に合わないと思って諦めてしまった。

Oはセグ木のクエリのように列を分割して構築していくのがよさそうに見える。こう制限すると、行うべき操作リストとその間の依存関係が得られるので、4並列で最適に並べよという問題になる。ハードウエア基礎で習ったデータフローグラフのスケジューリングというやつだ。当然一般には解けないので、何か問題特有の構造を見抜く必要がある。実は適当な貪欲で解けないか？と思い、自分に直接または間接的に依存している最も遠い操作までの距離が大きいものから四つずつ取っていくコードを書こうとした。結局時間切れ。

ABCDEFGLMHの2700点で18位。Hは解説の別解に相当するらしいが、メモリには一切気を使わなかった。実際 $7000\times 7000$ のint型が190MBくらいだし、DAGなのでその半分弱になると考えればメモリ制限256MBは余裕のある値に見える。しかしよくよく提出を確認すると、最大250MBくらい使っていてギリギリだったらしい。

11/07追記：最大流のライブラリを使うと逆辺を持つところで制限に引っかかる。自分は蟻本にある2部グラフの最大マッチングを求める専用のライブラリを使っていたため難を逃れたようだ。

また、解説を読んでIの勘違いに気づいた。上位bitから見たとき、今見ているbitで使えるか使えないか判断がつかない辺集合というのは完全に分かれているようだ。よって深いところで何度もチェックする必要のある辺などは存在せず、上に書いた方針で解けてしまう。考察の初めのほうに書いたテーブルが間違っていて絶望。ソロ参加が近い点数で塊になっているため、一歩抜け出すためにもこれは是非とも解きたかった。upsolveしておいた。

それから朝方になってOの上に書いた方針を実装したが、当然のようにWAだった。解説を読んだ感じ、分割を決め打った時点で間違っていそう。

しばらくコードゴルフして、午後9時からABC276。

AtCoder Beginner Contest 276 - AtCoder

Aは正規表現ではうまく書けないようだったのでおとなしくPerlのrindexを使った。 $S$ の先頭に1文字足しておくことで答えを調整。見つからなかった場合はもともと-1が返るのでちょうどよい。

Bはよい。Cはprev_permutationという関数があるのを知っていたが、一応自分で実装した。末尾から逆順に見て単調減少である間取り出し、残った列の末尾の要素を取り出した列に含まれるそれより少しだけ小さい要素と入れ替え、残りを昇順にソート、あるいは単にreverseして後ろにくっつける。

Dは要素ごとに2で割り切れる回数と3で割り切れる回数を求め、残りが一致しているかチェック。求めた回数を見て全体の操作回数を求める。Eは単に始点からdfsしたら通った。

Fは何をやっても解けるはずだが面倒な手順を選んでしまったか。あらかじめソートして順序付けておく。ありうる $K^2$ 通りのカードの取り出し方について、 $\max(x,y)=a$ となるのは先ほどの順序で $a$ 以下であるカードの枚数を $k$ とすれば $2k-1$ 通り。これを管理した。新たなカードを追加する際は、それに対応する $k$ を新しく計算するとともに、これまで存在したカードの $k$ についてもいくつか1増やす必要がある。前者はBITでよいとして、後者に区間ADDで対応するため遅延セグメント木を持ち出した。

Gはあっけなく解けた。数列 $a_2-a_1,a_3-a_2,\dots,a_N-a_{N-1}$ を考えると、この和 $S$ が $S\le M$ を満たし、かつ全要素が $\bmod 3$ で0でない場合に $M-S+1$ 通りが答えに加算される。この係数は $a_1$ が取れる値の範囲から来た。 $N-1$ 個の要素のうち $k$ 個が $\bmod 3$ で1、残りが2だとすると、残り $R=M-k-2(N-1-k)$ をどう割り振るかという問題になる。

数列の要素としては3ずつしか割り振れない。 $0\le i\le R/3$ として $3i$ だけ使うとすれば、 ${}_{n-1}\mathrm{H}_i$ 通りの割り振り方があり、答えに加算されるのは $R-3i+1$ である。 $(R-3i+1){}_{n-1}\mathrm{H}_i$ を $R$ の係数とそれ以外に分けてあらかじめ累積和を取っておくことで、 $R$ もとい $k$ を決めるごとに答えへの寄与の総和が出せる。

Exに1時間くらい残したが解けなかった。0にするべきマスはすぐわかる。残り1と2については矩形領域内にある2の個数の偶奇が問題になるので、 $Q$ 本の $N^2$ 元連立方程式を解ければ各値を確定させることができる。しかし当然間に合わない。二次元累積和を考えると変数を減らせそうだが、一部のマスは0と決まっており、そこを弄る必要が生じて壊れてしまいそう。壊れないような位置の組み合わせだけで累積和を表すと、今度は変数が減らないかもしれない。お手上げ。

7完15位。解説を読む。Fの遅延セグメント木を使った部分について、答えの差分を考えればBITでよかったことに気づいた。Exは、0のことを考えずにマスを埋めたとしても結局必要になるのは0にすべきでないマスだけなので、条件が満たされているかどうかは壊れないようだ。もうちょっと別の言い方をすれば、自分は0だと確定したマスすべてに1を入れて残りを考えていたが、ここで入れる値は何でもよかったということ。

コードゴルフ。AはPerl 19BがVim+wcの17Bに負けた。日記を書いているとき、 $S$ の先頭に1文字足す部分の改善を思いついた。19Bのほうでは$/を連結していたが、文字列を単項マイナスすると先頭に負号が挿入された文字列となるので、これを利用するほうが短い。試すと最短タイの17Bになった。残念。

BはPerlで、負け。CはRustのprev_permutationがそれなりに短かったもののRubyで真面目に実装したらちゃんと縮んだ。DもRuby。そろえる値を $\gcd_i a_i$ に固定し、余った素因数2と3を数える方法。以降は手付かず。

金曜日のyukicoderの問題文について、改めてイライラしてきたためTwitterでお気持ち表明したところwriterの方からリプライをいただいた。以下のツイートのツリーにある。

日記に書こうと思ってたけどTwitterで言うか。昨日のyukicoder-C問題の問題文について、
・なぜか\pmodを使わず[]で法を表記している
・問題と関係ない配列のindexingを説明している
・上二つの記号[]が衝突している
でさすがに勘弁してくれという感じhttps://t.co/qdPNUPHgb3
— こたつがめ (@kotatsugame_t) 2022年11月5日

少しやり取りして、\pmodを使うこと、数列は配列の形式でなく下付き添え字で書くことについては納得いただけたらしい。「競プロでは普通こうする」とばかり言って具体的な根拠を何一つ用意できなかったのは申し訳ないところ。最近のAtCoderの問題文では特別な理由がない限り全部そうなっているから、くらいが理由になるだろうか。

ただ、「 $\dots$ 」で省略することについては、厳密性が失われるためどうしても避けたいそうだ。自分は、少なくともこの問題文のような使い方において「 $\dots$ 」が厳密性を損なうとは一切思っていないが、その根拠は競プロerとしての前提知識に依存してしまっているので主張するには弱い。ある程度競プロに慣れた人間が読みやすい問題文を目指している自分に対し、writerの方は数学好きなら競プロに不慣れでも把握できるような問題文を目指しておられたので、それは意見が合わないわけだ。

省略記号についてはXORや転倒数などの用語のように下で説明するのはどうかとか、厳密さを重視した問題文と競プロっぽく書いた問題文を併記してはどうかという意見を提案しておいた。

午前4時からは日記を書いていたが、昼前に切り上げてラノベを読んだ。1冊読了。「冴えない僕が君の部屋でシている事をクラスメイトは誰も知らない」。

今年4月に発売された本で、買ってすぐ読み始めたのに途中で放り出したまま半年も止まっていた。内容はあまり好みではなかった。タイトルの「シている」がわざわざ片仮名交じりになっていることから示唆されるように、性行為が扱われている。もっと言えばセックスフレンドの話である。主人公がヒロイン二人の間で優柔不断な態度を取り続けるという、言ってしまえばありがちな展開が、そういう描写によって生々しさを増していて肌に合わなかった。クラス内の人間関係も一部ドロドロしていて辛い。

午前11時くらいに布団に入り、スマホを触っているうちに寝落ちした。

11/06(日)

午後9時過ぎ起床。

昨日のリプライに続きが来ていた。実際に問題文が修正されたらしい。また自分は修正前のような問題文にOKを出したtesterこそ罪深いとも考えていたのだが、実際に議論した上でwriterの方の意向を最大限反映した結果だったようだ。このことを聞けたのは、道理のない悪感情を抱くことが避けられたという点で非常によかった。

そういうやり取りをするうち時間は過ぎて、午後11時半からCF。CodeTON Round 3でcombinedである。

Dashboard - CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

Aで少し詰まった。 $n$ がやたら小さいので探索で解くのかと思ったものの、値が足し算で変化するため状態数は多そう。考察で条件を見つけたい。swapできないとあまり嬉しくないように思ったので、swapでソートできる条件を考えてみると、 $a_1=1$ ならとりあえずよいことが分かった。このときどんな $j,k$ を取ってもswapできるので後ろが揃えられて、先頭は1なので当然最小となる。

逆に先頭以外に1があった場合、それを先頭に持ってくることも、足し算で値を大きくすることもできないため、どうやってもソートできないことに気づいた。つまり $a_1$ さえ見れば判定できる。わかってからサンプルを見たらかなりあからさまで、がっくり。

Bは簡単。 $x=0$ または $y=0$ のケースは個別に求めるとして、そうでないケースは文字列の一部を取るより全体を取ったほうが $x$ も $y$ も大きくなって嬉しい。よってそれだけ調べればよい。

Cはまあまあ面白い。操作によって、各インデックスで $a_i$ と $b_i$ のどちらか一方のみが変化する。よって最初の状態で $a_i=b_i$ かそうでないかがすべての $i$ で一致している必要がある。一致していた場合、 $a$ だけ見て全部0に揃えたとき、 $b$ は全部0または1になっている。全部0ならOK。全部1の場合は、 $(1,n),(1,1),(2,n)$ の3手で $b$ のみflipすることで全部0にできるため、これもOK。制限の $n+5$ 手には十分収まる。

Dも簡単。まず $a_i\mid a_{i-1}$ がすべての $i$ で成り立っている必要がある。 $b_1=a_1$ として、以降 $i\ge 2$ について $b_i/a_i$ と $a_{i-1}/a_i$ が互いに素であればよい。そのような $b_i$ の数は、 $a_{i-1}/a_i$ の素因数だけ見て行う包除原理で求められる。係数がメビウス関数になるやつ。素因数分解がボトルネックに見えるが、 $a_{i-1}/a_i$ の総積が $m$ 以下なので十分高速。自分は $a_1$ を素因数分解しておいて、その結果を更新する方法で実装した。

Eはちょっと面白いかもしれない。まず一つの文字列に対して必要な操作回数を考えてみる。右に一つシフトする操作は、任意の文字をそれより左に移動させる操作に読み替えられることに注意。(を $+1$ 、)を $-1$ として、全体の和を $c$ 、累積和の最小値を $m\le 0$ とする。括弧の個数を対応させるため、少なくとも $|c|$ 文字追加で挿入する必要がある。

$c\ge 0$ のときは)を $c$ 個後ろにくっつけるべきで、その後 $-m$ 回のシフトで累積和の最小値が $0$ となるようにすればよい。操作回数は $c-m$ 。 $c\lt 0$ のときは(を $-c$ 個前にくっつけるべきで、累積和の最小値は $m-c$ となる。累積和の末尾の値が $c$ だったことから $m\le c$ とわかり、相変わらず $m-c\le 0$ となっている。よって先ほどと同様シフトを $-(m-c)$ 回行う必要があって、操作回数は $-c-(m-c)=-m$ 回。

まとめると、操作回数は $-m+\max(c,0)$ 回とわかった。あとは頑張ると求まる。自分は部分文字列の先頭文字を固定し、 $-m$ のほうは $m$ とそれが担当する区間を管理するstackで、 $\max(c,0)$ のほうはBITで適切な位置の和を取得することで計算した。先頭文字を一つ左にずらすときの値の変化を、これまで見てきた値に加えられるオフセットの変化だと捉えればよい。

ここまで1時間。しかしFが解けなかった。とりあえず操作する区間に含まれる0は連続しているとしてよい。操作の順序が何通りかあるのが大変なので、できるだけ左のものから操作していくことにした。全部1で埋めた二つの区間を用意し、その間に0がいくつかあったと思ってそれを全部1にした時の新しい区間を作る感じで、どんどん大きくしていく。

操作がこのタイミングで初めてできるようになったという条件を入れる必要があって、状態が2次元になった。そこから二つ取ってくるので遷移が全体で $O(n^4)$ になる。ここから $O(n^3)$ にするのもそこそこ面倒で、追加でもう一つ落とすにはインデックスが入り乱れすぎており絶望。

5完96位で2678→2681(+3)。highestから300も下のレートでこうも微動だにしないと、さすがに自信を失ってしまう。明らかな衰え。冷静になって考えてみると、最近のまともなratedはもはやCFにしかないのか。AtCoderに続きCodechefもTOKIも消えたし、SRMは質が悪いし、DMOJは謎。精進の習慣を失ってしまった堕落者にはつらい時期だ。

その後午前5時までかけてFのupsolveをした。解説がなかなか読めず疲弊。適当にdpテーブルを定義すると計算順序に困る。短い区間を1で埋めるために、より右にあるもっと長い区間が必要になるからだ。そこで1で埋まっていない区間のほうを数えることにするといい感じになるらしい。

長さ $i$ の操作し切った文字列があって、そのうち左から $1\le j\le i$ 文字だけ1が連続しているものを $dp_{i,j}$ とする。 $j=i$ のケースは $2^{i-1}$ から $j\lt i$ のケースを引くことで求まる。先頭1文字が1と確定しているので自由度が $i-1$ になっている。残り $j-i$ 文字が全部0の場合は $dp_{j,j}$ 通り。そうでないとき、次に出現する1までに0が $k\ge 1$ 文字あり、またその1が $l\ge 1$ 文字連続しているとする。

間の0を埋められないという条件が $j+l\lt k$ で表現できる。左 $j+k$ 文字の決め方が $dp_{j,j}$ 通りで、残り $i-(j+k)$ 文字のうち左から $l$ 文字が1なので、ここは $dp_{i-(j+k),l}$ 通り。掛けて場合の数が出る。左から1が連続している部分の長ささえわかればその右がどうなっていようとあんまり関係ないというのも意識できていなかった。コンテスト中の別の方針では11...100...0のような文字列だけを数えようとして失敗していた。

今説明したのは遷移に $i,j,k,l$ が登場するため $O(n^4)$ で、コンテスト中と何も変わっていないように見えるが、こちらは $O(n^3)$ に落とした時の遷移が綺麗な形をしているためうまくいく。具体的には、 $dp_{j,j}$ をくくり出して後から掛けられるのがうれしい。まあ綺麗といっても2次元配列を斜めに見るような累積和が必要になるので、そこそこ大変ではあった。

いったん計算量の悪いdpを書いて、遷移を見て計算量を落とせないか考えるというのは、ハマると抜け出せない方針のため避けるべきだと思っていて、実際コンテスト中もやっぱりダメだったかと思っていた。しかし公式解説も $O(n^4)$ から $O(n^2)$ に落としていて驚愕。実際にコードを書こうとすると長くなるので、ちゃんと紙の上で考えられるようになるべき。

Submission #179837858 - Codeforces

朝までかけてラノベを2冊読んだ。

1冊目、「冴えない僕が君の部屋でシている事をクラスメイトは誰も知らない」2巻。新キャラとしてヒロインの姉が登場し、主人公とヒロイン二人の間の微妙な関係性が彼女によって引っ掻き回されることで前に進むという巻。実際に変化が見られるのはヒロインたちの心情のみだった。そもそもこの巻のメインがヒロインの掘り下げだったらしい。それにしても主人公がずっと中途半端な態度を取り続けるだけというのは印象としてあまりよくなかった。

「この世界、わたしに都合がいいようです！」2巻。1巻を読んだのは去年の4月。3巻が1年以上出ていないため続刊の見込みは薄そうという考えがあり、かなり適当に流し読みしてしまった。この巻はあまり主人公の活躍がなく、現代知識で何か発明してもそれを振るうのが新キャラの妹だったり、ラストは母親が締めたりといった感じ。薄れて消えそうな頼りない記憶によれば、1巻では主人公のバトルがあったはずなので、ちょっと残念。

合間に本の注文を行った。12月刊行のラノベをメインに17冊。読んだラノベに挟まっていたチラシに買っていない本を見つけたからだが、念のためといろいろ確認するうちに米澤穂信さんの新刊がいつの間にか出ていたことを知った。慌ててそれも注文。発売日からあまり間を置かずに気づけてよかった。

「わたしたちには、切り札が必要だった」
放課後の図書室で当番をしていた堀川次郎と松倉詩門は、忘れ物の栞を見つける。栞に用いられた押し花は、猛毒のトリカブトだった。一枚の栞が探索と推理の日々を導き、誰にも知られないはずだった過去があばかれてゆく。『栞と嘘の季節』は11月4日発売です。 pic.twitter.com/2J7PGoOvjN
— 米澤穂信 (@honobu_yonezawa) 2022年10月29日

午前9時からは日記を書き、正午就寝。先週の週記は修正すると言っておいてまだ手を付けられていない。