週記（2021/06/21-2021/06/27）

06/21(月)

午前7時、目を覚ます。日曜日は布団から出ずに寝るのと起きるのを繰り返していたため、時間の感覚があまりない。まあ朝だし、このあたりで日付を区切っておくのがよいだろう。生活リズムが整っているように見えなくもない。起き抜けにTLを見ていると、今日が夏至であることに気づく。夏至は好きだ。

しばらくなろうを読んでから、投稿された典型90問を確認した。今日も特にゴルフする気にはならない問題。HW\le 16なので、まあなんでもできそうな気はする。とりあえず通るマスとして2^{HW}通り全列挙して、同じマスに二度入らないように一回りする閉路（ハミルトン閉路）が存在するか確認する、という方針を考えた。オイラー路と勘違いし、次数を確認すればよいと思い込んでいたが、思い直して調べ、間違いに気づいた。ちゃんと冷静になると、bitDPでできる。

解けたのでまたなろうに戻る。そのまま午後2時までなろうを読んでいた。途中で典型90問がAtCoderのほうに投稿されたことにも気づいていたが、放置して読み続けていた。

布団から出て先週の週記を完成させ、投稿する。金曜日の終わりあたりから溜めていたので、2日ちょっと分を2時間くらいかけて書いた。日曜日はほとんど虚無だったので、実質1日分かもしれない。投稿してから典型90問も通しておいた。

先週金曜日に注文した眼鏡だが、今日の午後3時以降なら受け取れる、ということを金曜日の時点で言われていた。先週の週記には下のように書いたが、実際はピッタリ月曜日に出来上がるということ。

出来上がるのは月曜日以降になるらしい。

週記（2021/06/14-2021/06/20） - kotatsugameの日記

大学に行く準備をする。眼鏡屋と購買が午後5時閉店で、学食が午後5時から開店なので、そのちょうど境目を狙って行くことで待ち時間なく買い物をしたり食事したりしたい。シャワーなど浴びていたら午後4時半で結構いい時間になった。ATMに寄って眼鏡の代金を下ろしたらギリギリになってしまったが、何とか購買で買い物をすることに成功。眼鏡屋のほうは、調整などしてもらっていたら午後5時を余裕で回ってしまい申し訳ない。食事して帰宅。

DDCC2021本戦の動画が公開された。インタビューを受けたことを覚えていて、30人しかいないのだから使われている可能性は高いぞ、と思ってドキドキしながら視聴したが、使われていないどころか映り込んでいる瞬間すらほとんどなくて拍子抜けした。感染症対策のビニールで人がよく判別できない。

https://www.discoverychannel.jp/campaign/ddcc2021/

布団に倒れこんでなろうを読んでいたらすぐ寝落ちしてしまった。午後7時半から午後11時半まで寝ていた。起きてからまた午前5時までなろうを読み続け、再度寝落ち。

毎週午前3時にClassroomに講義資料を投稿する教員がいて、親近感を感じている。

06/22(火)

午前11時起床。典型90問を確認。今日はただの木DPで、またゴルフする気は起きない。午後5時までなろうを読み続け、また寝落ち。次、午後8時半に起きた。夢を見た。

布団から出てサークルの運営関連の作業を少しした後、典型90問を通しておこうと思ってページを開いてみたが、問題がAtCoderに投稿されていない。スーパーリロードしても変わらず。順位表で現在の最高点を確認し、ようやくまだ投稿されていないことに確信が持てた。なろうを読んだり、いろんな人の週記を読んだりしていたところ、午後10時前になってようやく投稿されたので、通した。

またなろうに戻る。午後10時、ついに最新話に追いついた。

https://ncode.syosetu.com/n5534co/

布団に入ってから新しいなろうに手を出した。

週記（2021/05/24-2021/05/30） - kotatsugameの日記

記録によれば、05/24から読んでいたらしい。今日でちょうど30日。この作品は文字数が1277万文字ということで、1日あたりでは42.5万文字くらい読んでいたということになる。特に設定が好みで非常に楽しめたが、その代わり今月の物理本の読書記録は壊滅的である。ここにこの作品の感想を書こうと思ったが、久しぶりということもあり、また長く読み続けすぎたこともあって、何を書いていいかわからなくなった。

