週記（2021/10/04-2021/10/10）

10/04(月)

正午起床。寝ている間に大学院科目の先行履修の書類が受理されたとのメールが来ていた。一安心。

手癖でYouTubeを開くと、チュウニズム14新曲のAJ動画が投稿されていた。2人目が出たらしい。

www.youtube.com

シャワーを浴びて学食に行く。先週金曜日から秋学期が始まったということで生協の営業時間も更新されており、学食の昼の部は30分伸びて午後2時まで営業しているので、かなり余裕があった。帰ってきてから1時間くらいかけて溜めていた分の日記を書き、投稿した。

それから夕方のインターン先の定例会までは、それに向けた作業をしていた。とりあえず進捗報告用のスライドを1ページ用意する。さらに、先週Kaggleのチームを組んでから何もしていないのに罪悪感を覚えるので、とりあえずコードを手元で動かしたりしてみていた。入力データを絞ってちょっと実行するだけでも結構時間がかかって辛い。

定例会は今週も普通に終了。続いてKaggleチームのミーティングも行われ、そこで少しばかり質問した結果、どんなコードのどこを弄ればよいのかが分かった。一般に特徴量を増やす関数としてadd_featuresがどこかで定義されており、ここでオレオレ特徴量を入れて学習を回しスコアを見るのだとばかり思っていたが、それももちろん重要な一方で、モデルをいろいろ弄ってみるのも、最後にチーム全員のモデルをアンサンブルするため必要なステップらしい。魔法の特徴量は見つかったら根本的にスコアに影響を与えるものの、そう簡単に見つかるわけがないから、チームに貢献したいならモデルのほうでいろいろ試してみるべきかもしれない。

機械学習のPythonコードを手元でいろいろ変えつつ動かすのは、いちいち先頭から実行しなおす手間がかかってさすがに耐えられないため、ローカルにJupyterを入れた。試しに起動してみるとかなりいい感じ。大学のPythonを扱う講義ではいっつもGoogle Colaboratoryを使わされるが、似たようなものがローカルで動いていると感動を覚える。それでもらってきた.ipynbファイルを開き、自分の環境に合わせて少し書き直した上で走らせてみた。依然として実行に時間がかかるのが嫌なので、とりあえずデータ量を絞っていたところ、生成されるべきファイルがないというエラーが出て困っていたが、それもちょっとした手直しで解決して、一通りは動くようになった。

と、かなり良い感じになってきたがここでいったん放置して、4年ゼミのスライド準備を始めた。教科書のキリの良いところまで行間を埋めることに成功したので、Beamerを使い体裁を整えながら打ち込んでいく。あまりに久しぶりすぎていろいろ忘れてしまっていたが、これまで用意してきたTeXファイルを見ながら書いていった。5時間くらいかけて、とりあえず読んでおいた部分のスライドが完成。教科書のページ数としても、スライドの枚数としても、発表のためにはこの2倍弱の分量が必要だろう。しかし教科書の次の部分は章末の演習問題である。これまでのゼミでは、演習問題はみんな無視してきたが、そうはいってもとりあえず目を通しておくくらいはするべきだろう。そうして読んで、やっぱりやらなくていいかな……という気持ちになったので、次の章に入ることにした。次の章の内容は幾分簡単そうに見えるので、どうにでもなるだろうと思って今日はここで切り上げた。

明日は1on1の予定だが、前回金曜日から一切業務に手を付けていない。学業に専念している感じなので仕方ない、明日は正直に何もやっていませんと言うことにした。インターン先は良い会社なので、学業を優先させてくれるのだが、そうはいっても何も言わず急に業務を放り出すのはよくないだろう。これからは事前に、この時期は学業で忙しくしています、ということを報告しておきたい。

14AJの手元がまた1本投稿されていた。結構前からずっと追っているチャンネル。99AJでもうなんか全てがすごい。

www.youtube.com

今日は夕方かなり眠気があったつもりだったが、それでもいつの間にか午前4時過ぎまで起きてしまっていた。夜更かしが本当に常態化しておりまずい。とりあえず完全に朝になる前に……と布団に潜り込み、午前5時過ぎ就寝。

10/05(火)

午前11時前に目を覚ます。TLをちょっと眺めていたら眠れなくなって困っていたが、気合を入れると再度意識を落とすことに成功した。確かそれが午後1時過ぎのことだったと思う。

午後2時半、1on1前の目覚ましで起床。起き抜けはかなり頭がボーッとして身動きが取れなかった。途中分割されているものの、合計の睡眠時間だけ見れば結構寝ているので、深い睡眠から無理やり起きてしまったのだろうか。ちょっと怖い夢を見たが、すでに細部は失われていた。

1on1は10分で終了。次回はゼミが終わった翌日の金曜日にお願いした。さすがに1日くらいあれば何か報告できる進捗が産まれてくれるだろう。

