週記（2020/12/14-2020/12/20）

12/14(月)

前日の午前10時に就寝、午後6時に起床。土曜日に届いたはずの生協の弁当5食を2日で消費してしまい、食べるものがない。いや、パスタのストックはあるんだけど、茹でたりする操作が面倒で仕方がない。冷蔵庫にりんごがあったので食べた。貰い物だ。

サークルの解説会の準備をする。今日はARC110の予定で、A問題とD問題は解説役に立候補してくれた人がいるので、B問題とC問題を準備する。C問題を用意している途中で解説会の時間になってしまったため、先にD問題をやってもらうことにしてその間に作りあげようとする。

D問題は組み合わせを使用する場合の数の問題だ。僕は解説の方法（言い換え）で解いたので、マス目の経路の数え上げに帰着する方法は解説会で初めて聞いた。こっちもかなり天才的だと思う。形式的冪級数はいまだに手を出すタイミングをつかみ損ねているテクニック。

布団に倒れこんでいたらJOI二次予選の問題が公開された。コードゴルフをしようと思って見に行ったが、難易度的にそんな縮めるような問題ではなかったので、ゆっくり解くだけにした。TLでいくつか言及を目にしているので、全部1から考察というわけではない。

A問題はいうことなし。B問題はゴールから幅優先探索だ。古代ICPCみたいな問題だな。C問題は祭りをスキップする理由がないことに気づけば簡単。D問題みたいな問題は大体担当する場所が区間になるので、今回もそうだろうと信じると通る。

E問題はTLで盛んに言及されていた問題。3-SATの形に直してもいいことは何もないので、意味をもとにして考えることにする。自由度的に考えればスパイじゃない人ができるだけ多いと嬉しくて、ではスパイでなければならないのは？というのをいろいろ試してみると、結局AもBもスパイのときにCもスパイになるのが唯一の場合であるとわかる。新たにスパイになった人を検出するとその周りだけ調べる、という風に更新すれば十分高速。

3-SATの形にすると各クローズは￢A∨￢B∨Cの形で書けるが、このように全てのクローズで否定されていない変数が1個以下であるようなSATをHorn-SATというらしく、線形時間で解けるらしい。解説スライドによれば、E問題を解くのに使ったアルゴリズムと似たようなことをするそうだ。

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0314/review/5059171/kotatsugame/C++14

無向グラフの全域木の個数を数え上げる問題に落ちる。これをググると行列木定理というものに行き当たったので実装したら通った。かなりびっくり定理だと感じる。こんなのPCKに出したって検索なしなんだから解けないだろ……。

mizuwater0.hatenablog.com

証明を探したらあった。自分でも追えるレベルで書かれていてうれしい。証明方法を忘れたとしても、主張だけでもちゃんと覚えておく必要がある。

AtCoderの解説作成ボタンが復活したらしい。

ラノベを読む。「羽月莉音の帝国」1巻。信じられないくらい面白かった。設定が僕の好みにピッタリ合致していてたまらない。序盤急成長しすぎじゃないか？と思うこともあったが、最初にちまちまやっているのはいくら現実的だとはいえラノベとしては面白くないのだろう。

雪が降るなかゴミ出しをした。思いっきりパジャマで外出したのに人目に触れてしまって失敗。もっと朝早くに行く必要があった。

昼前までかけて「羽月莉音の帝国」を一気に4巻まで読んだ。奥付を見ると刊行ペースが異常に速くてすごい。3か月に1冊以上のペースである。面白いのでまだまだ読んでいたいが、火曜夜はサークルでこどふぉバチャがあるのでそろそろ寝ておかなければならない。

正午、就寝。

12/15(火)

午後8時、起床。食事してすぐサークルバチャに参加する。今日は#549。本当は#545の予定だったが、これはコンテスト時間が2時間半で、午後11時半から予定されているリアルタイムのコンテストと間がないため2時間のものに変えてもらった。#545は明日に回される。

Bはダブリング。先頭の値さえ決めてしまえば、順列pを対応させるためにどれくらいシフトすればよいかわかるので、できる。あとはそこから2個ぶん、4個ぶん、……と先に進めていけばよい。

