09/07(月)
昼頃、寝落ちから目覚める。たいぺーに昼食に誘われているのを発見するが、眠くてあんまり動けないので断ってしまう。
しばらくコードゴルフをする。Rubyで入力を読むのには、eval"A,B,...="+`dd`.split*?,というイディオムを頻用する。このとき、同時に何らかの変数を初期化するコード一般に適用できる短縮法を思いついた。
eval"A,B,...="+`dd`.split*?,;c=0というコードは（cが定数変数になることを許せば）eval"A,B,...,C=#{`tr ' \n' ,`}0"に変形できる。このままでは同Byte数だが、\nを実際の改行にすることで-1Bできる。定数の書き換えが多すぎてTLEしてしまうことは考えられるが……。これの適用範囲はかなり多そうだ。コードゴルフが一段落したときに、コードを先に作っておいて一気に更新することにしよう。ということで今は放置。
昨日寝落ちして書いていない分の日記を書いて投稿した。すでに夕方である。今日はまだ1食も食べていない。
昼食に誘ってくれたたいぺーに、今度はこちらから夕食の誘いをかける。ホスフィンも加わって3人で待ち合わせをする。
午後6時半に待ち合わせの予定だったが、ホスフィンに待ち合わせを知らせたのが遅くて、遅れてしまうとの連絡が入っている。これを見て気が抜けてゆっくり実況を1本視聴してしまった。結局午後6時半に家を出て、当然のように遅刻した。
待ち合わせ場所についても誰もいない。全員遅刻しているのか？しばらく仁王立ちでなろうを読んでいると2人が連れ立って現れる。何を食べるか決めるのにしばらく時間を使い、結局ラーメン屋に行く。
— こたつがめ (@kotatsugame_t) 2020年9月7日
辛味噌ラーメンらしい。実際、辛い。スープまで飲み干したところ胃腸の具合が少し悪くなってしまったように思う。
少し本屋に行ったが、最近新刊を買ったばかりなので、めぼしいものはない。ゲーセンに行く。
チュウニズムが空いていたので、3人でしこたまマッチングをした。待ちが出てきたのでいったん台を離れるが、よく見るととんえぼ（東北大学の音ゲーサークル）の人々なので、マッチングに入れてもらうことにする。僕以外3人は13+全鳥でかなり意味不明。ゲーセンは周りがうるさくて声が聞こえないので、よほどのことがない限り人と話すことはないのだが、4人マッチングの最中にも無言だとただのコミュニケーション能力に難がある人になってしまう。
ふとTLを確認すると、AtCoderの公式ライブラリが公開されていた。よく見るとzipファイルで配布されているので、家に帰らないと中身がわからない。また同時にpractice contestが生えていてびっくりする。コードゴルフの時間だ！
音ゲーをやっている最中なのでコードゴルフはできない。ちょっと気にかかりはするものの、とりあえず音ゲーのプレイを続行する。
とんえぼの人々が帰った後もしばらく続けていた。東方アレンジが2曲、13に追加されている。これのAJ粘着をし、無事2つともAJできた。Sweet Requiemはボルテで聞いたことがあり、かなり好きなアレンジなのでよかった。終盤に癖がついて何回か散ってしまったが、特に譜面を確認したりせず、プレイ回数でごり押した。
帰ってきてpractice contestをやる。A問題はUnion Findだが、これはAtCoder Typical Contest 001で既出（既出とは……）。なので最短コードをコピペして常勝！ｗしかしよく考えると言語を変えることで縮む。ATCの方も同じ言語で縮めておいた。
眠いので、残りはコードゴルフはせず、とりあえずACすることだけ考える。C,E,J,Lの4問を残してACできたので、寝る。続きはまた明日。
09/08(火)
エアコンを切って寝ているので、毎回暑くて起きてしまう。1回意識を取り戻すとコードゴルフの状況が気にかかってなかなか再入眠はできない。今日もまだかなり眠いはずなのだが、眠れなかったので仕方なく起きる。practice contestの続きをやる。
C問題はそもそも全然解けない。ALCのコードを読んで理解することにした。僕のライブラリにも追加しておく。
L問題は特にいうことなし。J問題はセグメント木上の二分探索をO(log N)でする方法を理解していないので取っておいたが、結局O((log N)^2)で解いた。あんまり新しいことを学ぶ気になれない……。
E問題も全然わからない。人のコードを読んでACした。縦と横の条件があるときに、両方を同列に扱おうとしてしまう。この問題では、縦から横（または横から縦）にフローを流すようにすればよかった。また、最小費用流の負辺をなくす方法もあんまり体得していない。内部のdijkstraをBellman-Fordに変えれば対応できる、というのを知って、考えがこれに引きずられている。
夕方であるが、学食に行かないことにする。practice contestの問題を全部解いたので、コードゴルフをする。
C問題はC++でライブラリを使うとほとんど縮めようがないほどシンプルなコードができる。このC++による最短コードは僕のものではないためかなり悔しい。そこで、別の言語でもっと短くならないか試すことにした。dcはTLEしてしまったが、Rubyは普通に通った。最初のACは147Bだったが、そこから37B削ることができて、無事C++の122Bを抜いて最短コードになることができた。
ライブラリの実装ではB%=Mをしているのだが、これは今回の制約では必要ない。B<Mが保証されているからだ。この条件は再帰的に呼び出すときも常に満たされる。これでB%=Mやans+=B/M*Nなどの関連する部分が一気に削れた。この更新が一番大きかった。
昨日書いていた、Rubyの入力イディオム関連の更新を探す。昨日、定数になるのでTLEするかも……と書いていたが、これは入力部だけでなくコード全体をevalすることにすれば解決できる。定数にしているのはevalの外でも同じ変数の内容にアクセスできるようにするためだが、そもそもすべてevalの中であれば問題ない、という話だ。
とりあえず現在Rubyが最短コードになっているものから探す。たしか10~15個くらいあったはず。ファイルにコードをためておいて、シェルスクリプトとonline-judge-toolsを使用して一気に提出した。
VimからRubyを呼び出すコードに更新があった。同じ変数（特にmod）やメソッド名を何度も書くとき、<CTRL-P>や<CTRL-N>による補完を利用すれば縮むらしい。Vim全然わからん。
結構適用範囲は広い。とりあえずまだ僕が最短コードを持っているものについては探して縮めておく。問題はすでに更新されてしまったものたちである。いつかと同じく、Vimでは勝てないので、Rubyのコードを縮めることで取り返す。
結局7個くらい取られて、そのうち5個はRubyコードの改善で取り返した。Rubyコードの時点で僕しかゴルフしていないようなものが多く、これは少し腰を据えて考えればポコポコ縮んでいく。
コードゴルフというのは結局競うことが最も短縮に貢献するので、1人でやっていたらそこそこの長さで止まってしまう。これはおそらく練習ではどうにもならなくて、1つのコードを縮めることに費やす時間を増やすことでしか解決されない。AtCoderには4000にも届かんとする問題があるので、1人でコードゴルフをやっているとどうしても次の問題へ次の問題へと進んでしまいがちで、こういう隙をいくらでも作ってしまう。今この瞬間はRubyでコードゴルフをしている人が僕以外にいないのでこれらの隙は表面化していないが、例えばakourryさんが少しコードゴルフをするとあっという間に驚くほど取られてしまう。
で、残り2つのうち片方は、Rubyコードの時点で僕以外にclimpetさんが参加してコードゴルフしている。当時かなり時間をかけたことを覚えており、確かに全然縮まない。これについてはどうしようもなく、取り返せないかもしれない。もう1つのコードも含め、また明日考えることにしよう。
09/09(水)
昼頃起きる。原付を買って1年目の点検のために、店にもっていく必要がある。ついでに学食によろう。
右折するときのタイミングがわからなくてかなり危険な運転をした。向かいから2台続けて左折の車が来たので、何を考えていたのかその間に飛び込んでしまったのだ。クラクションを鳴らされた。このことは僕の精神状態にかなり悪影響を与えて、ずっと思い悩んでいる。公道を走るのが怖い。
公道を走るのが怖いというのは、公道を走ってなれることでしか解消されなさそう。これはどうしようもない。僕は免許を取ってから二段階右折を2回しかしたことがないが、これはどちらも最寄りのガソリンスタンドに行くときのものだ。それ以外で二段階右折が必要な場所を通ったことがない。何故なら広い道路を走るのが怖いからだ。街へ繰り出すときにはいまだに自転車を使っており、そのため原付を買ってから1年経つのに給油をまだ2回しかしていない。
親には車の免許を取ることを考えなさいと散々言われているが、たぶん、取らない。怖すぎる。
ちなみに、学食は閉まっていた。購買は空いていたので、パンを買って食べた。
店に原付を預けて、歩いて帰ってきた。コードゴルフを始める。昨日残した2つのうち片方の短縮に成功する。もう片方はどれだけ眺めていても縮まないので、あきらめた。
Vimの補完とRubyのnumbered parameterは相性がいい。_1や_2は単語として認識されるのだ。確か最初に提案されたときは@1、@2という感じだったと記憶しているが、このままだったら補完は利かなかったことを考えると、結構奇跡的な感じがする。
それを利用して縮めたものだ。本来、numbered parameterを3回使うと、普通に書くのと同じ長さになる。|k|が削れて-3Bの代わりにkが_1になるのが3か所で+3Bといった具合だ。
ところが、補完を使うと話は変わってくる。あたかもnumbered parameterが1文字であるように書ける。それで上のコードは1B縮んだ。単語として認識されてしまう2桁以上の数値などが挟まらないよう、いくらか項の順番を変えた。
1333 pic.twitter.com/hhEY2pO1l8
— こたつがめ (@kotatsugame_t) 2020年9月9日
atgolferの更新頻度が落ちてきたので、ふと思い立ってAtCoder LibraryをPerlに移植することにした。
Perlのコーディング規約を守る気はさらさらない。とりあえず簡単そうなUFとBITを作って、SCCを作って、TwoSatを作った。
packageでくくることでオブジェクト指向みたいなことができるらしい。本来ならuseで呼び出すべきなのだが、AtCoderに提出することを考えると、当然コードの先頭にコピペである。
もうPerl歴はかれこれ4年近くであるが、これまでPerlをゴルフにしか使っていなかったので、例えばblessなど見たことも聞いたこともなかった。perldocとにらめっこして必死に勉強して書いた。
これまでgit pushするたびにユーザー名とパスワードを求められてイライラしていたのだが、これはsshで接続しておくことで解決できるらしい。かなり便利になってうれしい。
09/10(木)
昼頃起きる。電話がかかってきていて、原付の点検が終わったらしい。取りに行くが、その前に少しだけコードゴルフをする。
午後4時すぎに家を出た。ATMに寄ってatgolferを動かしているサーバ代を振り込む。もうこの時間なら学食の夜の部が始まっているだろう、久しぶりだなあ、とウキウキして行ってみると、夏季休業期間ということで学食は昼しかやっていなかった。かなりショック、というかお腹がとても空いていてヤバイ。カップ麺の自販機は止まっている。仕方なくアイスを買って食べた。
店に行く。マスクを着けていないので店内で声を発するのがためらわれる。支払いの時に、ATMでお金をおろし忘れたことに気付いたが、持ち合わせで足りた。危ないところだった。
原付に乗って帰る。仙台城前の道路の交通ルールが謎すぎる。よくわかっていないのでよくわかっていないまま書くが、僕が途中道路で止まって相手が横切るのを待っていたつもりだった車列は、少し先の停止線から伸びていただけで、僕の正解としては向こうがわざわざ開けてくれた車間を通って進むべきだった。結局僕の後ろの車が僕を追い越していって、それで気づくことができたが、この経験もまた僕の公道に対する恐怖をいや増した。
Perlでz_algorithmを実装する。ALCの実装をそのまま写経するよりも、すぬけさんのブログの実装のほうが速かった。よくわからない。
SA-ISも実装した。これは気合い。ALCの実装をそのまま写経した。関数内関数の仕様、特に中から呼び出し元のmy変数を見たときにどうなるか、がよくわからなかったので、とりあえず全部引数で渡し、そのあと、渡さなくても動くことを確認した。
本家の実装では、induce関数は外のsa配列を直接書き換えているが、どうやらこれはPerlだと遅いようだ。毎回中でsa配列を作ったあと、そのまま返したほうが速かった。
そんな感じで、いろんな書き方を試して、より速いほうを選択した結果、最初の実装から700msくらい速くなった。
ModIntを書こうとして、演算子オーバーロードを勉強する。とりあえず書いてみるとめちゃくちゃエラーが出る。寝る。
09/11(金)
起きてModIntを書く。定数をオーバーロードするのはちょっとどうしようもないのであきらめる。それと、2項演算の片方のオペランドがModIntのオブジェクトか通常のオブジェクトかによって処理を変える必要があるらしいので、これを何とかする。すると、見事に動いた。
ただ明らかに遅い。適当に探してきた問題に提出したら当然のようにTLEした。さらに簡単な問題を探して、一応ACできることを確認したが、実装した演算子の半分も使っていない。
convolutionを書く。ModIntなんて経由してたらTLEするのは目に見えているので、直接modをとることにする。
必死に書き上げたがTLE。関数を展開したり、bsf関数にlogかけていたのを全部前計算しておいたりしたが、もう全然TLEが取れない。大きな入力のケースはずっと5500msに張り付いたままで、これはつまり実行が常に打ち切られるほど遅いということだ。唯一4000ms台で通るようになったケースが存在して、これの実行時間を見ると1000ms以上の高速化に成功しているはずなのだが……。
Perlの定数について。constantプラグマで書くのが一番単純だが、引数を取らない関数を書いてインライン展開を期待することもできるらしい。
sub MOD(){998244353}と書くと、これはプロトタイプ()を持っているのでインライン展開される可能性がある。実際、解釈すればただの定数であるので、MOD()みたいな呼び出しはインライン展開される。
プロトタイプ宣言から引数を取らないことがわかるので、MOD+2などと書いてもMOD()+2であると解釈してくれる。結局、use constant MOD=>998244353と書くのと変わらない使用感が達成できる。さらに言えば、この関数が返す値を何か適当な変数にすれば、実行時modにも即座に対応できるというオマケ付きだ（この場合は当然インライン展開されない）。
インライン展開されているかどうかをチェックする方法も面白かった。関数を再定義すると警告が出るのだが、このメッセージがインライン展開される関数とされない関数で異なるのだ。
perlsub - Perl のサブルーチン - perldoc.jp
結局TLEは全然取れないままだが、とりあえず動くことは動くので、convolutionも書けたことにする。
yukicoderに出た。Dを解くのが結構速かったと思う。蟻本に載ってるものそのままだと思っていたけど、蟻本をよく読むと微妙に違う。セグメント木を抽象化しているので、少しいじる必要がある。
さて、Perlで実装するのがヤバそうなものしか残っていない。というか何を書いても実行時間との戦いになってしまう。微妙に嫌気がさした。FFの方がRubyに移植するリポジトリを立てているので、ここで何か書こう。
とりあえずSA-ISを書いた。Rubyもまたゴルフにしか使っていないので、クラスなどは全然わからない。SA-ISは関数をいくつか定義して後はゴリゴリ書くだけなので、設計としては比較的ラクチン。
内部実装はよいのだが、ラッパーの実装に困った。Rubyは標準ではオーバーロードを提供していないので、文字列と数値の配列で呼び出す関数を分けられないのだ。最初は関数名を変えていたが、結局1つにまとめて、引数の型をチェックして処理を分けることにした。
文字列を文字コードの配列にするのは、順当にいけばs.chars.map(&:ord)が思い浮かぶが、s.bytesにした。競プロで使う分にはこれで十分だろう。試してみたところ、s.bytesのほうが速い。これは直観と合う。
テストも書いて、さあプルリクエストだ！と送ったところで、masterのままだったことに気づいた。本当はこのまま別ブランチでconvolutionを書くつもりだったが、フォーク元のmasterブランチを再度引っ張ってくる方法がよくわからない。こういうやらかしをしたとき、全部破壊してもう一度やり直すこともできるだろうが、すでにプルリクエストを送ってしまったことだし、とりあえずマージされるのを待つことにする。
09/12(土)
起きたらWUPCが始まっていた。もう残り2時間ちょっとしかないんだが？あと寝ている間に地震があったらしい。ちょっとだけ覚えていないこともない。
とるものもとりあえず、登録して問題を解く。昨日の情報によれば最初2問以外は難易度順ではないらしいが、すでに開始3時間が経過していることもあり、solved数を見れば何から手を付ければよいか一目瞭然である。
solved数が大きいものを解いていく。ABCFGMJを順に解いて、このあたりから詰まってくる。Eはごちゃごちゃやってたら解けた。Iは実験したら解けた。この時点で残り30分くらいで、次にsolved数が多いのはD問題だったので、これを見る。mod Nとmod N+1が混ざってややこしい。焦っている。BSGSが必要だと思い込んで、そこであきらめてしまったのだが、解説を読むと拡張ユークリッドの互除法でいいらしい。式変形を正しく行えていれば、指数同士の等号になるようだ。僕はこれの片方が指数にならないと思ってBSGSを考えていた。拡張ユークリッドの互除法は持っているので、ささっと書いてupsolveしておいた。
Rubyでconvolutionを書き始める。実装方針にかなり悩んだ。modの値をどう扱うか、できれば定数変数に代入したいのだが、汎用性と両立できない。
こどふぉがあったので、出た。div.2だ。5位だった。やったぜ。
マインスイーパーの上級の世界記録が更新されたらしい。
ついにkamil氏が破られるときが来たか...しかし20秒台という数字は見慣れなすぎて現実味があまりないな pic.twitter.com/YTs1LMDg7z
— よわぽん＠ぐんにょり (@sweeper_yowapon) 2020年9月12日
12歳！？そうはならんやろ。
Rubyのconvolutionを書いた。見事にTLEした。解消する過程でいろいろやってみたのだが、定数変数に代入するのとメンバ変数（普通の変数）に代入するのは速度的にほとんど変わりがなかった。全部の個所に数値を直接書いたら速くなった。こんな実装をするわけにはいかない。
結局、数値を直接書くのと、クラス定義を外すのをやって何回か提出したら無事ACが取れた。ライブラリとしては、これらの改善はできないため、そのまま貼るとTLEするなんとも残念なコードが出来上がった。
設計にはちょっとばかし自信がある。まずクラスのインスタンスを作るのだが、初期化する際に計算に使用するmodを渡す。それで、作成したインスタンスのメンバ関数としてconvolutionを呼び出し、畳み込みを計算するのだ。
raise ArgumentErrorを入れようと、条件を精査していたら、どうにもAtCoderの実装とドキュメントにある制約が合わない。試しにmodを小さな値にして制約ギリギリ（かつ高速化のためのナイーブな計算が適用されない大きさ）の配列を畳み込んでみると、答えが異なってしまう。僕が以前から持っていたNTTライブラリは正しい答えを計算できるので、これは実装がバグっていると分かった。issueを立てた。
英語わからん。
そのあとz_algorithmを実装した。RubyにおいてもPerlと同様、すぬけさんのブログを参考にした実装のほうが高速だった。
布団に入ってから、かねてより読み進めていたなろうを読み切った。ハーメルンにおいて累計の最高評価を誇る作品なので、1度読んでみたいと思っていたものだ。このすばはほとんど知らないし、Elonaに至っては名前すら聞いたことがなかったのだが、十二分に楽しめた。非常に面白かった。
09/13(日)
起きる。寝ている間に昨日立てたissueが解決されていた。
今日はABCだ。全完したがFでペナルティを5億回出した。
A問題の最短コードは1Byteになる。気づくのが遅すぎたため時間差で負け。
D問題はRubyでO(S^2)を書いて満足していたのだが、O(S)解法があるらしい。dcで超短い回答が提出されているのを見て腰を抜かした。
すかさず縮めにかかる。何とか他の人にとられる前に縮めることができた。早い者勝ちという感じがある……と思っていたら、そのあとさらに-2Bすることに成功した。危ない、途中で満足していたら刺されるところだった。
Rubyで実装されていないACLのアルゴリズムも少なくなってきて、ヤバいものしか残っていない。今日はあまりやる気がないので、ラノベを読んだ。
「西野 ～学内カースト最下位にして異能世界最強の少年～」というシリーズだ。結構前に4巻まで読んで止まっていた。今日は5,6巻を読んだ。登場人物はかなり特徴的なので覚えているのだが、前の巻の出来事をきれいさっぱり忘れてしまっていて困った。
4巻で止まってしまったのは、そのときは主人公の扱いのあまりのひどさに辟易してしまったからだった。今はまた面白いと思って読んでいる。9巻まで出ていて、ちゃんと全部買ってあるので、今度は一気に読み切りたい。なんだか自分の中で評価が定まっていないので、またいつ放り出すかわからない。
まあ面白くてもタイミングを逃してなんとなく途中で放り出してしまった作品なんていくらでもあるんですが。SAOとロクでなしをちゃんと読み進めたい。
z_algorithmの速度計測についてだが、実はPerlもRubyもACLの実装を完全に再現していない。特にRubyにおいて配列のある位置の値の参照を得る方法がわからなかったのだが、毎回indexingするのではなくちゃんと変数に取り出したら改善するのだろうか。そう思って書き直してみたが、やっぱりちょっと遅かった。