あらすじにもある通り、主人公は一度転移して異世界で勇者になり、3年後に再度、今度は通っている学園丸ごと同じ異世界に転移する。異世界ではその間におよそ300年が経過しており、勇者その人や当時一緒に戦った仲間たちはすでに伝説となっていた。主人公はその300年後の世界で、学園生としての立場と異世界の勇者としての立場を行き来しつつ活躍していく……。1回目と2回目の転移の間でかなり時間経過があったという設定は「神話伝説の英雄の異世界譚」を思い出す。こちらも主人公のチート具合が好ましい、が、今は置いておこう。

主人公はいち学園生であったわけだが、さすがに勇者なので、立場を隠している状態でも戦闘力については序盤から学園で最強だった。と、ここで、「勇者であったことを隠している」という設定がまず健康に良い。隠しきるわけではなくて、自分から明かしたり、あるいは見破られたりするわけだが、そのような「自分の立場を明かす」という一種のカタルシスが手を変え品を変え何度も訪れるのが良かった。さて、主人公が学園最強であるという話だったが、これを恃まれて、ある事件をきっかけに学園生出身の冒険者を統率する立場に抜擢される。「冒険部」という部活動を作り、メンバーを統率して教育し、組織づくりを行っていく。この「組織作り」や「組織のトップに立つ」というのも好みの要素だった。

あとはまあ、主人公最強モノであるので、これも好み。大まかにはこれくらいの要素が僕の好みのどストライクだったというわけだ。

来週また僕が発表することになった。今週は不甲斐ない感じだったので、来週は頑張りたい。

週記（2021/06/14-2021/06/20） - kotatsugameの日記

日付が変わったあたりからゼミの発表準備を始める。午前6時までやったが、予定している発表範囲の半分弱、教科書にして2ページ半しか進まなかった。まあその分厳密かつ細かい注釈（教科書にある証明方針が採用された理由等）も付けることができているのではないだろうか。できているとよいなあ。これまで2回発表してきたわけだが、テキストが簡単なこともあって、証明が爆発炎上したりしたことはまだない。今回もこれまで以上に気を使っているつもりだから、とりあえず正しいことは書けているはずだ。

水曜日の午後2時からインターン先とのちょっとした面談が予定されている。ちゃんと時間までに起きるためもう寝ようと思い布団に入ったが、なろうを開いてしまう。午前6時半から午前10時半くらいまでなろうを読んで、どうにも眠れないことを受け入れ、このまま起きていることにした。

起きて今日の典型90問を解く。最初少し迷ったが、\bmod 3の数列として見ることで解けた。あるインデックスを選び、そこを-1して、それより前は+1する。数列のすべての項が0になったら操作終了。非0の項を+1して得することはない（感覚的にそう）ので、先頭から順に0に揃えていく感じで操作すればよい。0-indexedでi項目を操作したとき、それより前に対する影響がすべて解消されるのには2^iステップかかる。これを各インデックスで足し合わせれば答えになる。最大ケースは2e18くらいのようだ。

入力を加工してdcで読めるようにしたり、revをかませたりするのをVimで行って、計算自体はdcで行う、というコードを書いていったん満足。それが午前11時くらいで、すでにAtCoderに問題が公開されていることに気づき、通した。35Bだった。revをかませることを念頭に置き、dcコードを反転して入力したりしており、見た目に面白かった。

その後しばらく考えていて、bash 24Bと大幅に短縮することに成功した。これは入力を2進数として読み込む手法で、2001を2進数で解釈するというのは通常だと意味が通らないが、dcにおいては構わず2×23が使われることを利用したもの。星6で24Bということで、星1つあたり4B（？）。これは今のところの最小値である。

学食に行き、帰ってきてから日記をつけていた。午後2時少し前から準備して、面談。すでに内定しているため、今日は人事の方から実際に働くにあたっての契約説明がされた。契約書のコーナーケースを指摘したりしていたが、どうやら契約書の内容を公開するのは一般にヤバいらしいので、何も書けない。30分くらいで終了。

またゼミの発表準備を進める。2時間くらいやって切りのいいところまで進んだ。いい加減眠いので切り上げることにした。布団に入って就寝。午後5時だった。

06/23(水)

消えた。

06/24(木)

06/23 午後11時半に起床。正直もうちょっと寝ておきたかった。このような時間に起きるのは好ましくない。二度寝しようと思ったが、布団でノクターンノベルズを読み始めてしまう。興奮していよいよ眠れなくなった。しょうがないので起きる。