Cはずっと考え込んで、実は放物線が条件を満たすかチェックする場所は少ないのではないかと思って実装した。頂点から左右に離れるにしたがってy座標が2乗のオーダーで増えるので、左右に1000も調べれば事足りそう。分数で持とうとしたらオーバーフローしかねなかったので、そこも含めていろいろ注意して書くと通った。

想定解を読んでみた。放物線の方程式y=x^2+bx+cを式変形してbx+c=y-x^2に直してみると、座標(x,y-x^2)における直線を表していることになって、そのように変換した頂点集合の凸包の上に乗る直線をカウントすればいいらしい。天才的。

こどふぉdiv.3に出る。ふと思い立ってコンテスト中の画面を録画してみた。Bandicamの試用版を使っていたのだが、制限がかかっていて10分ごとに切れたのでちょっとびっくりしてしまった。E2で誤読した結果初手が違うのを修正するのに非常に時間がかかってしまった。

録画したものはゆっくり実況に仕立てて投稿することに決めた。なぜならやってみたいからだ。早速ゆっくりムービーメーカー3を落としてくる。

なぜかmp4を読み込んでも動画が映らなかった。いろいろ試行錯誤した結果、wmvファイルに変換してみたところうまくいった。とりあえずexoファイルに出力してAviUtlに持っていけるかどうかまで確認することにしたら、今度はAviUtlで動画が読み込めない。wmvが悪いのかと思ってaviファイルに再度変換してみても動かない。

結局AviUtlに入力プラグインを入れたら一瞬で解決してしまった。AviUtlってくらいだからデフォルトでaviファイルはなんでも読み込めるものと思っていたが、いろいろあるらしい。このあたりの話は全然知らないので必死でググっていた。

何とか動画の書き出しまでできたようなので、本格的に実況動画を編集していく。ゆっくりムービーメーカーの倍速はあんまり安定しないみたいで、そのあたりを確認しながらセリフを合わせるのはあきらめることにした。7時間くらいぶっ通しで編集し続けて、午後10時前にひとまずの完成を見たため、AviUtlで動画を書き出してみた。

死ぬほどずれていた。まずスタートから違うし、後半はほとんど静止画像になってしまっていた。原因がわからず途方に暮れていたのだが、AviUtlのほうで動画の詳細を確認すると、再生開始のフレームなどの値がおかしなことになっていることが分かった。ゆっくりムービーメーカーで編集するのはあまりよくないらしいので、泣く泣くAviUtlのほうで全部手作業で修正することにする。

セリフはすでに時間まで指定して置かれているため、そこに動画を合わせようとしたところ、どうにも合わない。ゆっくりムービーメーカーのほうで再生したものと突き合わせて比べてみてもよくわからないが、どうやらゆっくりムービーメーカーのほうでは全体的に時間の進みが速かったようで、その微妙に速い再生速度に合わせてセリフが置かれていてどうしようもない。泣く泣く1.3~1.5倍速くらいにして尺を合わせるが、どうしても想定していたセリフとズレてしまうシーンが出てきてしまった。そんなのを全部修正するのはさすがに絶望的なので、初めてだし……と自分を納得させて諦める。

そんなこんなで全体の修正が完了したのが11時。動画の書き出しに30分くらいかかるので、その間に学食に行っておく。帰ってきて書き出された動画を最後にチェックし、まあゆっくり実況の体裁をなしていたので投稿した。

見返すたびに粗が見つかる。自分が重要だと思ったものをいくつか書き残しておこう。

  • 話題が切り替わるときはセリフの間をしっかり開ける
  • 無理してセリフの末尾に読点を入れなくてもよい
  • コンソールの文字がつぶれて見えない
  • 考察を全カットするのはまだしも、実装をほとんどカットするのはよくない
  • ゆっくりがしゃべっている間でもコーディングは倍速しておくのがよさそう

録画環境も含めてまた何とかしておきたい。動画はまだ出したいという気持ちがある。午後3時、就寝。

12/16(水)

午後8時半、起床。昨日学食に行ったときに買っておいたパン等を食べて、こどふぉバチャに備える。今日は#545。

Aは座圧。適当に実装したら1000ms以上かかっていてビビる。BはZ-algorithmでどれだけ重ねられるかを調べるが、この時の判定で頭のおかしなことを書いていたため1WA。

