08/03(月)
午後6時に起きてatgolferをチェックする。いくつか取られている。今日は1つも取り返せなかった。しかし、それとは無関係に更新されていたコードには結構縮む余地があって、ぽんぽんと取っていく。結局プラスマイナスゼロくらいだが、それは勝てないから別の問題をやっているだけで、コードゴルフ力とは関係がない。
明日提出のレポートをやる。この講義は2回のレポート以外課題が出ておらず、レポート問題は講義スライドの途中に挟まれるのだが、最後3回分くらいは問題がないので読まずともレポートが書けてしまう。いずれ苦しむのは自分であるとわかってはいるが、講義内容をまともに理解しようとせず、とりあえずレポートだけ解こうとしてしまう。
今回提出ぶんはたった3問なので、かなり悩んでいたが数時間もあれば終わる。1問は連続と1階微分可能を取り違えていて、絶対値関数で壊れているように見えてしまい困っていた。もう1問は、以前提出したレポート問題の結果が適用できそうな形をしていたので、やってみたら求める式が出ず困ってしまったが、結局途中の議論をそのまま応用すればすんなり解けてしまうことに気づいた。無理に結果を応用する必要はなかった。
そのあとコードゴルフをした。6時間くらい。ABC126以降はほとんど見ていないのだが、驚くほど更新できるコードがあるみたい。ヤバい。
今日も1つ取り上げる。取られたやつなのだが、かなり頭が良い。
普通だったら引き算した値のペア3つを比較しなければならないのだが、それはさすがに面倒すぎる。そこで、a,b,cをa+b-2cにして、これが3つ等しいかどうか試しても正しい答えが出ることを実際に提出することで確認したため、それを実装する。3つ等しいことを比較するのも面倒なので、さらにもう一度a,b,cをa+b-2cにして、これが0に等しいことを確認すればよい（これも実際に提出して確認する必要があるが）。
僕の元最短コードは、これをa+b=2cで判定していた。引き算するよりはそのまま=で判定したほうが短いと思ったからだ。しかし、考えてみればこのa,b,cをa+b-2cにする変換は全部同じことをやっている。というわけで、その変換を行うマクロを（以前は3回しか実行していなかったが）4回実行すればよい。
さらにマクロを定数回実行するときの書き方も最近新手が出て、マクロの外で何回もxを実行するのではなく、あらかじめその個数dしておいて、マクロの初っ端でxすれば短いことが分かった。マクロの外で何回もxを書くときは、いつもマクロをスタックの上に持ってくるrやRが必須だったのだが、この書き方ではそんな必要はない。
相も変わらず生活習慣が崩壊しているわけだが、どうやらチュウニズム クリスタルプラスの最初のイベントは今週の水曜日までらしい。そこまでに1度ゲームセンターに行っておきたいが……。チュウニズムを始めてからこれまで、イベントは宝物庫マップと今年の3月コロナで行けなかったやつ以外全部完走していたと思うが、今回は完走できなさそうだ。あと、チュウニズムクリスタルの最終epをまだ1つもやっていない。譜面動画を見て机をべしべし叩いているだけでは何にもならず、解禁しないとお話にならない。
あと本屋にも全然行けていない。通販では、すでに追っているシリーズの続刊を確認することに終始して、新しいシリーズを見つけにくい。つまるところ、どうにかして月2回くらい外出しなければ生活に支障が出てしまう。でもコードゴルフ辞められないんだけど！！！
08/04(火)
起きたらJOIの問題がいくつか縮められていた。JOIは入力定数個がやたら多い。そこに使われていたテクは昨日上に書いたばっかりのやつなので、やはり時間をかけてたくさんの問題に目を通さないと、あたら最短コードを奪われてしまうばかり。ということで今日はコードゴルフの日にする。
途中学食に行ったりもしたが、結局昼過ぎに起きてから朝方までずっとコードゴルフをしていた。今日の日記として書くべきことは何もない。
精度の変数をレジスタ代わりに使うテクは以前から何度も使っているが、出力の基数をレジスタに使うことはこれまであまり意識していなかったように思う。それ関係で縮むものを探そうと、dcの提出が存在するすべての問題に目を通すやつをした。いくつか見つかってうれしい。出力基数は2以上である必要があるが、たとえ制約に「1以上」とあって1が存在する可能性があったとしても、実際テストケースにそういうものが入っているかは提出してみなければわからない……。このことは前にも書いた気がする。
今日は最初の2時間でJOIをざっと見て、その次に8時間くらいかけてABC126~ABC148を確認した後、残り3時間は上の確認作業、つまり縮みそうなやつを見つけては問題ページを開き、適当にコードを書き換え、提出してWAになるかACするか確認する、ということを延々繰り返していた。時間はatgolferのツイートを元に算出した。
ちなみに、出力するものが例えばYES/NOの文字列だったりすると、最後にAoで基数を元に戻す必要がなくなる。これもいくつか適用できる問題があって、縮んだ。
こんなところか。今日は特に面白いコードを書いていないように思う。明日こそはゲームセンターに行きたいので、朝日が完全に顔を出す前に寝る。
08/05(水)
突然だが、この部分は木曜日の日記と一緒に書いている。3週間目に突入したところでサボるとは、三日坊主ならぬ三週間坊主といったところか。ガハハ！
昼過ぎに起きて、課題をやった。最終回だ。実際は他にも任意提出の課題が毎週出ていて、これは期限がまだ先。これまで毎回出してきているので、せっかくだし全部出したいところだ。もう単位を得ていることは確定なんだけれど、こういうところで手を抜けないのも大学生活に不慣れという感じ。
bashのgrepコマンドは、1つも見つからないと終了コードが非0になるので、そのままだとREを吐いてしまう。以前までは;:として:の終了コードを参照させることで回避していた。+2Bだ。
dcではシェルコマンドが+1Bで呼び出せるが、（当然）REは引き継がないらしい。ということでこれになる：
う～ん、なるほど。ちなみに最初、提出言語がdcになっているのに気づかず、必死にman !を叩いたりbash エクスクラメーションマークなどで検索したりしていた。
風呂に入りながら、競プロにおけるF_2線形代数について思いを馳せていると、有名問題「鯛焼き」のコードを更新できる可能性があることに気づく。実際に書いてみたところ、縮んだ。
行列式 mod 2を求めたいが、modの線型性から、最初からF_2上で行列式を求めることにしてもよい。で、F_2上で行列式が0か否かというのは、つまりF_2上で行列の各行（または各列）のベクトルが線型従属か否かということだ。つまり基底を求めることにしてもよくて、熨斗袋さんのツイートで有名になった基底の取り方をすると、かなり短く書ける。
ゲームセンターに行く。チュウニズムをする。チュウニズム運営は最近チュウニズムデュエルというのを始めた。これはアップデートごとにキャラクターとHPが用意され、1プレイごとに出したスコアに応じたダメージを与えて、累積ダメージによって撃破に成功するとアイテムがもらえるというものだ。
1プレイで与えることができるダメージと相手のHPについては、運営も調整に苦労したようで、例えば初回なんかは全体的に100分の1の値だったような気がする。スケーリング変えると何かいいことがあるのかな。
で、これがまあ撃破にかなり時間がかかる。3段階あって、この日は30クレくらいプレイしたが最後の段階の3分の2くらいで終了した。全体で与えたダメージを見ると、3段階すべての撃破に必要なダメージのおよそ半分といったところか。数値はかなり適当だ。何が言いたいかというと、さすがに1日で撃破するのは無謀だったということ。開凸すればまた話は変わるが……。
神威（NAOKI × ZPP MIX）という曲に粘着した。ノーツ数が2777でBPMも210あり、また高速トリルやらフリック連やらでかなり疲れる曲だ。初見プレイ時はあまりできる気がしなかったのだが、案外ごまかせることに気づいて、鳥寸を2回踏んだが最終的には無事SSS達成した。1時間くらいやっていたので、20連奏くらいか？13+の粘着としては多くもないが、チュウニズム自体久々のプレイということもあってか結構つらかった。この曲はアプデで定数が下がったらしい。まあ13.9といえば本家神威と同じなので、さすがにそれはないかな……。
帰ってきたら疲れ果ててあまり動けなかった。なので日記も書けなかった。
08/06(木)
GCJ Tシャツの再配達で起きる。自分で時間を設定しておいて寝過ごしそうになった。ヤバいわよ！
サークルの定例会をMeetでホストする。一応今回で前期の活動は終わりということにした。
幾何学の演習の課題をやる。これで今期の幾何学系は終わり。つらかった……。問題についてだが、先週友人にいろいろ話を聞いたのがかなり役に立った。ありがたい。自分で本を読んだりして勉強することがないし、講義スライドも最後のほうはまともに読もうとしていないため、少しひねられると手も足も出なくなりがち。あと、構築問題だったのだが、これは純粋に難しい。感覚として理解（こういう言い方は批判もあるだろうが）していなければ何もわからないことが多い。
今日はあんまり記憶がない。演習の課題は22時に終わったはずなのだが、そこから数時間くらい何をやっていたのか本当に覚えていない。ここまで書いたところで、そういえばYouTubeでゆっくり実況を見ていたことを思い出した。改めて考えてみるとめちゃくちゃ時間溶けるな……。強く自制したい。
今日のゴルフはかなり取られた。特に、Vimで入力を少し加工してシェルに流し、最後にもう一度加工する……みたいなやつが強いらしい。Vimは算術演算がやりにくいのが少し難点なのだが、そこをbcに任せたりする、あとreverseはrevというコマンドがあるし、しまいには空白を改行に置換するのをdcのfコマンドに任せたりする。といっても、空白区切りの数値を改行区切りにするのにdcを使うのは、bashでも使うが。
なるほどな～という気持ち。2行目でf<Space>して移動し、r*するのだが、この後そのカーソル位置を利用する。具体的には、カーソルを上に1つ移動させてf-し、r+する。これは、2つ目の数値に負号がついていればそれを+に置換し、なければf-での移動が発生しないため、カーソルを上に1つ移動させたときのまま、直下の空白が+になる。上手いな～～～。
そのあと、この2行をbcに流して計算し、値をVimのほうでソートする。
ちなみに、制約以外全く同じ問題が存在して、そちらもきちんとほとんど同時に更新されていた。完敗。Vimで何が縮むかというのはもう全然わからない。
そういえば、生協に注文した本を取りに行けていない。まずい。この日記を書いている間に、もう完全に朝になってしまった。金曜日も行けないまま終わってしまうのか……。
08/07(金)
実は金曜日は寝落ちしたのでこの部分を書いているのは土曜日。またか……もうガバガバじゃないか。あきれたなあ。結局生協には行けていない。
課題をやる。金曜日の演習は、これまで何度か言及してきたが、サボって半分も出せていない。前は半分出してるとか言ってたが、あれ以来一回も出せていないので。
これはさすがにまずいということで、どれだけ解けばよいか集計して、放り出していた。過去の課題も含めてすべての期限が、今日の日付が変わる直前ということだ。やらねばならない。
で、頑張って書いた。起きたのがすでに午後7時くらいで、そこから午後11時くらいまでやって、かなり適当だけど3回分弱のレポートを錬成した。実は1つは仕上げを残すのみだったので、作業量は2回分くらい。計算したところこれを含めると全体の6割強の評点が入っているはずだ。7割あれば安心だと思っていたんだけど、もうやる気がみじんもないのでここですっぱりあきらめることにして、まとめてレポートを提出した。
今日のゴルフだが、Vimで空白区切りの単語を改行区切りに直す方法に新手が出た。
幅2のウィンドウを開いた後、行全体を整形（gw）している。Vimのドキュメントでgwを見てみると、整形には3種類くらい方法があるらしいが、おそらくオプション'textwidth'による各行の長さの制御だろう。実際、:set tw=2したあとgwjしても同じ効果が得られた。行の幅を超える単語は、無理やり折り返されるなんてことはないのか。
このあたりのページを見ると動作が分かった。多分この解釈で間違いないだろう。それにしても、垂直分割によって暗黙的に'textwidth'を設定するとは……探したけどそういう言及は見つからなかった。こういうテクは人のコードを見て覚えるしかない。
夜、適当にコードゴルフをしていて、少し集中がきれたのでベッドに倒れこんだらそのまま寝てしまった。
08/08(土)
午前6時くらいに目を覚ます。今日は生協行けそうだな、と思ったら土日なので購買・書籍店がやっていない。クソッ、やられた……。
眠るのに失敗し続けた挙句、なろうを1つ一気読みしてしまった。
https://ncode.syosetu.com/n0262cw/
多分8時間くらい消し飛ばした。自分のリソースを使うのが下手くそ。
今日は何もないのでコードゴルフをやる。明日AGCなのでかなり緊張するが、精進する気にはなれない。あなたが精進している間にライバルはコードゴルフをしています！！！
ある値xが正・0・負のどれであるかに応じて3つの文字列を出力する場合分けをする、という問題はかなり数がある。これに関しては今のところ、最初に3つ文字列を積んでおいて、
2 x ^1+として1、2、それ以上に分け、Rする（ただしxの絶対値が小さくなければ使えない）
1 x vd/として文字列の上に1~3個の数値を積み、4Rでその下から文字列を持ってくる
の2つのやり方が最短だった。ただしここでxはxの値を積むことを表す。
これは、x 3*Rでよい。xがあまりに大きすぎる場合はこのままでは使えないが、2 x ^とは違って7e8くらいの数なら動く。原理を説明しよう。
まず、x==0のとき。この場合Rは何もしないので、もともと一番上にあった、最後に積んだ文字列が上に来る。
次にx>0のとき、3x>=3であるから、これでRするとスタックの上から3番目、つまり一番下にある、最初に積んだ文字列が来る。なぜなら3より深いところはないからだ。（ないようにしなければならない。）わざわざ3倍するのは、主にこのためだ。
最後にx<0のとき、3x<-2だ。負の数でRすると、逆に一番上の文字列がその下に飛ばされる。-1で飛ばすと元通りになってしまうのだが、これも3倍しているのが効いて、ちゃんと深いところに飛ばされる。結果、2番目に積んだ文字列が一番上に来る。
これで3通りの場合に対処できていることが分かった。テストケースによっては、わざわざ3倍して対応しなければならない3つのケース、つまりx==1とx==2とx==-1という微妙なケースがないこともあって、その場合は単にx Rとするだけで通ってしまったりもする。
この更新はデカい。xがちょっとくらい大きな数値なら、x 9*vRとかすれば動いてくれる。これはx<0の場合の原理が違う。負の数をvすると消し飛んで、文字列でRするとそれも消し飛ぶので、結局2番目の文字列が露出するという原理。
ただこれでは対応できないものもあって、上に貼ったリンクの2つ目のやつは制約が1e100とかいうバカげたことになっているので、ダメだった。
寝ようとしていたところ、atgolferに奪取されたツイートが流れてきて一気に目が冴えてしまった。困るが……。
08/09(日)
起きたら午後6時だった。早速緊張し始める。洗濯機を回したり洗濯物を干したり部屋の換気をしたりしてコンテスト開始を待つ。腹を壊して2回もトイレに行ってしまった。
コンテスト直前は緊張で心拍数が120回/分を超えていたと思う。ほんの数秒程度しか図らなかったが、1秒数える間に2回ちょっと鼓動していた。ABCはほとんど毎週あるけど、ABC ratedの人は毎週末このような緊張にさらされるのだろうか？それともコンテスト回数の多さを考えると少し気が楽になったりするのだろうか？黄色直前でコンテスト前の緊張やなんやかんやにやられて救急車のお世話になった人というのはtwitterで数人観測するけど、納得だなあという感じ。
AGC047はABCEの4完で27位だった。銀パフォを出して2600を軽々と超えていった。コンテスト中の動きを記録しておこうと思う。
A問題
コンテスト開始と同時にA問題を開いた。まず、サンプルを適当に眺めて、小数部が0であるような数のペアじゃないと整数にならないのではないかと考えるが、これは大嘘。5/4*4/5=1.25*0.8=1とか考えると当たり前。
とりあえず入力を有理数にパースしたくなるので、gcd関数を書いて分母分子を約分する。ここで手が止まる。少し冷静になると、分母の素因数は2か5しかない。有限小数だからだ。で、足りない2と5を相方の分子から持ってきたい。このあたりで約分しなくてもよさそうだと感じ、gcd関数を消す。
つまり、問題は次のようになる：「掛け算した後分子が持つ2と5の素因数の個数を数え、小さいほうがlog_10 分母以上であるようなペアを数える。」
このままではペアの条件が分離できていないが、事前にlog_10 分母をそれぞれの素因数の個数から引いておけば、2と5の個数が両方足して0以上になるということになって、分離できる。小さいほうが〇〇以上というのは、両方が〇〇以上であるというのと同じだ。
ここまでくればただの典型だが、まだ少し手間取った。最終的には片方でソートしてもう片方を配列にカウントする方法で解いた。出てくる数値がlogになって小さいので、累積和を使わなくとも毎回数えてよい。A問題は12分かかった。
B問題
いったん順位表を確認すると70位くらい。BとCにACが出ている。A問題はかなり難しいと思ったので、これだけ手間取っていてもまあまあ速い。B問題を開く。またペアを数え上げるのか……。
操作という単語を見て、一瞬正規形に直すことを考えるが、この問題の操作はペアの片方にしかできず、文字列を短くすることしかできないので、この方針は一瞬で棄却できる。
先頭から見ていって、ある文字を残そうとすると、そこから後ろで捨てられるのは連続した区間のみ。ここから僕はちょっと遠回りして、文字列を逆から見て貪欲に残すことにするのが最適であることを示した後、結局文字列の長さ-1の接尾辞が一致していないとダメであることに気づいた。
とりあえず文字列をreverseしたあと、接頭辞（reverseしたので）が共通の文字列たちであって、残りの文字列中にある文字を含むものを高速にカウントできればよさそう。これはSA……じゃだめだけどtrie木が使えそうだが、できるか？→できる。
実際に、trie木のノードに長さ26の配列を持って、それぞれ部分木で特定の文字を含むものの個数をカウントすればよい。trie木に文字列を入れるときに、定数倍が26かかる線形時間でできる。
trie木に不慣れなのもあって少し実装に手間取るが、通る。考察自体は何というか、手ごたえがない。14分かかったらしい。
C問題
また順位表を確認すると、36位くらい。いいんじゃないの？C問題を開く。またペアを数え上げるのか……。
難しい。しばらく悩む。数列A自体を処理するのではなく、出現回数を数えたcntAを処理してみてはどうだろう？これは添え字がi*j mod Pの畳み込みになる。とりあえず「競プロ 畳み込み」で検索すると、以下のブログに突き当たる：
競技プログラミングにおける畳み込み問題まとめ（FFT,アダマール変換,メビウス変換,ゼータ変換） - はまやんはまやんはまやん
まったく同じものがPDFで解説されているように見える。実際に見に行くと今まさに求めているものだった。初めて書くので、しばらく紙の上で実装の構想を練る。ちなみにP=200003の原始根を求めようとプログラムを書いたら2が出てきてびっくりした。なんとなく3以上のイメージがあった。
頑張って書く。modがNTT-friendlyではないので、FFTを使う必要がある。僕のライブラリにはFFTもNTTもあるが、かなり遅いことが経験的にわかっている。なのでうしさんのライブラリから窃盗することも考えたが、他人のライブラリを使うのは難しいことが予想されるので、とりあえず僕のFFTを貼っておいて、TLが厳しそうだったら書き換えることにする。
微妙にintのオーバーフローでバグったりしつつ、サンプルが合う。すごく小さいサンプルなのに手元で結構かかる……と思っていたら、畳み込む数列の長さはP-1で固定だった。AtCoderのコードテストで走らせると700msくらいだったので、僕のFFTのまま提出。通った！21分かかっている。
E問題
順位表を見たら、あと少しで1ページ目の位置にいた。これはすごいぞ！
さて、次にD問題に行こうかE問題の部分点に行こうか迷う。順位表を確認すると、やむなくさんがE問題の部分点を解いている。さらにE問題を見ると、いかにも興味を惹かれる問題文をしている。決めた！E問題に行こう。
とりあえず部分点を考える。条件に応じて0かxを代入する処理が書ければよさそう。
まず、1を作らなければならない。これはA+B>0とした。A+B=0、つまりA=B=0のとき、いかなる操作によっても0以外の数値が出現しないため、何をしてもよい。これは面白い。
次に、論理積を取る方法を思いついた。x+y>1でよい。これを使えば、定数回のループ中でcond && dist<xをdistに足すことで、condに応じた代入が可能になる。
部分点では10回のループを回せばよい。まず外側のループでcond = i<Bとしつつ、これを使ってAを足したり足さなかったりするとよい。
念には念を入れることにして、チェッカーを書くと、通る。提出して部分点を得る。32分かかったらしい。順位表を見ると2ページ目最上段にいる。
難解プログラミング言語っぽさを感じるので、何とか満点をとれないかと思い、Dに行かずこれを考えることに決める。
制約が一気に大きくなった。2べきに分解するのだろうとあたりをつける。先ほどの「条件に応じて0かxを代入する」処理では毎回1しか足していないが、ここを2べきでできればよい。
しばらくうんうん考えると、cond && dist<xをN回2倍すればよいことに気づく。細かいことを言えば、dist<xの部分を判定するために、まず2べきを足してみて比較しないといけないが、大枠はこれでよい。ステップ数の計算をせず、とりあえず書いてみることにする。Bのループも同様に2べきで分解し、A*2^iを足したり足さなかったりする。
書いて、チェッカーに通してみると、なんと用意した全てのケースに正当する。ステップ数のチェックも入れているので（124532ステップだった）、つまりこの出力は問題の条件に合致するということ！喜び勇んで提出し、AC！！！
部分点を取ってから23分、E問題には55分かかったらしい。順位表を見ると9位！素晴らしい。
その後
順位表の1ページ目に載ってみたいが……。D問題を開いたけれどうまく集中できない。結局順位表を数分おきに確認したり、atgolferで最短コードが取られているのを発見して打ちひしがれていたりするうちに、順位表の1ページ目から転がり落ちてしまった。悲しい。さらに順位は落ち続けて、最終的に27位だった。
今日のコンテストはかなり調子が良かった。もう何週間もコードゴルフしかしていないのでちょっと心配だったが、問題との相性が良かったのだろうか？
コンテスト後はコードゴルフをやっていたはずなのだが、全然進まなかった。ちょっと気持ちがふわふわしている。 今週末は全然レポートを書いていないが、来週期限のものが複数個存在する。何とかしなければならない。