ゼミの準備を進める。というか発表当日になってしまっている。今週もTikZで図を生成した。面白い。

2時間半くらい頑張って完成した。ホスフィンに投げつけて一旦寝ることにした。いい感じに眠気があったはずだが、なろうを少し読んでいるうちにどこかに行ってしまったので、少し頑張って寝た。午前5時半就寝。

午前9時に目を覚ます。今日の典型90問を解く。今日は簡単だが、コードゴルフをどのようにするかがわからない。bashからfactorを呼び出すのは固定として、それをどのように加工するか。最初はwc→dcの順で使っていた。次にwc→dc→wcとなり、さらにdc→wcとなった。具体的な内容は割愛。これで32Bが達成され、満足していたが、後からrakuを使って31Bが作れることに気づいた。これを自動で提出する設定にしておいた。

昨日の典型の、climpetさんの解法に至る過程が面白かった。今見ている桁より右で操作された回数を求めておき、今見ている桁を考慮すると、A+=A+(0 or 1 or 2)になる。

さて、そのようなことをしていたら1時間以上経過し、眠気が消え去ってしまった。このまま起きていることにする。ホスフィンから指摘があった点をいくつか手直ししたり、スライドに書いていないけど触れておきたい内容をメモ書き（これもホスフィンにやったほうが良いと言われたこと）していたら、学食に行き損ねてしまった。午後1時、ゼミが始まる。

今週の発表は、自分ではなかなかよかったと思っている。正確にしゃべろうとするあまり冗長だったりくどかったりしたかもしれないが、とりあえず喋りたかったことはすべて喋ることができたし、逆にちょっと先のことを喋ろうと思って、前提を話していないことに気づいて慌てて戻る、ということもなかったと思う。メモ書きを作るにあたって、自分がどのような発表をするかというのをおぼろげながらも通しで考えていたので、それがよかったのだろう。結局メモ書きの内容は覚えていたのであまり見なかった。

今週のスライドもアップロードしておく。追記と書かれたページは、発表のときに教えてもらった内容・指摘を受けた内容を反映したものである。

Apostol_Chapter3_3.6-3.10.pdf - Google ドライブ

今日のゼミは1コマ分で終わり。来週もそう。ちょうど終わったあたりで今日の典型90問がAtCoderにアップロードされたらしく、ちゃんとACできていた。

ゼミが終わってからしばらく、スライドの追記ページを作ったり、論理学の講義動画を見てミニットペーパーを書いたりしていた。06/09に提出したレポートの採点が終わっているのを見つけて確認してみたが、今回はそこそこ点数が取れているようだった。土台はよくわからないもので構成されているが、その上に乗っている理論は何となくわかる気がする、という感じ。

何とか解けそうな問題を選んで解いていき、午前5時に5問の回答が完成した。すぐに提出。

週記（2021/06/07-2021/06/13） - kotatsugameの日記

午後4時前に家を出て、購買に寄ったあとゲーセンに行く。家を出たときは、地面は濡れているけれども遠くに青空が見えていたので、自転車で大学まで行った。ところが、購買で買い物をして出てきてみると、雨が降り出していた。すぐやむかと思ってしばらく待ってみたが、どうにもやみそうになかったので、折り畳み傘を出して地下鉄の駅に向かった。自転車は大学に置いていく。地下鉄に乗って駅前のほうまで出てみると、ちょうど見えていた青空の下に入り晴れていたので、頑張って自転車に乗ってこればよかったなと後悔。

ゲーセン。午後4時半から午後11時半までみっちりプレイした。今日はかなり進捗があって、13+のSSSが1譜面、13のAJが（今日のアプデで追加されたものも含め）7譜面。さらに14のSSが3譜面増えた。

106小節

トドメだの人のAJ動画（現在非公開のはず）で知った運指。半信半疑でやってみたら全然出なかった。この運指を使って2回目でSSSが出たので、たまたま通っただけかもしれない。しかし、この餡蜜が通るのはかなりびっくり。それほどBPMが速いのか。

ついに（現在解禁している）13+の未鳥が1画面に収まるようになった。Angel dustだけ13.8で、他は13.9。

立ち食いそば屋で夕食をとる。そのまま帰ってもよかったが、晴れているようだったので置いてきた自転車を取りに大学まで歩いて戻った。