CはSCCして気合い。本当は全頂点で週のそれぞれの日スタートの最大値を求めたいが、さすがに間に合わない。そこで、強連結成分ごとに1つ代表する頂点を決めて、それだけ計算しておく。他の頂点については、代表する頂点との距離をいくつも（ループを周回すると変わるので）求めておいて、それで日数を補正して計算すればよい。

解説を見たら頂点と曜日を組にしてSCCしていてびっくりした。確かにそうであることだなあ。サークルバチャの反省会でSCCって言われたのはこのことかと納得。僕は自分の解法が絶対的に正しいと考えて喋っていたので、公式解説の解法を念頭に置いていた人とは話が食い違っていたのかもしれない。

D問題は制約が1000で動かせる駒が10個あるから2^10を何か利用するのだろうなと思っていたが解けなかった。適当に実装したがずっと2番目のテストケースが突破できなかった。あきらめて解説を読んだところ、駒は3つでもよかったらしい。天才的すぎた。泣きながらupsolveしようとしたら80番目のテストケースでWAしてさらに涙が止まらなくなった。

昨日言っていた録画環境について少し考える。いろいろキャプチャソフトを調べていたところ、NVIDIA GeForce GTXシリーズのグラフィックボードを使っていれば使用できる公式のキャプチャソフト「ShadowPlay」があるらしいので、それを利用することにした。完全無料である。素晴らしいではないか。

GeForce Experience - NVIDIA GeForce グラフィックス カードの強力な支援ツール | NVIDIA

マイクラをすると思って買ったグラボだったが、今まで塩漬けになっていた。こういう形で役に立てることができてうれしい。

同時にゆっくりムービーメーカーもバージョン4に切り替える。ShadowPlayで録画したmp4を試してみたところちゃんと読み込めたのでうれしい。AviUtlとの連携も上々。

朝になって外を見たら結構雪が積もっていて楽しい気分になる。家から出る用事がないのでなんの心配もない。雪が降っているのを見るのは好きである。ただどうにも粒が小さい。とても大きな雪が灰色の空からゆっくりゆっくり落ちてくるのを口を開けて眺めるのが究極かつ至高な雪の眺め方であると信じてやまない。

昨日のこどふぉを確認してみたところ、E1が落ちてしまっていた。それに伴い順位もとんでもないことになっていた。せっかく動画を作ったのに、その回で落ちるのは非常につらいものがある。順位も「そこそこ良い」みたいな言及をしたくせにそこから転がり落ちたので決まりが悪い。

先週のABC185は、B問題とF問題がclimpetさんに取られたままになっていた。頑張って粗探しをする。B問題については言語をAWKに切り替えることで縮んだ。数値を1つずつ、符号を切り替えながら処理しようとすると長くなるが、2つ組にして処理すると短かった。F問題はPerlのまま更新できた。もともとサブルーチンでループしていたところを、再帰呼び出しに変更した。かなり遅くなると思っていたが、ギリギリTLEしなかった。

午前12時半、就寝。

12/17(木)

午後8時半、起床。起き抜けにヒカキンに24時間密着する動画を視聴した。動画最後のじゃんけんに負けて辛く悲しい気持ちになった。

食事をして、PCKの問題を1問解く。昨日のキャプチャソフトのテストもかねて録画しておいた。ゆっくりムービーメーカー4の設定をする。こちらでゆっくりを動かすのは、ほとんどプリセットされていたバージョン3に比べて少し難しい。

えでゅふぉ100に出る。100回目！5完だった。D問題で深く考えずに特攻したら思ったより難しくて時間を使ったように感じていたが、実際D問題を解いた直後に順位表を見ても1ページ目にいたので、みんな爆発していたのかもしれない。そのままE問題もそれなりの速度で解いて、システス前の順位は11位くらいだった。今回もスクリーンキャプチャを録画した。

えでゅふぉは後回しにして、まずPCKの問題を解いた録画をゆっくり実況にする。今回はテストの意味合いが強いと思っているので、長さもなるべく抑える。