今日の5限に講義を1つ入れたはず、と思ってClassroomを確認したところ、初回である今週は課題なしで、スライドや動画を見るだけ。「AMATERAS RAY」（なかなかかっこいい名前だ）というサービスを使って適当な目的変数を予測してみるという内容で、プログラミングは一切行わなかった。僕らのような素人がGUIでポチポチやっている裏では、サービス提供元の作り上げたごっついモデルが動いているんだろうなあと考えていた。今回の講義で出てきた言葉から自分なりの「キーワード」を探して回答せよという指示だけあったので、「説明変数」と答えておいた。

Service Amateras

大学生協に寄って買い物をしてから、街中に出てゲーセンに行く。その前に腹ごしらえをしようと思い、一閃閣というラーメン屋に行こうとした。この店は仙台に2店舗存在する。自転車を停めた場所がその2店舗からちょうど等距離にあるように思えたので、これまで行ったことのない店舗のほうに行こうと思い、しばらく歩いていたところ、以前この辺りを通りかかったときは閉まっていた「昭文堂書店」という本屋が営業しているのを見つけ、ふらふらと吸い寄せられてしまった。

棚いっぱいに古びた大きな専門書が詰め込まれている、絵に描いたような古本屋さんだった。頭の白くなったおじいさんが店番をしていて、客は僕一人。人文学の本で埋まった棚を眺めつつ、何も買わずに出るのもアレだけど、ここにある本を買ってもなあ……と思っていたが、別の棚に行ってみるとそっちは完全に理系だった。店のちょうど真ん中を境に、いわゆる文系向けの本と理系向けの本が分けられていたようだ。並んだブルーバックスの背表紙にMS-DOSとかC言語とか書いてあるのを見て、これはもう古典だな、と思うなどしていた。数学に関する本やコンピュータに関する本を一通り確認して、「プログラマの数学」という本を購入した。ホスフィンが売り払った本である可能性があるらしい。世間が狭すぎる。

うっかり30分くらい古本屋に吸い込まれていた。出てから改めてラーメン屋を探すと、目の前に建っていたものの、閉まっていた。慌ててホームページを確認すると、どうやら平日は昼間しかやっていないらしい。そんな……と思いつつ、完全に一閃閣の気分になっていたので、一番町まで延々歩いてもう1店舗のほうに向かった。そちらは問題なく営業しており、食事にありつけた。

ゲーセン。新曲の13+、「Love & Justice」を何回かプレイしていたが、SSSは不可能であるという結論に至って放り出した。難しいところは全部8分全押しで通りそうだが、全然安定しなかった。あとは12+のAJを6個99AJに更新し、理論値を1曲出し、13AJを1個出し、さらにもう1曲理論値を狙ったが出せずに終了。

最後のトラックで「TiamaT:F minor」をプレイしたところ、1500点伸びて14では初めてSS+に乗った。序盤の鍵盤を適当に擦って大量失点しているので、ちゃんと運指を考えたらワンチャンあるのかもしれない。

ざるそばを食べて帰宅。帰る途中、大通りから分岐した脇道の横断歩道を一時停止なしで渡ろうとしてしまい、ちょうど横から車が来ており、お互い急ブレーキをかけてギリギリ接触せずに済んだ。なぜ気づかなかったのかなど反省点が多いはずだが、そのときちょうどぼんやりと考え事をしていて記憶が定かではない。

帰宅してちょっとコードゴルフをした後、昨日の分と合わせて日記を書いた。今日は結局ゼミ準備をしなかった。午前4時就寝。

10/06(水)

午後2時頃に目を覚まし、atgolferの更新を見て縮まないかしばらく考えていた。なんとなく縮みそうな気がしたのでいったんパソコンの前に座ったが、しばらく試行錯誤して、途中で別の問題が縮んだりしつつ、元の問題はやはりダメだったことが分かったので、また布団に戻った。

tatyamさんの、PAST8のバチャをツイキャスでするというツイートが流れてきた。慌ててAtCoderのトップページを確認するも、特に表示はされていない。ツイキャスを見ても画面が小さくよくわからなかったので、別の問題を解いているのだろうと勝手に納得して閉じた。しかし、他にもPAST8のバチャに関するツイートをいくつか目にして、試しに以下のURL（過去のPASTから推測できた）を直接打ち込んでみたところ、見事にPAST8のコンテストページが開けてしまった。

https://atcoder.jp/contests/past202109-open

慌ててパソコンの前に戻り、解き始めた。Aのdc 11Bはさすがに自明すぎて取られていた。Bはそもそも負け。Cはdc 22Bを書いたが、この日の夜遅くに21Bに更新された。DはPerl 53B。

Eは自分では綺麗に書けなかったが、Rubyのかなり上手いコードが夕方提出され、そのあまりの美しさにひっくり返っていた。

atcoder.jp

Fは結構頑張ってRuby 78B。GはRubyで二分探索するだけで90B。HはC++で適当に書いて、IはCython。そこから先の問題はそう簡単に縮まなさそうなので、急いで解く必要があったのもこれくらいか。午後6時くらいに一段落したと感じたので学食に行く準備をしたが、やっぱり気になってさらにコードゴルフしている間に学食が閉店してしまった。