自転車を出したところでまた雨が降ってきてびっくりしたが、かまわず乗って帰ってきた。

日付が変わってから帰宅。日記を書いたりして午前3時に布団に入る。信じられないくらい疲れており、眠ろうとじっとしているのすら辛かった。疲れているのは確かなので、即座に入眠。

06/25(金)

午前8時に目を覚ます。起きる気はなかったが、典型90問を読んでいたらなんとなく眠気が消え失せてしまった。ゴミを出す。

今月は1200万文字のなろうに全てを破壊され、まだ1冊も物理的な本を読んでいない。この時間に読んでおくことにする。買ってから机の上で寝かせていた本のビニールを剥き、読み始めた。正午、読了。

「ネトゲの嫁が人気アイドルだった」。表紙イラストが非常に良く、タイトルにも惹かれたので購入を決定したが、あまり面白くなかった。多分、人気アイドルだとかネトゲの要素を目的としていたのに、実際にはヒロインの性質やヒロインと主人公の関わり（のみ）を掘り下げるような内容だったからだろう。あとはヒロインがヤンデレなのもあまり受け入れられない。

続いてもう1冊手を出した。前巻の内容を一切覚えていないが、記録によれば半年ほど前に読んでいるらしい。主人公のペットであって最も最近登場したものについて、何一つ覚えていなくてちょっと戸惑った。少し読んだところで今日の典型がAtCoderで公開されたことを知り、解く。

尺取り法をしたが、やはりこれはwhileループが長い。しばらく考えて、連想配列で値の出現を記録しておけばよいことに気づいた。Perlで書き、連想配列の代わりに${-1}や${-2}を使ういつものテクで縮めた。最終的には入力された配列にmapとgrepをかませるだけになって、変数に配列を保存する必要もなくなりスッキリしたコードで気分がいい。

またラノベに戻ったが、午後2時半くらいに切り上げ。寝ようとしたが微妙に眠れなかったのでハーメルンでGame of Vampireをしばらく読み返していた。何度読んでも良い。午後4時就寝。

今日はサークルの解説会を20時から（SRMに被っているが）予定していた。それに向けて目覚ましを30分おきにセットしており、まず午後6時の目覚ましで一瞬意識を取り戻した。あまりの眠さにギリギリの午後7時までは寝ることを決定。午後6時半の目覚ましを取り消そうとしたが、そこまで考えた時点ですでに体が動かず、そのまま二度寝した。結局午後6時半の目覚ましでもまた起こされることになってちょっと残念。

午後7時起床。食事してサークル解説会のためのスライドを作成しようとしたが、残り15分しかなかった。ABC206-Fに登場するGrundy数について、自分なりの理解を書き記そうとしたのだが、用意が全然間に合わず、ええいままよと発表したら喋っているうちに間違いに気づいたり、口頭で捕捉しようとしたが喋る内容がまとまっておらず上手く言えなかったり……と散々な結果になった。用意は大事。このザマになるのならば、恥を忍んでB問題とかC問題でお茶を濁すのもありだった。

2021/06/25 定例会 | puzzleknot 公式サイト

午後9時20分からyukicoder 301。4完。

yukicoder contest 301 - yukicoder

Aはよい。特別な場合として24=42は有名で、小さい値をしばらく考えてみてもそれ以外はなさそう。Bは区間スケジューリング。Cは置換と合成をセグ木に乗せる。Dを読んだがわからなかった。しばらくWolframAlphaで展開した式とにらめっこしていたが解けない。ふとE問題のsolvedがかなり多いことに気づき、問題を読んでみた。ただのbitDPで、慌てて通す。

残り時間はF問題に挑戦していた。1列持つbitDPで、状態数はかなり少なめ。ここまではよくある考察で、bitDPの遷移は以前evimaさんの問題を解いたときと同じ感じでよさそう。

No.1397 Analog Graffiti - yukicoder

あとは遷移を高速化すればよくて、これは行列累乗だと思っていたが、N=9のときに状態数が2188あることを知った。間に合わない……。遷移行列は疎なので、1ステップ進めるのはかなり素早く計算できる。多分Mが小さいときの値を調べるとうまいこと求まるとかだと考え、それで殴っている人を最近TLでよく見たことも覚えていたが、アルゴリズムの名前がわからなかった。ちょっと調べているうちにうっかりラグランジュ補間だと勘違いしてしまい、ライブラリを貼るも当然通らない。そのままコンテスト終了。知りたかったアルゴリズム名は「Berlekamp-Massey Algorithm」だった。