ゆっくり魔理沙の語尾は「～だぜ」を代表とする男口調が一般的だと考えているが、ゆっくり霊夢の語尾は悩む余地がある。1本目の動画を作成した時には、できるだけ「～だよ」「～だね」を使用して中性に寄せていた。これは、ゆっくり霊夢と動画投稿者（自分）を同一の存在とする認識が根底にあったからだ。しかしこれはちょっと難しいと感じていた。ところどころ、不自然な（書いていて真っ先に思い浮かぶものではない）語尾を使用することになっていた。そこで今回は、自分とゆっくり霊夢を別個の存在であるとして、ゆっくり霊夢には女口調でしゃべってもらうことにした。それほどあからさまではないが、「～わよ」「～ね」などの語尾が現れるようになった。そういう決定を下したのは編集の終盤だったから、最初のほうは普通に「～だよ」が連打されているが、そこまで直す気力はなかった。台詞を結構詰めているので、発音にかかる時間が変わると全体が少しずつずれてしまう。

設定として、実際にゆっくり霊夢がコーディングしているところにゆっくり魔理沙が口出しするようなものを考えているので、視点は相変わらず自分と同一である。

今回の画質はフルHD、1920×1080だ。動画時間は1本目の半分なのに、ファイルサイズは2倍になっていた。縦横2倍なので当然のこと。きれいな比例関係だ。

今回も効果音は一切ないが、ゆっくりの表情をいくらか変更した箇所がある。ゆっくり霊夢は目を閉じ、ゆっくり魔理沙はジト目をするようになった。ほかの表情はたくさんありすぎて使えなかった。

4時間くらいで編集が終了し、午前7時すぎにアップロードが終了した。

前回自分で指摘したポイントはすべて考慮したが、今回もさらに自分で直したいポイントを見つけたので、列挙しておこう。

  • 喋ることを決めてから動画の尺を合わせるように倍速編集をする
  • 解説をするつもりならちゃんとする
  • 特に二分探索で区間の両端は何を表すか、セグメント木に何を乗せるかには言及したかった

最初にコーディング風景を4倍速にすることに決めて、画面に合わせるようにゆっくりのしゃべる内容を決めてしまったが、これはあまりよくなかったのだろう。

正午くらいに就寝。

12/18(金)

午後8時くらいに起床。昨日上げた動画にミスの指摘があった。ローリングハッシュにおける素数と基数の関係を「互いに素であればよい」としていたが、これは誤り。

じゃあ1と素数-1はダメだよ、と書いておくか……と修正したが、これも正確には違うようだ。乗法群における位数が大きければ大きいほど良い基数となるらしい。どういう風に書けばよいかわからなくなったので、間違っていることだけ書いておくことにした。

ラノベを読む。「羽月莉音の帝国」は、昨日と一昨日で5、6巻を読んでいた。7巻と8巻を読む。信じられない勢いでスケールアップしていて非常に爽快。1巻のはじめでは借金300万がどうのという話をしていたが、桁が8つ違う。信じられないくらいのサクセスストーリーで非常に面白い。10巻の完結までもう秒読み、いよいよ展開は最終局面を迎えたように感じられる。この後どのように話が閉じられるのか、すごく気になる。さっさと読んでしまおう。

朝方、TechFULコーディングバトルの32回に出た。この週記が公開されるのはイベント終了前なので、詳しいことは書けない。ただ、今回はシンプルに僕の実力不足で不本意な点数を取ってしまった。

えでゅふぉ100の録画も、全完はしていないが編集して投稿したいと思っている。しかし土曜日にはABCもあり、こちらも録画しておきたい。動画編集はかなり時間を食うことが分かったので、こういう風に溜めたりしてモチベーションを少しでも失えば、途端に投稿しなくなってしまうだろう。帰省で編集できる環境から離れても同じことが起こると思われる。

昼になって布団に入り、ハーメルンの更新を確認していたところ、「このすば*Elona」の更新が来ていた。およそ4か月ぶりか？うれしい。1話ごとの長さが長めなのもうれしいところ。

この日は寝落ちした。ブラウザの閲覧履歴を見るに、11時半ごろだったらしい。

12/19(土)

午後3時くらいに目覚ましで目を覚まし、そのあと30分ごとに寝たりうつらうつらしたりして弁当の配達を待つ。午後4時半ごろに配達されたのに何とか対応することができた。今日は午後6時半ごろからこどふぉがあるが、それまで微妙に時間が空いている。かなり眠いけどそのまま起きているかもう一度眠るかかなり迷った。迷っていると目が冴えてなかなか寝られない。