PAST8がいつ公開されたのか提出を調べてみると、なんと日付が変わったあたりの提出が存在したことが分かった。なぜAtCoderのトップページに出ていないのか。腹が立ったので愚痴をツイートした。

しばらく別のコードゴルフをしていた。今日の起き抜けに縮んだ問題がさらに大幅に縮められていたので、それを取り返す。しばらく格闘した後にまたPAST8に戻ると、いろいろ縮められていた。先に述べたE問題のコードが提出されているのを見つけたのも確かこの辺りだったはず。他にI問題も縮められていた。I問題に関しては方針を大きく切り替え、先に3倍を繰り返した要素たちの列を作っておいて、全体をソートしてから特定の位置の値を出力することで大きく縮めることに成功した。

さらに問題を解く。JKはC++、LもC++で書いたが、二分探索の中でさらにBITを使ったらTLEしてしまった。logを2つつけたらTLEした、のようなツイートをどこかで見たので、ああこの問題だったのだなと思った。冷静になるとソートして尺取りすれば線形時間で判定が行えるので、それで通した。解説では、尺取りは上端と下端を持つというようなことが書かれているが、実際にはどちらかを今見ているインデックスに合わせておけば区間がそれぞれちょうど一回カウントされるようになり、後から半分にする必要もないし定数倍も半分になってくれる。コードゴルフしようとしたが、RubyではなくCrystalでないと通らないようだったし、そちらも謎のREが出てしまったので放置。

午後9時過ぎ、さすがに明日のゼミ準備がまずい気がしてきたので、そちらに取り掛かった。途中集中力を失ってコードゴルフに戻ったりTLを眺めたりしていたが、午前3時半くらいになって一応の完成を見た。月曜日に進めていた分に比べて、今日やった箇所は章が変わって初めのほうということもあり、かなり簡単め。それでも、教科書で直ちにわかるとか書かれている部分が微妙に怪しく感じられたので、結構丁寧に（あるいはねっとりと）証明を書いた。

ICPCのアカウント設定を済ませる。Activateが必要で最初ログインに失敗したときはちょっとドキッとしたが、問題なく完了した。アカウントに登録する情報について、去年急に「Number of Full-Time STEM Semesters Completed」という項目が増えて困惑したことを覚えている。去年は以下のような理由で5を記入し、そのことを日記にも書いたのだった。

STEMとはScience、Technology、Engineering、Mathematicsのことで、それに関連する学科を指しているのか？とりあえず、僕は数学科で2年半、つまり5セメスター過ごしてきたため、5と書いておいた。

週記（2020/10/12-2020/10/18） - kotatsugameの日記

今年はICPC横浜大会公式ページ最下部のQ&Aにおいて、この項目が初期値0のままでよいと明言されているため、それに合わせておいた。未だに「Number of Full-Time STEM Semesters Completed」で日本語サイトを検索すると僕の上の週記がトップに表示されるため、迷い込んでしまう人のためにそちらにも追記しておこう。

アカウント登録 | ICPC 2021 Asia Yokohama Regional

明日に備えて寝ようと思ったが、ふと思い立って、以前より温めていた短編小説のプロットを書き始めた。核となる競プロ関連のネタはしばらく前に何となく考えていて、加えて最近pixiv小説でテーマが合致した執筆応援プロジェクトとやらが行われているのを知り、以来数日なんとなく想像をたくましくしていたところ、ここにきて急にいろんなシーンが思い浮かんできたので、それを忘れないようメモしようというわけだ。大まかな流れを書いておけば、その適切な位置にシーンをメモ書きの形で挿入し、保存しておくことができる。

しかし、思い浮かんだもののうち覚えていたシーンだけ付け足しつつ書き上げてみると、すでにいい具合のボリュームがある気がする。これをしばらく寝かせて新たに思いついたシーンを挿入するのもよいが、それよりも今は、これを実際の短編小説として出力してみたいという気持ちが大きい。あまりに楽しみすぎて明日早いことを忘れ、4時間かけて完成させてしまった。一読して誤植などはなさそうに見えたため、そのままpixiv小説に投稿した。約8000文字。ちゃんと起承転結を意識したつもりで、12が起、345が承、6が転、7が結だと考えている。

www.pixiv.net

せっかくの日記なので、後書きっぽいことをここに書いておこう。以下の文章には上の短編小説のネタバレが含まれる。

先に話した核となるネタはもちろん、フロアの電気を全部消すスイッチの組み合わせを求める問題である。しかしそこからどういう話にするのかは非常に難しかった。導入はまあどんなものでもよいだろうけど、消した後はどうなるのか。あるいは消す過程を詳細に記述することも考えたが、これもどうもうまくいかない。貪欲などしていてはダメだから、結局基底を取るしかないのである。そこで、電気を全部消したときにビルの隠された空間を知る、という展開を思いついた。すると今度は現実味がなくなった。単純に壁が動いてお宝が……よりはリアルにありそうなことを描きたい。というわけで、全部消したはずの電気がついているという流れで発見されることにした。最初に「奥まったところから光が漏れ出ている」という気づき方を考えたが、ビルのフロア丸々使った1室という舞台に奥まったところを無理なく設定できなかったので没になり、外から見て気づくという流れになるようにした。