途中で行列積の高速化について調べていた。3重ループにおけるループ変数の順番を変えてシーケンシャルアクセスになるようにする、という手法が簡単かつ効果が高い。自分のライブラリではそのようになっていなかったので、書き換えたら、テストが落ちてしまった。びっくりして調べてみたら、掃き出し法のverifyに使用していた問題にHackケースが追加されたらしい。場合分けが必要なコーナーケースかと思ったが、よくよく見ると普通にバグだった。num[i]を使うべきところでiを使用していたのを直したらテストが通った。

D問題は数学典型らしい。ここに貼られている問題のうち1問目は誘導付きだったので、それに従って考えてみようと思ったが、解けなかった。泣く泣く未だに持っている赤本を引っ張り出して調べたところ、n\leftarrow n+1とした式に漸化式を代入して式変形するだけだった。

論理学の中間課題の提出期限は明日の午後5時である。CF div.1があるが、writerのレートが低いし配点も不穏なので、見送って課題に取り組むことにした。テーマはこれまでの講義に関係していればなんでもよいという自由度の高さなので、対話形式で証明を進めてくれるプログラムを作ろうと思い立った。一部に構文解析が含まれるので、その実装に慣れているC++言語を選択。どんな設計にしようか考えていたが、考えれば考えるほど実現したいことが思い浮かんでくるので、とりあえず動くものを書こうと心掛けた。

6時間くらいコーディングして一応の完成を見る。とりあえず4つくらい、講義で取り扱った証明を再現できることは確認してあるが、それ以外ほとんどテストしていない。特に、エラーを検出してほしいところでちゃんとエラーが出るかということは全くもって確かめていない。

github.com

READMEをちょっとばかり整備して、リポジトリの作成はこれでOK。課題の文章も適当に作成して提出しておいた。kotatsugameというハンドルネームが自分自身であることは証明できないが、そこを指摘されたときはその時ということにしておいた。

そのようなことをしていたら午前9時半になってしまった。せっかくなので典型90問の投稿を待ってから寝ることにして、昼間読み止しにしたラノベを読み切った。

「異世界でチート能力を手にした俺は、現実世界をも無双する」8巻。このシリーズは1巻が非常に好みだったのだが、巻を追うごとに興味が失われていくのを感じる。現実世界で無双しているのが好きだったのに、前の巻までは異世界でバトルするのがメインで、今巻からは宇宙に舞台を広げている。

典型90問が投稿された。今日は星7だが、ただの2部マッチング。よく見ると制約が少し大きめなので、「辺のキャパシティがすべて1のグラフでフローを流すときにDinicのアルゴリズムを使うと計算量が落ちる」ということが問われているのだろうか。確かにこの事実を正確に認識したのはACLが公開されたぐらいの頃だった気もするので、難しめの知識ではある。まあ何も考えず投げても通りそうだが。

午前10時半就寝。

06/26(土)

午後1時少し前起床。AHC004に参加する。

AtCoder Heuristic Contest 004 - AtCoder

問題文を読んだが、すぐには方針が思い浮かばない。15分くらいコードゴルフして、あとは布団に戻って寝ながら考えることにした。コードゴルフはVimで、Nが固定であることに気づいて多少縮んだ。最初提出制限が30分になっていてびっくりした。

午後1時半くらいにまた就寝。そのあと何度か起きつつも、基本的には寝ながら生協の弁当を待っていた。午後5時、今週も受け取りに成功。再度寝ようとしたが、AHCが残り2時間くらいしかないことを考えて、起きてしまうことにした。まず典型90問を通してから、午後5時半過ぎにAHCのコーディングに入る。残り1時間半。

縦横両方向を考慮するのは難しそうだったので、とりあえず1方向のみ考慮してどうなるか点数を見てみたい。文字列がどれくらい重なっているかを前計算して、これをもとに20文字にどれくらい詰め込めるかを計算する。この時両端がループすることは考慮しない。最初に入れる文字列は乱数で決定し、残りをdpで計算して復元したものを1行として、これを20回繰り返したものを提出した。3.8e9点。