普段ならあきらめて起きてしまうところだが、今回はこどふぉよりもそのあとにあるABC186を見据えて、こどふぉを寝過ごすことも視野に入れてちゃんともうひと眠りすることにした。1時間半後の午後6時、問題なく起床できた。これは目覚ましによるものである。

こどふぉはABの2完で終わり。Bは1004が通ることをなぜか信じられなくてずっともっと速い解放を考えていたため、かなり遅くなってしまった。そのうえC問題が解けず最悪。BとCの間に結構な崖ができていた。2707→2642(-65)。

こどふぉは午後9時まで言及が禁止になっていたので、こどふぉとABCの間の30分は無になった。ABC186である。これは録画してまたゆっくり実況にするつもりだ。

AからDまではかなり速かったと自負しているが、EとFはそこそこ時間をかけた上にペナルティまでつけたので、終わってみると順位はそれほど良くない。ただA問題のFAが取れたので、動画映えはするだろう。全完後のコードゴルフの模様も録画しておいた。

D問題は過去に出題された問題とほとんど一緒である。コンテスト中に45Byteの解を作って提出した後、過去の問題のShortestを参考にしようと思って最短コードを見てみたところ、46Byteだった。深く考えず同じコードをこちらにも提出してしまったが、そのあとこれはまずいのではないかと認識する。とりあえずatgolferのbotを確認したところまだ拾われていなかったので、急いでサーバーをシャットダウンした。

自分ではそんなに悪いことをしたという感覚がない。このことについてツイートして、自分でもいくらか考えてみた。そもそも過去の既出問題であってもコンテスト中に書いたのと全く同じコードを提出するのがダメで、コードゴルフに関連する形で問題が表出したから感情的に反発しているのだろう。

日付が変わったあたりから、今日のABCの動画編集を初めて、午前7時くらいに完成した。動画を出力してYouTubeにアップロードしたところ、ファイルサイズが大きすぎるとはじかれた。不思議に思って動画ファイルのプロパティを確認したところ、150GBもあった。15分の動画なのにこれはおかしい。YouTubeのトラブルシューティングで「ファイルサイズの制限に引っかかる」みたいな項目を見ると、エンコードをしろと書いてある。

僕は動画ファイルを出力するのがエンコードだと思っていたけど、実際はデフォルトで無圧縮の出力がされていたらしい。ちょっと調べてエンコーダを導入し、出力してみたところ、なんと66MBになった。本当にびっくりした。これまで投稿した2本の動画はどちらもファイルサイズが数十GBだったが、これは無圧縮だったからのようだ。問題なく投稿できるどころか、以前はアップロードの待ち時間が30分くらいあったのに今度は一瞬である。

今回は効果音がついているし、霊夢と魔理沙の表情も幾分豊かになった。テキストを用いて見えにくいコードを表示したり、考察をtexで清書して表示したりといろいろやってみている。解説もそこそこ丁寧にやったつもりだ（特にF問題）。今回の教訓は以下。

  • 字幕を幅いっぱい書くと動画にしたときに見切れる
  • 相変わらず倍速してから尺に合わせてしゃべっている

C問題以降のコードゴルフはダイジェスト式に編集したが、これはよかったのではないかと思う。

A問題からD問題までは3分もかかっていないので、ここは等倍でそのまま流した。等倍なら時間の感覚がある。しかしE問題とF問題で倍速を使用し、こちらは時間の感覚が破壊されてしまうため、なんとなく臨場感がなくなってしまう。かといってカットを多用するのは競プロの試行錯誤の過程を全部ないがしろにしてしまう感じがしてどうだろう……。悩ましいところだ。割り切って編集スタイルをどちらかに寄せるのがよさそう。ただ自分で見てるとバグったコードを必死に書いている時間は滑稽なんだよな。

今回、ゆっくり霊夢の口調は完全に「～わ」「～ね」に振り切っている。「～わ」が連続してしまう箇所がいくつかあって、そこでは「～よ」を適度に挟んでいる。

「羽月莉音の帝国」の9巻を読んだ。いよいよクライマックス。というか予定されていることを考えるとあと1巻でシリーズが完結するのが信じられない。どのような過程がどのように描かれてどこに着地するのだろう。いろんな想定がありえて、10巻を読むのが怖くもあり楽しみでもある。10巻の扉近くのページだけ読んでいたが、これまで各巻の主要人物が紹介されていたページに革命部5人だけしか描かれなくなっていて非常に不穏。