ここまで、つまりビルの電気を消し、外から見て隠し部屋に気づくという流れが、考えていたプロットの根幹である。あとは適当に考えたシーンを書き加えただけであり、それをどうやって思いついたかについてはほとんど覚えていない。が、「ビルの電気がついたり消えたりしているのを見て」のくだりはなかなかお気に入りである。実際のところ、フロアの光量が激しく増減しているのを見てもそういう表現にはなると思うが、多少は許してくれよな！という感じだ。相変わらずラストをどうするか決められなかったので、最初はリドルストーリーにするつもりだったが、さすがにそれは放り投げすぎだろうということで、ちょっとばかりショッキングな描写を入れてお茶を濁した。あとは伏線になるように適当に言葉を散りばめて完成。友人の感想では伏線が弱く感じたという話だったが、まあ初めて書いた小説にしては良いだろうと自画自賛しておく。

長さ8000文字は思ったより短く、もうちょっと余計な描写を入れてもよかったかも、と思わないでもない。1、2のあたりではまだ周囲の描写を入れたり、地の文と会話文の量に気を配っていたのが、だんだん文章を書くのに夢中になっていってそういう配慮は姿を消し、自分の書いたプロットに忠実に、必要なことしか書かなくなってしまった。また、自分なりの伏線回収の部分に圏点を打ったのだが、「言う事全部重要おばさん」が思い浮かんでダメだった。

投稿してすぐ、朝にも関わらず数件のいいねやRTが来て嬉しくなった。そのままTLを見ていたい衝動に駆られるが、4時間後にはゼミが開始してしまう。午前9時半就寝。

10/07(木)

午後0時半起床。眠すぎて動けないが無理やりスマホを睨みつけて眠らないようにする。何とか布団を這い出し、食事してゼミに備える。

ゼミ準備としては、スライドを元に口頭で説明したいことを紙にまとめておくのがよいのだった。幸い今日の発表は2番手になったので、1番手が発表している間に見直しを進める。すると証明が壊れていることに気づいてしまったが、教科書の参考文献を試しに検索してみると元論文が見つかったので、それを見て修正。何とか間に合ったが、土壇場の変更をスライドにちゃんと反映しきれていなかったのが悔しいところ。発表している最中に修正点をいくつか見つけたので、逐一メモを取って後から直しておいた。今回もスライドをここに載せておこう。

Apostol_Chapter4_4.10-4.11_Chapter5_5.1-5.2.pdf - Google ドライブ

発表内容としては特に問題なし、だったと思う。記号の読みとかスライドの記法とか、そういう話はいくつかされた。正直次回まで覚えていられるかは……謎。メモとしてここに書き残しておこう。句読点を．と，に置換していたが、これは別に半角でもよく、教科書に合わせて数式にピリオドを付けたりするならば半角のほうが良い。また\hat{a}は「エーハット」と読む。あと、これは僕の宗教を許容されたのだが、量化子付きの命題を書く際に\forall x\in A.\;\varphi(x)とピリオドを付けて書く、一部の数学基礎論で見られる記法についても話題に上がった。

ゼミが終わってから、今日アップデートでチュウニズムに追加された新曲の譜面動画を見ていた。13に追加された2つがどちらもかなり強めに感じられる。AJは難しそうだ。

ゼミ中に部屋のチャイムを鳴らされたが、その時は数十分以上後にまた来てくれと言ってお引き取り願った。夜ごろまた来る、というようなことを言っていたが、午後5時くらいに来たので対応。電力自由化を利用して電力料金を下げないかという話だった。面倒なので断るタイミングを伺いつつ、ついついごみ箱から電力料金のはがきを掘り出して見せたりしていたのだが、その場で入力させられそうになったので直截的に「その気はない」と言った。するとすんなり引き下がってくれたのだが、最後少しの会話で僕が親からの仕送りに頼って暮らしていることを明かすと、そういう人を勧誘してはならない決まりなのだと言う。よくわからない決まりだが、お互いにとって意味のない十数分だったことが明らかになり、ちょっと申し訳ない気分になった。

夕方はTLに人が多いことが期待されるので、昨日投稿した小説のツイートをセルフRT。目論見通り新たに数人がいいねやRTをしてくれて嬉しい。

昨日のPAST8-I問題が、昼頃さらに縮められていたようだ。これはもう、いったい何をしていたのかというレベルの典型の見落とし。非常に悔しい気持ちになった。

今日こそ学食に行く。今日初めてのまともな食事ということで、入るだろうと楽観視して丼の小にラーメンの大を合わせたのだが、全然食べきれなかった。なんとか丼とラーメンの麺だけは腹に収めたが、トッピングのから揚げは見るだけで嫌気がさしてしまったので、残した。うっかり癖で大サイズを注文したのが失敗だった……。少し膨らんだ腹を抱えてえっちらおっちら帰宅した。

