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

09/14(月)

夕方くらいに起きる。今日はHUPC day1だったが、起きた時点で終了していた。悲しいね……。

VimからJuliaを呼び出すやつで1つ、縮められていた。数値を変数に代入していたのだが、これはうまいことすると補完で書ける。補完で書くときは数値が1桁だと単語と認識されずにうまくいかないのだが、数値リテラルの先頭に0を書けばよいらしい。これはRubyなど大体の言語で8進数という意味になると思っていたのだが、Juliaはそうではないらしい。こうして0をくっつけておくと数値が必ず2桁以上になって、補完で呼び出すことができる。

eval"A,B,...="+`dd`.split*?,;c=0というコードは（cが定数変数になることを許せば）eval"A,B,...,C=#{`tr ' \n' ,`}0"に変形できる。

週記（2020/09/07-2020/09/13） - kotatsugameの日記

これはさらに1B縮む。空白と改行をtrの第一引数にしたいが、範囲指定をうまく使うことでエスケープやクオートの必要なしに書ける。例えば文字コード1の文字と文字コード33の文字（これは!のことだ）はどちらもクオートしなくてよいため、' \n'は[1]-!（[1]は文字コード1の文字とする）と書ける。これは文字コードでいえば1~33の文字を指定しており、空白（文字コード32）と改行（文字コード10）はどちらも含まれる一方、数値'0'~'9'は文字コード48~57であるからどれも含まれず、置換の対象とならない。

これを適用して、先週縮めたものが軒並み-1Bされた。本当にビビった。こういうイディオムで自明な更新点を残してしまうのはかなり危険である。

こどふぉdiv.2があるので、出る。A問題のサンプルが合わない。ちょっと考えてもよくわからなかったし、なんとなく僕ではなくサンプルが違うような気がしたので、B問題に移動して読んでいたところ、アナウンスでA問題に間違いがあることが知らされた。unratedである。

A問題が直って、やはり最初に書いたコードが正しかったことを確認し、提出。B問題も書いて出した。B問題はジャッジが壊れていたらしいが、通った。どういう壊れ方をしていたのかには興味がない。

Eは期待値をmod 998244353で求める問題だ。AtCoderか？なんとなく苦手意識を感じながら、適当に式を作って通す。

Fが全然通っていない一方、Gは結構通されている。これはdiv.2の最終問題だけ解いて終わる人々の影響もあるだろうが、実際にAから解いてF飛ばしてGを通した人も多い。なのでGを読む。結局わからなかったので途中であきらめてしまった。

Gは、数列が与えられるので、その部分列であって各要素がちょうど3回ずつ出現するものの個数を数える問題だ。ハッシュを使うらしい。baseを用意して、ある要素xを数列全体から探して、先頭から1,4,7,...番目にあるものにはbase^x*(-2)、それ以外にはbase^xを対応させると、各要素が3の倍数回ずつ出現する部分列は対応する数の和が0になる。あとは6回以上出現しないように範囲を絞るとよい。なるほど～。

通販サイトで本を購入した。今月出た新刊たちを10冊くらい。しばらくリアルの本屋に行く用事がないことが予想されるため、買っておいたほうが良い。できればリアルの本屋で買いたいと思っていたが、別に品ぞろえが特別良いわけではないし、それほど気にする必要はないかもしれない。

完食した。かなりつらかった。賞味期限は9か月前に切れている。消費速度を上げるため、毎回2食ずつ食べて（飲んで）いた。

Rubyで1000ACを達成した。これで1000ACを達成した言語は6つになった。

明日は昼からオンラインで打ち合わせがあるので、午前6時頃に布団に入る。うっかりハーメルンを開いてしまう。？？？？？

ドハマりして、確か午前11時くらいまで読んでいたはず。さすがにまずいと思って、寝た。

09/15(火)

死ぬほど頑張って13時ごろに目を覚ますと、ちょうど10分くらい前に打ち合わせが始まっていて、メンションが飛んできていた。許容範囲とみなす。自分で打ち合わせの時間を設定したので、一歩間違えればとんでもない無礼者になっていた。すでに無礼者かもしれない。

眠い目をこすってzoomに接続し、しばらく喋る。終わって布団に倒れこみ、昨日から読んでいるハーメルンをしばらく読んで、再入眠。

起きたら午後8時くらいだった。今日はコンテストは何にもないので、ハーメルンを読み切る。日付が変わったあたりで読了。

syosetu.org