冷静になると、多点スタートのBFSなどと同様、最初に入れる文字列を固定する必要はなかった。4.5e9点。

ある文字列が別の文字列を含む場合、これまでは無理やりずらして重ねていたが、片方に吸収させてしまうことにする。その分、吸収した文字列には重みをつける。5.6e9点。1方向しか考慮していないのに2桁順位になってしまい、興奮する。残り30分。

文字列を重ねるときに、同じ行の前のほうで使った文字列を使わないようにした。遷移履歴によってどの文字列を使ったかは変わるが、使った文字列をbitsetで保存し、dpの各値に対応付けて覚えておくことで実装できる。毎回大量のbitsetを生成すると信じられないくらい重くなったが、グローバルに置いておくと爆速だった。また、行の端でループする部分列と縦方向の部分列も検出するようにした。これで5.88e9点。

トップページを探しても採点についての注釈がなかったが、AHC002と同様の形式（短時間マラソン）であることを考えると、今回もコンテスト中の最高点で順位が決まると考えてよさそう。ということで最終提出のことはあまり考えず、残り時間で2回ほど提出を行ったが、結局伸びなかった。

最終順位は68位、パフォーマンス2283でレートは1783→1941(+158)。AHC002と同様まったくランダムなことをしていない。自分では全く考えもしなかったが、この問題でも普通に焼きなましが効くらしくてかなりびっくりだった。何を焼きなますかというのは、やはり経験がないとわからない部分なのだろう。

TLでいくつかの方針を見ていたが、今回の問題では文字列同士の重なり具合に応じてマージするのが強力で、それをして（さえ）いればそこそこスコアが出るらしかった。

今朝提出した論理学の中間課題に評価がついていたが、どうやら提出だけチェックされたらしく、内容については一切触れられなかった。ウン百人と受講者を抱えているのでしょうがない部分はあるのだろうが、さみしい……。

しばらく日記を書き、午後9時からABC207に参加した。

AtCoder Beginner Contest 207 - AtCoder

全完7位。D問題は真面目にやっていたのに25分かかってしまった。これはE問題とF問題にかけた時間を合わせたよりも長い。

A問題はVim。似たような問題を数問ゴルフしたはずなので、そこからコードを引っ張ってくることにした。「ringring」という問題名を思い出せたので検索してみると、こちらは最小値。まあやることは変わらない。ACした後、試しに数値ではなく文字列として比較するコードを投げてみたら、通った。これで少し縮んだ。

A - ringring

Bは式変形。ゴルフもちょっと考えていたが、場合分けが面倒そうなので後回しにした。Cは場合分けパーティーかと思ったが、最初に全部半開区間にそろえておけば簡単。問題文をまともに読んでいなかったため、サンプル1を試して初めて実数の点を考慮しなければならないことに気づいた。気づいてすぐ、半整数に拡張することで同様に扱えることを思いつけたのはよかった。

Dは、座標も小さいので、たいがい何をやっても解けそうではあるが、逆にどのような実装方針を選んでも面倒に見える。僕は、両方の集合から基準とする点を1つずつ選んで、残りを偏角ソートし、ずらして対応させられるか見る方法で解いた。最初、基準からの距離も考慮しなければいけないことを忘れており、書き直しに時間を取られた。基準点を選ぶのにO(N^2)、ずらす度合いを試すのがO(N)、対応させられるか見るのがO(N)くらいか。日記を書いていて気付いたが、片方の集合の基準点は決め打ってしまってよかった。

EはDP。部分列をいくつ作ったか、今作っている部分列の総和の余りがどうなっているか、をキーに持つDPは3乗だが、部分列を一気に遷移することにしたら2乗に落ちそう。実際、遷移先としては一番近くて総和の余りが0になるようなインデックスだけ考慮すればよく、それらもまた2乗の前計算で求められる。Fは2乗の木DP。

Dが大爆発したが、みんな大爆発していた。黄色diffらしくてさすがにすごい。すごいぜ。まあこういう実装が面倒な問題の解かれ具合なんて予想できないだろうから、D問題においてあること自体はわかる。しかしこの問題はただひたすら面倒なだけなので、普通にアルゴリズムが難しいE問題のほうが解かれているというのはびっくり。