しばらくTLを眺めていたが、急激な眠気に襲われて午後8時半くらいにベッドに倒れこみ、そのまま日付が変わったころまで寝ていた。

起きてからしばらくは、以前に読んだなろうの読み返しをしていた。印象深いシーンを思い出して探していたのだが、2500話近くあるとタイトルを眺めて思い出すにも結構限界がある。ずっと遡っていきつつ他のシーンも拾い読みしていたが、実は求めていた話は結構最近のものだったらしい。そういうことを、途中TLを眺めたりしつつ午前5時までやっていた。

今週日曜日のOpenCupがなくなったらしい。これで2週空いたことになる。

朝方、さすがに何もやっていなくてまずい気持ちになったので、とりあえずPASTの残りの問題を解いた。MNO。

Mはなかなか苦行枠で、奇閉路があるなら頂点の値が1つ決まり、そうでないなら適当に定めてチェックすればよいと思っていたが、サンプルを試しているときに負の値が許されていないことに気づいた。幸い修正は容易で、二部グラフの場合のみ自由度があって色が同じ頂点すべてに同時に足してもう一方から引けるので、それで負の値を消そうとしてみればよい。実は「+ Graph」とほぼ同じ問題で、解説の方針も同じだったようだ。

atcoder.jp

Nは明らか。Oは、最初順列が与えられることに気づいていなかったのでしばらく迷走したが、なんとか解けた。ある部分木の値たちは、最終的に誰に負けることになるかが上から見ていくことで決定できるので、それとの大小関係だけ考えればよい。と思っていたら解説はもっと頭がよく、情報が矛盾しないならば勝敗が決まっている戦い以外はどちらが勝ったとしても対応する色の割り当てがただ一つ存在することから、その自由度を計算するだけで木dpっぽいことをせずに解いていた。

O問題をこの方針でコードゴルフして1時間半、さらにL問題のREの原因が添え字の和のオーバーフローであったことに気づき、それを直してさらに縮めるのにまた1時間半使った結果、午前9時になってしまった。明日は午後3時半から1on1で、まだ一切進捗を産んでいないどころか起きられるか怪しい時間になってしまった。急いで布団に入ったが、そこからうっかりハーメルンを1時間読んでしまい、午前10時就寝。

10/08(金)

午後2時半起床。シャワーを浴びたりしているうちに時間は過ぎ、結局ろくな進捗がないまま1on1に突入してしまった。

インターンはそういう契約なのだから、と励ましの言葉をいただいたが、この信用を失うのは怖い。自分ができないことをできると言うべきではないが、自分ができることをしないのはさらに良くない。とにかく今日は、ちょっとした勉強会として機械学習モデルの実装の説明をしていただいて、1時間弱で終了。

10/07(木)の朝方に投稿した短編小説は、一応pixiv小説の執筆応援プロジェクト・テーマ「夜」への応募作品として書いたものであった。昨日数回セルフRTした甲斐あってかPV数がかなり伸びており、確認すると「注目の応募作品」のところに自分の小説が載っていた。これはかなり嬉しいが、ツイッターのFF数と競プロ界隈の内輪ノリを頼みに無理やりPV数を伸ばした印象があって微妙な申し訳なさも感じる。そんな中、競プロ界隈と全くかかわりのなさそうな見ず知らずの人が、どういった経緯でか僕の小説を読んでくれて、面白かったとリプライしてくださったのが一抹の救いになっている。つまり、確実に僕の小説を評価してくださったということがわかるのだ。

1on1が終わってからすぐ大学に向かう。今日はおよそ20か月ぶりに対面でサークル活動が行われるようだ。ちょっと遅刻してしまったが、バチャをやっている静かな中にシュッと入って座り、自分もコーディング。今日のバチャはAOJ-ICPCから星の多い問題を選んだということで、実はほとんど解いたことがあったのでそれを再現するだけになってしまった。最後に初見の問題に挑もうとしたところで時間切れ。

AOJ-ICPCの500点に「薔薇園の魔女」という問題があって、初めて読んでから長い間解けていなかったのだが、今日のバチャで出てしまった。僕は不可能枠だと思っていたので見た瞬間飛ばしたが、1人時間内に解いたサークルメンバーがいて度肝を抜かれた。解法を聞いて感服し、帰ってから通しておいた。細かな実装テクとして、イベントソートして値を管理しつつ最大値を取るものは、値を減らす操作を増やす操作の前に並べると、ソートした後愚直に1つずつ処理していってよい。

AIZU ONLINE JUDGE: Code Review

これで500点の残りは「Spherical Mirrors」と「凸多角形柱工業都市」。両方幾何で逃亡の構え。

午後8時から三連続でコンテストに参加した。まず第一弾としてSRM815。18位で2540→2536(-4)。厳しい。

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