昨日から読んでいたのはこれである。評価値ランキングにおいて、現在1位の「このすば*Elona」が登場するまで、ずっと1位に君臨していた作品で、超有名なものだ。

マジで、死ぬほど、面白かった。

作品の存在自体は知っていたが、ハリー・ポッターを読んだのが小学生のころでもうほとんど話の内容を覚えていないということもあり、ちょっと敬遠していたのだが、もうそんなこと関係ないくらい面白かった。

本当に信じられないくらい面白いので、二次創作が地雷じゃない人はぜひ読んでほしい。心の底からおすすめしたい。

終わり方も超きれいで、余韻が強すぎて読み終わった後1時間くらい身動きができなかった。

何とか身を起こしてコンビニに行く。真夜中なので原付に乗っても怖くない。コンビニまで行ってみると、営業が終了していた。6~24時らしい。コロナ許せないな？

帰ってきてパスタを食べ、また寝っ転がってハーメルンを読む。ハリポタ二次創作を探した。

午前6時になったので、再度コンビニに行って、お菓子とサラダとおにぎりとパンを買ってきた。最近全然野菜を食べていないため、ここらで1つテコ入れをする必要がある。

食べ終わって、また布団に寝っ転がったら、寝てしまった。

09/16(水)

起きたら午後3時だった。うつらうつらしながらハーメルンを読んでいると、生協から弁当が届いたので、受け取る。寝過ごさなくてよかったね。

また布団に戻ってハーメルンを読んでいたら、寝落ちしてしまい、次に目を覚ますと午後8時だった。意味不明。寝てしかいない。それもこれも昨日の「ハリー・ポッターと野望の少女」が面白すぎたのが原因で、作中世界からまだ脱出できておらず、全然現実感がないためである。

3年春学期の成績をツイートした。

これはいつもなら8月下旬、成績が出そろうや否やツイートしていたものだが、今回はタイミングを逃してしまっていた。ホスフィンから指摘を受け、投稿。各講義の感想ツイートもできていない。これも指摘を受けたため、今度書く。

よく考えたらHUPCは3日間一回も出れていない。AOJに追加されるのを待ってupsolveしたい。アリーナの方でやるのは何となく気が向かない。

最近全然ACLを書いていない。Rubyを見てみると、最大流・最小費用流が実装されていたので、コードを読んでコメントをした。この際、本家の実装も読解したのだが、現在自分が持っているライブラリとだいたい同じアルゴリズム・実装だったので助かった。

何もしていないのもアレなので、中国剰余定理を実装してプルリクエストを送る。これのverifyには、yukicoderの次の問題を使用した。

yukicoder.me

本来ならgarnerのアルゴリズムを使用して、64ビット整数に収まる範囲で計算する必要があるのだが、Rubyなら多倍長整数が使えるため、中国剰余定理のライブラリでそのまま計算できる。modが互いに素になるように正規化する必要もない。

VimからRubyを呼び出すやつで2つ縮められていた。どちらも998244353関連だ。

998244353を補完で呼び出すのだが、たとえば9や99を入力して補完しても、入力される数値によってはそちらがヒットしてしまうことがある。これを回避する方法が新手。

998244353=2^23*119+1=0x3b800001なので、この16進数の数値を書けばよい。+1Bだが、0を入力して補完することで必ずヒットさせることができる。なぜなら、先頭1文字が0であるような10進数の数値は0以外になく、0は補完にヒットしないからだ。

例のごとくRubyコードの短縮によって片方は取り返したが、もう片方は縮まなさそう。もう諦め気味。

と思って、朝方に寝るつもりでここまでの記事を書いたが、結局そのあとも起き続けていた。徹夜の構えだ。諦めそうになっていたコードも縮んだ。

atcoder.jp

これはたぶん、Vimのほうの更新と言ってよいだろう。削除しつつレジスタに保存するときに、直前の空白も含めるようにする。こうすることで、まずRubyのメソッドpの後ろに空白を挿入せず即座にペーストしてよくなる。このままだと更新にはならないのだが、ほかのところでも空白が役立つ。この空白の存在によって単語がそこで切れていると判断され、文末まで入力した後にBコマンド一回で戻ってこれるようになった。そこでコマンドを一回使用する用事があるのだ。

具体的に言えば、デクリメントをする。<CTRL-O>で使用するとカーソルの位置が単語の後ろまで行ってくれないので、以前は一旦挿入モードから抜けて、デクリメントして、もう一度挿入モードに入っていた。単語がうまく切れてくれたので、そのまま最後まで入力を終えたのちにBしてデクリメントできる。-1Bである。