Fの解説では2乗の木DPが2乗になる理由としてN頂点の完全グラフのことが書かれていて、これ知らない証明だなあと思った。僕が知っているのは計算量T(N)がT(l+r)=T(l)+T(r)+lrを満たすことからT(N)=O(N^2)を示す方法で、シンプルだがなんだか騙された感があった。細かい理論を知らないからかもしれない。

コードゴルフをする。A問題は最初に少し時間を使ってゴルフした。B問題は場合分けをどのように吸収するかが本題。dcは0とのmaxを取るのが簡単に書けるので、わざと答えより1大きな値を出しておいて1引くことで回答を作り、-1を出力するべきケースでは頑張って非正の値が出てくるようにする。CはよくわからないがとりあえずRubyで書いておいた。EをRubyで通そうとして、なかなかTLEが取れず苦労したが、どうやら途中でmodを取っていないのがまずかったらしい。最初のほうに試したときはむしろ遅くなっていたのだが、何があったのだろうか。

D問題は、まず重心からの相対座標に直して、あとは回転させる角度をたくさん試すと通るらしい。角度をたくさん試す解法のコードゴルフには前例がある。Octaveを使い座標を複素数として持ってexp((0:n)*i)を掛けているが、これは弧度法における0からnがだいたいバラバラに分布することを利用しているわけで、結構好みのコード。

F - Engines

これでやってみることにした。回転させた後はソート（複素数をソートすると絶対値の大きさ→偏角の大きさで比較するらしい）して一致を判定する。が、一致判定のEPSをどのような値にしても微妙に通らない。しばらくコードを投げ続けていたが、ふとソートがヤバいことに気づいた。絶対値が等しい2点があったとして、回転させた後も等しいと判定してくれるかは微妙っぽい。これは……どうしようもないだろう。たとえ実部と虚部に分けて比較したとしてもダメそう。諦めた。

朝方、D問題のRubyによるコードゴルフが行われていることに気づく。集合から2点選んで基準ベクトルとして使うコードらしい。選ぶ2点を全探索する部分が長そうだったので、配列をシャッフルして先頭2点を取り出すことにした。いわゆる乱択解法で、\binom{N}{2}通りから求める1通りを引く必要がある。時間制限との兼ね合いから180N回くらい回すことにした。当たりを引けない確率はN=100の時に最大で2.6%くらいらしく、ちょっとヤバげだが、投げたら3回目で通った。

日記を書いていたが、途中で切り上げ、明日のAGCに向けて寝ることにする。布団に入ってから少しだけラノベを読んで就寝。午前7時半だった。

06/27(日)

午後7時、目覚ましにより起床。かなり信じられない。寝る前に念のためと言ってセットした目覚ましだが、12時間もあるのだし自然に起きるだろうと思っていた。疲れがたまっていたらしい。

昨日寝る前に読んでいたラノベを読みつつAGCが始まるのを待って、参加した。AGC054。

AtCoder Grand Contest 054 - AtCoder

3完50位でパフォーマンス2974、レートは2749→2774(+25)。highestを13更新した。

Aは簡単。先頭と末尾が同じ文字'a'の場合を考えたとき、'a'以外の文字が連続する箇所がないならば、どのように操作しても常に先頭と末尾が同じ文字'a'である状態が保たれてしまう。いずれすべてが文字'a'になって終了。そうでない場合は前半と後半をそれぞれ消せて2回の操作で空文字列にできる。そこそこ丁寧に考えて解いた。明らかにゴルフしやすい見た目をしていたのでゴルフ欲が抑えられなかったが、「先頭と異なる文字」をsedの正規表現で書く方法が思いつかなかったこともあり、すぐに諦めて次の問題に進んだ。

Bはよくわからなかった。値の大小を考えてみてもよい性質はなさそう。ここで方針ガチャとして、お互いの取る要素を固定することにした。まだよくわからないので、もうちょっと方針ガチャを回して「どのような順番だったらその割り当てで取れる順列が存在するか」ということを考えてみると、驚くべきことにどのような順番であっても順列がただ1つ対応することに気づいた。半信半疑でbit全探索を書いてみるとサンプルが合ってしまうので、どうやらこれが正しいらしい。