EasyはbitDPやるだけ。制約が50×220で攻めてるな？と感じたが、冷静になれば余裕で間に合うことがわかる。Medは親の顔より見たグリッドを鏡写しに並べていく問題。丁寧丁寧丁寧に実装していたらルームの黄色が何人も僕より先に通していて涙が止まらなかった。Hardはよくわからない。大きい値から適当に貪欲みたいなことを考えていたが、どうにも正当性が信じられない。M^N\le 10^{18}以下という制約を各Nに対して考えてみたが、うまく分けてもどうしようもなさそう。最後に、適当に値の範囲を絞って全探索してみたが、N=7、M=372のケースでTLEしてそのままコンテスト終了。

チャレンジフェーズ前は30位台で、部屋の提出もあんまり落とされなかったので絶望していたが、システスが終わってみるとバカスカ落ちていて18位になった。特に、Medを僕より速く解いた黄色が何人も落ちていて、ひどい話だが安心してしまった。別に僕がチンタラやっていたわけじゃなかったのだ。ただレートは下がってしまった。

次にyukicoder 317。全完。

yukicoder contest 317 - yukicoder

Aはよい。Bはdcで殴ってしまった。Cは全探索だが、0個の品物を選んでしまい1WA。Dは左右からdpしてマージ。Eは男女それぞれ誰まで見たかを持つdpで、遷移で頓珍漢なことをしており1WA。Fはそれぞれのバス停にいる確率の遷移行列を累乗するが、このとき1単位時間先の確率も持っておく必要がある。Gはセグ木。HはFでバス停3つを区別していたのを、バス停1とそれ以外の2つに分けて行列累乗し、1台だけ見たときバス停1以外にバスがいる確率を求めてM乗し、1から引けばよい。

Hはかなり面白く感じられた。ただ問題文が正確でない・（一般的な書き方をしていないため）読みにくい、という理由でコンテストに対してはネガティブな印象を抱いた。CとEが特別にひどく、TLではDの良い部分列の定義も不必要であると槍玉に挙がっていた。コンテスト後にいくらか改定されたようだが、この日記を書いている時点でやはりまだ読みにくく感じられる。こういうものはテスターが排除するべきではなかったのか。特にE問題は、問題文を忠実に解釈すると絶対に以下のツイート（Cと書いたがEである）の質問文のような解釈になるはずである、が、修正を執拗に迫るほどの熱意もないので、愚痴るだけ愚痴って放置。

さらにCF #747 div.2。途中寝てしまったが何とか全完。

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

Aはギャグ。Bはkを2進数展開してn進数として解釈する。Cは2回あれば全部の要素を操作できるので、1回以下でできるかを全探索。Dは各人に対応して真偽の頂点を作り、辺を張る。このグラフの作り方は実質2-SATだが、辺の特徴から真の人数、あるいは偽の人数を最大化できるということで、このことは直接グラフを作りに行ったほうがわかりやすい。E1は根が6通り、あとは上から見ていくとき一度分かれるとその後は独立だから、各頂点で4通りの自由度がある。指数を10^9+6で割った余りを計算したが、別にその必要もなかったようだ。

E2は面倒。自由度が4とならないような頂点たちは、すでに色が決まった頂点とその祖先たちだけで、高々O(nk)頂点しかない。これらについては各色の通り数を直接計算することにして、残った頂点の個数を数えて最後に4の肩に乗せて掛け合わせる。Fは問題文がちょっと難読気味だが、n項で総和sの数列であって、どの連続部分列の和もkとならないものが存在するかを答える問題。累積和を考えると、0\dots sから0とsを含めてn+1個選び、どの2つの差もkにならなければよい。何個選べるかを考える。端から貪欲に詰めていけば、周期2kで埋まっていき、最後に余った個数とkのうち少ない方だけ使える。s=kの場合必ずYESになるが、これも処理できていると勝手に思っており、しかし全然そんなことはなく1WA。

問題が解けたので目が冴え、コンテスト後はしばらく日記を書いていた。朝方切り上げ、布団に入ってハーメルンを読んだ。1作読了。「東方古神録」。主人公のチート具合が好みで、結構面白かった。キャラも過剰に変な感じはしなくて、受け入れやすい。

東方古神録 - ハーメルン

午前9時就寝。

10/09(土)

午後8時起床。今日は夕方からCFで4hコンがあり、ちょっと興味を持っていたが、実際その時間に目覚ましで起きてみるとあまりの眠さに衝撃を受けた。耐えられず二度寝し、この時間になった。急いで食事してABC222。

Exawizards Programming Contest 2021（AtCoder Beginner Contest 222） - AtCoder

Aはどう書いていいか悩み、AWKでprintfを使った。Bは適当にRaku。ここからはC++を使った。Cはなかなか実装が重めで大変だった。Dは自明。Eは辺ごとに通る回数をカウントすると、うまく±をつけて目的の値を作る問題になって、制約をよく読むと絶対値が105で抑えられるので、dp。Fはオイラーツアーして遅延セグメント木を作り、辺を行き来するたびに区間更新でその辺の重みを足したり引いたりした。Gは式を整理すると、あるmに対して10^i\bmod{m}が1になる最小の正整数iを求める問題になって、ちょっとだけ位数のことを考えたが、合成数modのBSGSを持っていることを思い出してそれを使った。最初答えが全部0になってキレそうになったが、確かに100が1であることに気づき、耐えた。答え0を検出しないようにライブラリを適当に書き換え、祈るように投げるとAC。