ニコニコしていたが、別の問題でまだ更新されていた。いつも挿入モード中に<CTRL-R>でペーストしてばかりだったのだが、一旦抜けてPやらpしたほうが短くなる場合もあるようだ。他のコードもこれで縮みそうなものだが、あまり検証していない。

昼前、月曜日に注文していた本が届いた。通販、速い！

下に書いているようなライブラリのテスト作業の合間に、さっそく1冊読んだ。2巻で打ち切りになりそうな気配をビンビン感じている。

競プロライブラリは、これまで手作業でテスト（適当な問題に提出）してたけど、あこがれからonline-judge-verification-helperを導入することにした。ドキュメントがかなりしっかりしているので、よくわかっていない人が良く分かっていないなりに使用するのは全く問題ない。変なことしようとしないしね。

あとファイルの依存関係とかがチェックされていて、テストを作っておけば対応するライブラリを更新しただけでちゃんと必要なだけテストし直してくれるみたいだ。例えば、僕の線形合同式を解くライブラリは内部的に拡張ユークリッドの互除法のライブラリをインクルードしているのだが、この時互除法のほうを更新しても線形合同式のテストが走ってくれた。いやまあそうでないと困るのでそうであるだろうと予想はつくが、まじめにドキュメントを読んだりしていなくて、何回もpushして確かめる方法を取った。

ちなみに、デフォルトの設定ファイルだと毎回NimとC#の環境も作ってしまい、テスト時間が1分以上かかっていたが、これはC++使いの僕にはいらないので、ちゃんと設定ファイルをいじっておくべき。何回もテストを走らせた後、設定ファイルのコメントを読んでようやく気づいた。最初に読んでおこうね！

oj-bundleというコマンドを使えば、ライブラリの依存関係を解析してうまく1ファイルにまとめてくれるらしい。これもめちゃくちゃ便利だ。ライブラリの整備意欲がいや増す。とりあえず現在持っているライブラリのテストを書くことにした。

途中学食に行きつつ、いろいろ書いた。とりあえずyosupo judgeにある問題でライブラリそのままの問題は大体書いたと思う。b-フローはよくわからなかった。

Lowlinkのライブラリは、グラフが連結である場合にしか対応していなかったみたいだ。実装の参考にした螺旋本でそうなっていたからだ。これまで一般のグラフに対して橋や関節点を求める機会がなかったの、結構衝撃的だな。確かにほとんど使わないライブラリかもしれない。二重辺連結成分分解のライブラリもこれに依存しているので、こちらも連結グラフに対してしか使ったことがなかったらしい。バグが見つかってよかったね。

結構頑張ってテストを書いたが、いくつかまだ残っている。残っているものはtxtファイルに残して管理してある。前時代的かもしれない。

午後7時に寝る。木曜日は消えるだろう。

09/17(木)

消えた。

09/18(金)

日付が変わったあたりで起きてしまう。起床ツイートをせずにしばらくハーメルンを読んでいた。野望の少女に影響を受けたのと、あとエカスドクィナさんがツイートしていたのを見て、別のハリー・ポッターの二次創作を読んでいる。

ecasd-qina.hatenablog.com

起きて、別のラノベを読んだ。「お隣の天使様にいつの間にか駄目人間にされていた件」の3巻。これ好き！かなりいいので、かなりいい。ふぁぼん氏におすすめされたいくつかの作品との類似性を感じるため、これもふぁぼん氏に教えられたものかと思ったが、違って、確か店頭で惹かれて買い始めたはず。1巻がすでに最高に面白く、続刊を待ちきれなくてなろうの方で当時掲載されていた分を全部読んでしまったことを覚えている。

屋根がない場所で横倒しになった自転車を長期間放置した跡について。

足でこすってみたけど全然消えない。駐輪のマークってこうやって作るんだなあ。

AtCoderへの提出回数が40000回に到達した。つい半年くらい前まではvjudgeの1つに勝っていたはずだったが、最近確認すると1~5すべてに大差をつけられていた。競技人口の増加には勝てない。

1000ACを数える言語が6つもあって、かなり自慢。なんの自慢になるんですか？実際のところratedでまともに使えるのはC++だけである。

yukicoderに出たが、あまりに眠すぎて考えがまとまらない。必死に意識をつなぎとめてデバッグしていた。早めに寝る。

09/19(土)