適当に部分和DPっぽいものを書くが、ループが3重になって計算量がヤバそうに見える。しかしどのように高速化したものかとんとわからないので、とりあえず最大ケースを試してみよう……としたら爆速だった。改めて計算量解析をするとO(N^2\sum W)で、これは1004になって間に合う。投げたら通った。かなり速く解けたが、解法ガチャに成功しただけで、一歩間違えれば一生解けないタイプの問題に見える。

Cは順当に解けた。一般に、転倒数を減らす方向のswapしか考えなくてよいようだ。これはP'を考えていても得られる性質だが、これ以上はPを考察の対象にする必要がありそう。そこでまず、PからP'を作り出す操作列（これは複数考えられる）が一意にならないか考えてみる。適当に実験してみたところ、どうやら値が小さいものから貪欲に揃えていくのがよいようだ。具体的にどこにそろえるかというと、まず1はK+1番目以前に動かさなければならない。次に2だが、これは1がK+1番目以前にある状態ではK+2番目以前に動かせばよいらしい。別の言葉で言えば、1を無視した列においてK+1番目以前に動かす。以下、同様にiはK+i番目以前に動かす、あるいはi-1以下を無視した列においてK+1番目以前に動かす。

各iについて、i-1以下を無視したPにおいてK+1番目以前にあったものは、i-1まで揃えた後でもK+1番目以前にあるため、動かさなくてよい。逆に言えば、i-1以下を無視したP'でちょうどK+1番目にあるような要素i、つまりP'でちょうどK+i番目にあるような要素iはそれ以降から動かしてきた可能性がある。この自由度がPの自由度になりそう。具体的には、場所の候補がN-K-i+1通りある。

サンプルでは単純にこれの総積が答えとなるが、自由度が1より大きな要素が1つしかないので、本当はこんな単純なわけがないと思い、K=2で4 2 1 5 3 6を考えていた。1に自由度4、3に自由度2があって、自由度が1より大きな要素が2つある。互いに干渉することで自由度が減ると思ったのだが、実際Pを作ってみると本当に8通りあってびっくり。改めて考えてみると、自由度を考えるときもi-1以下を無視することで、自分より右にはいつでもN-K-i個の要素があって、自分より小さい要素との位置関係を無視してよいことが納得できる。O(N)の非常にシンプルなコードになって、まだ微妙に疑いながらも提出してみるとAC。順位表を見ると結構通されていたようで、度胸が足りなかった。

この時点で30分しか経過していなかったが、そこから90分くらいD問題を考えてなんの成果も得られなかったので、残り時間はコードゴルフをしていた。終盤DとEがそこそこ通されたので順位は思っていたより落ちたが、赤パフォが出てよかった。

Dの解説を読んだ。括弧だけ抜き出してそろえることは考えていて、oとxがどの位置に行くかで操作回数が変わりそうだと思っていたが、変わらないらしい。)o(を()oとするかo()とするかで操作回数が変わらないことが、もっとたくさんの括弧と記号でも言えるということ。このあたりで僕がコンテスト中に考えていたことは終わりで、解説の残りについてはあまり考えていない。

コードゴルフをする。A問題は何かしらの言語で正規表現を使うのがよくて、sedだとダメらしいのはコンテスト中にわかっていたため、Perl。マッチの結果の0と1を使って計算をして答えを作り出すことで場合分けを減らしている。Cはdcで解けた。Nを精度kとして保存し、後から998244353で割った余りを求めるときに0kで戻していたが、実はループ内でkをどんどんデクリメントしていたので、ループ後にはちゃんと精度0になってくれている。

ラノベを1冊読んだ。「クラスに銃は似合わない。」。句点までが題名。主人公の護衛対象となるヒロインの性格があんまり合わず、読み始めはちょっとげんなりしていたが、進むにしたがって主人公にスポットライトが当たるようになって面白かった。読み終わった直後は、合わない要素が1つでもあることによってあまりよくない印象だったが、日記を書きながら冷静になってみると、最後はそこそこ楽しんで読めていたことに気づいた。最近読んだラノベを面白くないと思ってしまいがちなようだが、せっかく買っているのだからできるだけ好意的な感想を持ちたいものだ。

今日のAGCでへのkが自由色になった。へのk様と呼ばせていただきます。1999年生はmaroonさんとの間にめちゃくちゃデカい壁があると思っていたが、AtCoderのレートで見たらもうほとんど差がない。壁は相変わらず高くて、それを越えていくへのk様はすごい。

日記を書いていて、自分の文章について思うことがあった。