Hは、まずメモ化再帰で正しい値が出ることを確かめ、ループで直接求めるコードまで書いた。これは畳み込みっぽかったので、オンラインFFTをやれば解けるんじゃないか！？と思ってこの後ずっと実装していたが、結局合わせることはできなかった。そもそもオンラインFFTはlog 2つだから、107の制約では通らないか。

H以外の解説を読む。Fは木をちょっと拡張すれば直径の両端のどちらかが必ず答えになるらしく、なるほどなあという気持ちになった。G問題で使った合成数modのBSGSだが、今回のケースでは底とmodが互いに素でない場合必ず解なしになるので、最初少し探索してgcdを処理する部分が必要ないらしく、面白い。またオイラーのφ関数の約数を全探索する方法も紹介されており、こちらのほうが素直だったなと反省。

今日の昼頃にPixivランキング事務局からメッセージが来ていて、水曜日に投稿した短編小説が小説ジャンルのオリジナルウィークリーランキング83位に入ったことを知った。嬉しい……！小説を投稿した時のツイートのインプレッションは21000ちょっとだが、そこからリンクを踏んだ人は400人にも満たないようで、PV数のもう半分弱はどこから来たのかがよくわからないが、もしかしたらランキング経由で来た人がいるかもしれないと思うとワクワクする。

コードゴルフ。A問題はVimが最短になっていた。10000を足してから左端の1文字を削っている。そういえば、dcで出力の基数に10000を設定すると、10000進数のつもりなのか4桁で表示してくれたような……？と思って提出したものの、0は常に0とのみ表示されるらしくWA。Bはdcの22B解がほとんど自明で、僕はコンテスト終了直前までH問題をやっていて提出が22時40分過ぎになったのだが、22時38分の提出があって非常に悔しい気持ちになった。そのほかもコンテスト終了時点では何一つ最短を取れていなかった。このような状況はかなり久しぶりではないだろうか。衰えを感じる。

悔しいので、とりあえずC問題をRubyで、D問題をOctaveで縮めておいた。そうしているうちに午前2時になったので、FHC R3に出た。

Facebook Hacker Cup - 2021 - Round 3

ABD1の43ptで82位。R2を59位で通過したとき、Tシャツにバッジが付くのがR3の上位200人であることを知って残念に思っていたが、結局R3でもそれなりに良い成績を残せた。

ABcCを通して59位。R3進出、Tシャツ獲得に加え、上位200人なのでTシャツが何か特別仕様になるはずR3の上位200人に対する褒章らしい。ぬか喜び……。

週記（2021/09/20-2021/09/26） - kotatsugameの日記

Aは、更新をそれぞれ区間と見てマージしていけばよい。setで区間を管理するいつものやつだが、区間の端がどうなったら区間をマージできるのかを間違えたり、区間の左にあるものとマージし損ねたりして、サンプルを合わせるのにはそれなりに手間取った。Bは3列しかないため、行って戻って行って……のようにジグザグに動くことがない。考えるべきは、2点の間の移動方法と、2点からそれぞれ端のほうに行ってUターンしてくる場合のコスト。レベルで降順ソートするのは当然として、前者はセグメント木に3x3の距離行列を乗せればよい。後者は、Uターンする地点は近ければ近いほうがよく、これはsetで取得。さらにその間が通行できるかにはこれまたセグメント木が使える。安全性をとって定数倍悪めの解法を書いたら実行に結構時間がかかり、ちょっとヒヤヒヤした。

D1も値で降順ソートしてUF。以前に使ったロボットが同じ連結成分に存在するなら、それを流用できる。D2、D3については、UFのマージ過程を木にして、これの頂点とある点の間のパスに対していろいろ弄ることができればよさそう。HLDでできると思って、beetさんのライブラリを窃盗して1時間半格闘していたが、結局サンプルも合わなかった。

またABC222のコードゴルフに戻る。EはちょっとRubyで書いてみたら当然のようにTLEしたので、C++で清書した感じにしてお茶を濁した。FはRubyで、結構な時間を使って頑張った。

午前7時半くらいに布団に入り、ハーメルンを読む。2作ほど読了。

東方古神録～幻想幼女～ - ハーメルン

「東方古神録～幻想幼女～」。昨日読んでいた「東方古神録」の続編で、エタっている。

はりまり - ハーメルン

「はりまり」。霧雨魔理沙がホグワーツに入学する話。非常に面白かった。東方Projectにおける魔法とハリポタにおける魔法の違いの考察も興味深いが、何より魔理沙のキャラと立ち位置が好みだった。しかしこちらもエタっていて悲しい。