午前7時くらいに起きて、しばらくハーメルンを読んでいた。1作読み終わった。読み終わったというのは掲載分を読み終わったということであり、この作品は更新が途絶えてしまっている。ネット小説の宿命。

syosetu.org

人は未完の小説を読んだ数だけ強くなる。（適当）

結構面白かったけど、とんでもない場面で更新がストップしているため、読後の精神状態もとんでもないことになった。

今日はACPC day1。ソロ参加行くぜ！したら7完で7位だった。途中解けなくてお布団インしたりしてたけど、それがなくても順位は変わっていなさそう。

AはA問題。BはFAだった。Bみたいなやつはとりあえず書いてから合わせに行くのがいいはずで、これはパソコンを一人で占有できるソロ参加の利点が効きそう。知らんけど。

C、D、Eを解いて、F。フローの流し直しで答えは出そうで、計算量はよくわからないけど書いてから考えよう、ということで書いたら4回もWAを生やした。辺の削除がへたくそだった。そこを直したら通ってびっくり。後から計算量を考えると、毎回探索は1回で済みそうだな、ということが分かった。ちなみにこれにはACLのコードを利用した。辺の情報の書き換えなど必要になるとは思っていなかったため、自分のライブラリでは対応していない。

Gはしばらく考えてもわからなかった。眠くなってきたので布団でゴロゴロしていたら降ってきて解けた。

夜まで頑張って起きて、ABCに参加した。全完3位だった。本番中は双対セグ木を2回貼ったが、どちらも必要なかった。いらないlogをつけてしまったが、AtCoderのTL設定はゆるゆるなので余裕。

コードゴルフもやったけど、よくわからない。これを書いている時点ではB以外の最短コードを保持しているが、Fとかはさすがに縮むだろう。見るからに同じことを2回書いている。とはいえ自分ではどう書くかわからないので、このままにしておく。

AはsedよりVimが1B短かった。文字列末尾への追加で差がついた。

こどふぉにレジり損ねたので、眠いし出ないことにする。明日はARC級のコンテストだ。ライブラリの整備などしておきたい気分だが、まあ明日は公式のライブラリを使用するだろう。

ACLにFFTがないのは、convolution_llで代用できるからだろうか。けんちょんさんのツイートによれば、FFTよりもconvolution_ll（NTT3回）のほうが速くなったらしい。にわかには信じがたい。

そういえば、FFTで誤差が出ない10^15くらいの計算をするなら、NTTは2回でよくなるのか。ATC001-CはFFTだが、これは要素の最大値が10^9くらいに収まるので、modを選べばNTT1回で計算できてしまう。ここまでくれば確実にNTTのほうが速いが、2回ならまだしも3回実行するconvolution_llがFFTよりも速くなるのか……。いずれ自分で検証してみたい。

ABCの最中、結構強めの眠気が来て困った。ARC級のコンテストの最中にこれが来るのは何としても避けたいため、今日はしっかり寝たい。朝起きてすぐにハーメルンを読み始めるなど言語道断。

09/20(日)

9時ごろ起きて、小説家になろうを読み始めた。ハーメルンじゃないからいいとかそういう話ではなく、眠気をとるためにしっかり二度寝するべきなんだよな。

https://ncode.syosetu.com/n1309m/

連載中になったまま8年経過しているらしく、途中で止まるのか……と思って読み始めたが、本編は完結していた。番外編として短編をいくつか投稿している最中に更新が停止していた。

「上位存在として人間の発展を見守る話」が好きだと宣言していて、これもその一種として読んだ。この作品に限らず一般に、いくら上位存在だからと言って向かうところ敵なしというわけではなく、同格の存在とのバトルシーンがある。物語としては必要な描写であると理解しつつも、ちょっと読んでいて精神に負担がかかる。それだったら主人公最強系をずっと読んでろという話だが。

「無職転生」という超有名ななろうの作品があるが、これは同格どころか明確に上の存在にやられる描写がかなりあって、読んでいる途中はものすごく辛かった。しかし全体としてみれば、やられる描写まで含めてとんでもなく面白いという結論になる。物語として必要な描写というのは、そういう意味で言っている。

読み終わったのがちょうど昼頃だった。昨日のF問題がPerlで縮められている。変数の値を変数名に使用するテクで、同じことを2回書かなくてよくなっている。型グロブでさらに縮めることができた。

昼食を食べてACPC day2に参加する。1時間弱で5問解いて、そこから1問も解けなかった。悲しい……。