寝る前まで定期的に投稿した動画の再生回数を見ていたが、すでに200回再生に届こうとしている。やっぱりABCってだけで耳目を集めるのだろうか。こどふぉとかやってる場合じゃないな。他にはA問題のFAをプッシュしたのもよかったのかもしれない。

正午近く、就寝。

12/20(日)

午後9時起床。昨日投稿した動画がかなり伸びている。1000回再生を突破していてびっくり。やはりAのFAが注目されているようだ。動画のURLツイートの引用リツイートを見たり、リツイート先を見に行って言及を確かめたりしていた。

動画の冒頭に置かれているから、数秒で当該シーンを視聴することができる。さらに2、3分見るだけでD問題までの速解きを把握できる。見るだけで何が特徴的なのかわかる物事は動画映えする。ただ「速い」だけ。

ただ、これを認めてしまうと、競プロ実況動画がなかなか作成できなくなってしまう。そういう目に見えて特徴的なことが起こるコンテストなんてそうそうないだろうし、「解説しながら解く」タイプの動画に落ち着いてしまうのだろうが、それは文章でよい。そもそも図を作成するのを面倒がっているため、解説動画の作成は致命的に向いていない。まあ自分は腐っても日本で上位50人に入るプレイヤーであるから、そういう人間がどのようにコンテストに参加しているのかを実況することに何らかの需要があると信じて続けていきたい。

ラノベを読みつつ、日付が変わった直後のこどふぉを待って、参加した。pretest時点ではABCDが通っていたが、C問題はシステスで落ちてしまった。3完で2642→2643(+1)。

Aはルークの動きをイメージするのが難しいので純粋に数字の入れ替えの問題として捉えるべき。Bは直感的に11...00か00...11の形しかないことがわかるが、念のため示した。

Cは実験するとかなり何でもできることがわかる。僕は下から偶奇でつじつま合わせをしていったが、これは誤りで、上のほうの桁を変えると全部反転してしまう。正解は上から貪欲らしい。各桁で使える個数がたくさんあるのに、なんで貪欲ができるのかよくわかっていない。

Dは無限場合分け。1つだけ2種類両方試さないといけないことに気づいて、それに対応するためにコードを思いっきり書き換えたのがよかった。試すための関数を別に用意して、それを何回も呼び出す。これまでifとelseを連ねていろいろ分類していたが、条件を満たす場合を全部計算してしまうことにするとより安心できる。

Eは全然わからなかったが、Grundy数は最大でO(sqrt M)くらいになるらしい。これ何回も見たことあるな。あとは確率の遷移行列を書いて何かするんだろうけど、実はそこから先はTLで解法ツイートを見なかったのでわかっていない。

「羽月莉音の帝国」の10巻を読んだ。非常に良かった。終わり方もかなり良い。ネタバレは絶対にしたくないので、何も書かない。著者の至道流星さんはほかにも経済ラノベをいろいろ書いているようなので、買いあさりたい。

シリーズの途中で主人公の羽月巳継が「ネットはそれほど強い力を持たない」といったことを言う。そのあたりは微妙に不穏な空気が漂うシーンだったので、ネットが何かの障害となる伏線かと思ったのだが、特にそのようなことはなかった。結局、この発言はラノベが書かれた2011年ごろの認識によるもので、今（つまりネットが実社会に強く影響を及ぼすようになった時点）から見ると違和感があるというだけだった。

月曜提出のレポートが2つある。朝までのCGレポートと、夜までの幾何学序論。とりあえずCGを片付ける。

幾何学序論は前回のレポートを書いてからの講義内容をまずチェックしなければならない。チェックした後レポート問題を読んだが、なぜか急にやる気を失ってしまいハーメルンを開いてしまった。Game of Vampireを読み返していた。やっぱりこれ好きだなあ。

冷静になると、夜のサークル解説会はまだ1問も解説役が決まっていないのでスライドを用意しておく必要がありそうだし、レポートも1文字も書いていなくてかなりまずい状態。とりあえず寝ようと思って、寝る前に日記を書いていたら午後3時半になってしまった。シンプルにヤバい。