「はりまり」を読み終わったのが午前10時半。そこから午後1時半のHTTFまで3時間しかないが、ひと眠りしようと思って一度はスマホを手放した。しかし微妙に目がさえて眠れないこと、日曜日はHTTF以外に特に予定がないことなどを鑑みて、このままずっと起きていることにした。というわけでさらにハーメルンを漁って2作ほど手を出したが、片方は文章の拙さを我慢して読むほどでもないなと思ってしまい、もう片方は知らない作品の二次創作だったために、どちらも少し読んで投げ出した。

昼過ぎだったため、少し日記を書いて時間を潰し、午後1時半からHTTF。

デジタルの日特別イベント「HACK TO THE FUTURE for Youth+」 - AtCoder

途中までは非常に調子が良かったが、最後の1時間は全然スコアを伸ばせず、結局6位まで落ちてしまった。

A問題はビジュアライザをポチポチして1265823。このスコアはずっと更新されず、もしや理論値引き当てたか！？と思ってわくわくしていたが、openのほうで終了30分くらい前にもっと良い解が提出されていた。1x1ブロックはなるべく使わないようにしていたのだが、ビジュアライザを見た感じ思ったより使われていた。

B問題とC問題は全く同一のコード。まず、置いて印をより多く覆えるようなものを、タイブレークは盤面の中心にあるものを優先的に取るようにして貪欲に置いて行った。この段階では連結性を特に考えていない。次に、1x1ブロックを置いて全体を連結にする。2つの連結成分からそれぞれの代表点を全探索して連結成分同士の距離を出すのを全ペア行い、最も距離が近かった2つを実際に繋ぐ、ということを繰り返す。最後に、1x1ブロックに被さるように別のブロックを置いて、必要なコストが下げられる場合は置き換える、という操作を繰り返す。以上の3ステップであった。Bが1500000弱、Cが1890000ちょっとだった。

ここからさらに、1x1ブロックでつなげる際に縦と横のどちらを先に動かすかを両方試して少しスコアが上がり、以上のステップ全体を座標を調べる順番にある程度のランダム性を持たせたうえで時間の許す限り繰り返すことでBは1560000弱、Cは1900000弱になった。コンテストとしては、入賞を逃したし、抽選のアマゾンギフト券も外れてしまって残念。

昨日のABC222-Cが縮んでいた。配列の値をmapで加工してpで出力するとき、mapの中で出力するとsplat演算子が必要ない、というのは何度も何度も何度も何度も何度も何度も何度も見たのにいまだに忘れてしまう。絶望。

午後6時から少し遅刻してECR115に出た。コンテスト終了直前にGが通ったがその後Hackされ、現在6完。

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

Aはよい。Bは選ぶ曜日を全探索して、2日とも行ける人と片方しか行けない人を数える。Cは数列の要素から平均を引くと、足して0になるようなペアを抜き去るしかないので、ちょうど平均と一致する要素だけ特別扱いして頑張る。わざわざ尺取りで数えたが、logをつけても変わらなかったかもしれない。Dは補集合を数える。片方が3つとも同じ場合はもう片方が必ず3つ互いに異なるので、両方2つずつ同じ値であるような3つ組を数えて引けばよいようだ。これは、(A,B),(A,\ast),(\ast,B)のような組だとわかるので、(A,B)を全探索すれば簡単に求まる。

Eは英語が読めなくて苦労したが、「右下右下……」と「下右下右……」のことを言っているようだ。数え上げは非常に面倒な気分になったが、差分更新にO(N+M)かけてよいことに気づき、愚直にどこまで伸ばせるかを求めて足したり引いたりしたら通った。FはbitDP。かっこ列典型の累積和を考えると、確かに使う文字列集合を決めれば末尾における累積和の値も決定し、それ以外の情報は必要ではない。ある文字列を足したとき、先頭からの累積minと現在の累積和が一致しているような場所の数がdpの値に足される。これは前計算で求められる。注意点として、ただ累積和の出現回数をカウントすると、'('で（累積和が増えて）終了するようなかっこ列をカウントしてしまう。文字列を足して先につなげる場合は、累積minが非負でなければならないので、そのチェックもする。

Gは落ちてしまった。まずn=|X|と置くと、片方がn桁の場合はもう片方は自由、そうでない場合は両方n-1桁にならなければいけない。片方がn桁の場合はそれほど一致しまくるケースが作れないだろうと思って愚直で書いた（ここを突かれて落とされたし、冷静になってみればそういうケースはめちゃくちゃある）。両方n-1桁の場合は面白かった。繰り上がりありでn-1桁ごとに和を取った文字列を用意して、Xの先頭1文字（これは'1'でなければならない）を取り除いた文字列を先頭にくっつけてZ-Algorithmすれば、もし求める位置があるならば2桁目からn-1桁目までは必ず一致する。1桁目は自分で削除したので、最後に文字列末尾の繰り上がり処理をキャンセルして一致を確かめればよい。

しばらくコードゴルフをしていたが、さすがに眠くなってきた。先に日記を書き上げて投稿する。予定通り日曜日は消えた。

10/10(日)

消えた。