途中、TSGのオンライン五月祭の配信を視聴していた。コードゴルフの部分だ。明日は僕も外部ゲストとして参加できることになっている。

ここでのゴルフはAtCoderと違い、途中でエラーを吐いてもそこまでの出力でジャッジが行われる。よくあるのは、入力の末尾まで到達したらゼロ除算をして落とす、というものだ。AtCoderでばっかりゴルフしているので、そういう見方が完全に頭からすっぽ抜けていた。ちゃんと覚えておいて明日に生かしたい。

夜、ARC級のコンテストがある。1時間ほど前から緊張してきて、2回もトイレに駆け込んだ。野菜をあんまり食べていないのもあり、おなかの調子が良くない。

実装がバグっていると分かった。issueを立てた。

週記（2020/09/07-2020/09/13） - kotatsugameの日記

これがRTされていたので、調子に乗って説明を加える。mod 998244353で計算しようとして壊れるのは、畳み込む配列の長さの和が2^22を超えだすあたりからなので、実用上問題になることはほとんどない。

コンテストが始まった。結果から書くと、ABCDEの5完で全体24位、パフォーマンス2943を記録した。レートは32上がったが、これはコンテストの手ごたえに比べると少なく感じる。僕のレートが直感より高くて困る。

A問題は3回WAを出してしまった。特に最後の1回はfirstとsecondを取り違えていたことによるものだ。これはひどい。

B問題も、愚直解と突き合わせるためにコードを書き換えている時間が結構長かったばかりか、デバッグ出力の消し忘れで1WA生やしてしまった。すでにA問題で3回WAを出しているので、あまり気にしなかったように思う。

C問題はもう見るからにフロー。制約も謎に小さい。

D問題はひらめきが冴えわたっていた。まず条件の一部をダブリングで求められることに気づく。場合の数を求めるのは、互いに素な区間の要素の個数を数えることに落ちるので、区間の両端それぞれで和を取って足し引きすればよく、これもダブリングで一緒に計算できる。このことに一瞬で気づけたのがかなり天才的だった。

E問題は期待値の問題。ライブラリコンテストじゃなかったんですか……？何もとっかかりが見えないので、とりあえず愚直に計算しようとしてみる。今回の問題では愚直コードが結構簡単に書けた。O(N^3)だ。ここから高速化を目指す。

まず、一番内側のループは等比数列の和を取っているので、公式に置き換えて消せる。次に、ループごとに値の変わらない変数がたくさんあるので、これをくくり出す。ループの順番を入れ替えることもした。

これでO(N^2)だ。ひとまず提出すると、WAが出なかった。今のところは間違っていないらしい。

最後にもう1回ループを削るのがかなり大変だった。P_iとP_jの大小関係に応じて足すのと引くのを入れ替える必要がある。さらに足す数もmaxやminが入り混じっていて、分離はかなり面倒そうだ。このあたりで順位表を確認すると、ABCEの人がたくさんいてびっくりする。僕はABCDなので負けている。このままではレートがとんでもないことになる！

面倒そう、との意識からあんまり頭が働かないが、1つずつ場合分けして、ループを分割してmaxとminを消していく。最後に、足す数のiとjを分離して、今jのループを回しているからiのほうをデータ構造で管理して、O(N log N)が完成した。残り5分。サンプルを試す。合わない！BITの区間の右端が1足りていなかった。震える手でもう一度サンプルを試す。答えが合う！ファイルの内容をcatしてクリップボードに入れるだけのコマンドを打つのに、タイプミスを何度かする。残り2分半で提出。ジャッジを待つ間に、ほかに高速化できるところがないか探そうとしたら、ジャッジが爆速で終了した。AC！思わず机をたたいて立ち上がり、部屋を歩き回った。

全体としては、最初のほうの問題でペナを生やしまくっていて全然よくないはずだが、E問題をギリギリでACできたことにかなり影響を受けて、良い結果を残したように感じてしまう。

E問題で必死に高速化をしていたが、そもそも最初に等比数列の和を取ったところで、もう少し計算を進めると1/2になった。いわれてみれば直感的にも納得できるのだが、本番では閉じた式にできたことに満足してしまっていた。

明日は昼からコードゴルフ配信に参加するので、確実に起きる必要がある。最近6時間で起きてばかりだし、生活リズムもちゃんと合わせてあるのでかなり安心できるが、変なタイミングで突然12時間睡眠をキメる癖があるため、用心したい。