週記（2021/04/12-2021/04/18）

04/12(月)

朝方、先週分の週記を投稿してからの話。この日から今セメスターの履修登録が始まったので、どんな講義が取れるのか一通り確認した。

数理統計学は3セメスターに開講されている講義で、当時は再履修が多すぎて単位取得上限に引っかかって取れなかったもの。今セメスター取ることにした。すべてオンデマンド型の講義なので、まあ負担にもならないだろう。いざとなったら落とせばよくて、取って損はない。

ほかに言語学と論理学もちょっと興味を惹かれる。しかし言語学のほうは毎週課題があって、そのために指定された教科書を買わなければならないようなので、取らないことにした。論理学は人気なので、定員の制限が怖い。水曜2限と木曜1限の2つのうちどちらにするかも含め、後日決めることにしよう。

3月のコードゴルフ大会の問題をJellyfishで解くコードの解説記事が公開されていた。Jellyfishの入門記事としても書かれているようで、非常に面白かった。

Jellyfish(esolang)の紹介

午前11時くらいに布団に入り、なろうを読みふけっていた。

昼頃、仙台レジャーランド一番町店の閉店情報が流れてきた。

かなりびっくりした。日付が変わってもしばらく開店していることや、チュウニズムに台を拭くための濡れタオル（今は使い捨ておしぼりに変わった）が設置されていることなどを理由に、これまで3年間頻繁に利用してきた。僕はチュウニズムしかプレイしないので少し離れたSEGAでもいいが、ボルテや弐寺がメイン機種の人はさらに離れた店舗まで行かなければならなくなりそう。確かに最近たまに行っても全然人がいないという印象だったが、閉店してしまうとは……。

ずっとなろうを読んでいたが、午後4時くらいに寝落ちした。

午後10時起床。またずっとなろうを読み続けていた。ゴミを出さなければならないので、午前4時半くらいに切り上げて布団から出て食事した。

ゴミを出す前にExperimental Educational Roundというのを埋めた。18問あって、競プロを始めてすぐの頃にFだけ解いていたようだ。

Aはよい。Bは誤差が怖いが問題文中の数字をそのまま使って出しても通った。CDもよい。Eは22ケース目でWAしてしまった。入力された点を中心とする六角形が存在するよう、入力に従って座標系が少し変わるらしい。解説についたコメントでもここでハマった人がたくさんいたことが見受けられた。

Gは2つの二項係数を1つの変数で計算しようとするとオーバーフローする。Hはちょっと考え込んだ。Iはよい。Jは「when the next number of sales is divisible by all numbers from 2 to 10」だから2519の時点でボーナスがもらえると思って1WA。KLMNもよい。Oは幾何ライブラリがあればベクトルの回転・足し算で簡単。Pは↓の記事を見て解いた。2018年の記事なのでコンテスト当時はなかったが、まあいいだろう。

つくばサイエンスエッジ2018/文京学院大学女子高校 - 「みらいぶ」高校生サイト

Qは三角錐と四角錐の体積を求めたあと、サンプルを使って五角錐の体積の計算式（係数）を求めた。Rはエスパーで解いたが、解説を見ると相手の真似をする戦略が取れるとあってなるほどという感じ。

このコンテストは全体的に面白くなかった。アルゴリズムを使うような問題がなく、またmodを取らせないことでオーバーフローに気を使わせるだけの問題も多い。

ゴミを出してからECR8を埋めた。Aは題意を把握するのに手間取った。BCはよい。Dは桁DP。Eは優先度付きキューとBITを使って、右上のマスから見たときに左下のマスになれるものを数える。Fは問題タグでフローであることを見てしまったのですんなり解けたが、コンテスト中に出たら解けたかどうか自信がない。

布団に入ってまたなろうを読んだ。午後1時くらいに寝落ちした。

04/13(火)

午後10時起床。またずっとなろうを読み続けていたが、午前2時半に最新話に追いついた。

https://ncode.syosetu.com/n4212eh/

先週からずっと読んでいた「プニキとはじめるリーグ運営　～野球ゲーム？作って運営します～」。非常に面白かった。代表となって会社を大きくしていく系の話として捉えている。

主人公はプログラミングができるわけでも経理や広報に詳しいわけでもないが、それらは会社の代表としての仕事ではないから別の人に任せるので問題ない。会社の方針を決めて責任を取ることや、会社の顔として取材を受けたり会見をすることが仕事であって、その意味で主人公には会社の代表となる才能がある……ということが書かれていた。そういう設定は「羽月莉音の帝国」を読んで以来の好物である。主人公の性格も好みであった。

起きてコードゴルフをした。2つ取られていたが、両方取り返すことができた。片方はdcで、もう片方はPyPyだった。PyPyのほうはRubyやPerlではもっと短くなりそうだったが、TLEしてしまう。ではCrystalならどうだろうと試してみることにしたが、ここで1つの発見があった。これまで入力をすべて読むのにはARGF.gets_to_endを使用していたが、言語アップデートで使えるようになったのか、`dd`で良いようだ。この更新が効くコードを探し、全部縮めておいた。

Rubyでmapを使いto_iを適用するとき、map &:to_iと書ける。しかし例えばto_i(2)を適用しようとしたときにmap &:to_i(2)とは書けない。&はあくまでSymbolをprocにするだけの糖衣構文であって、procにはレシーバと残りの引数を同時に渡す必要があり、procの第2引数だけを部分適用することなどはできないということだ。

一方Crystalではmap &.to_iと書く（コロンだった箇所がピリオドになる）が、to_i(2)の場合もmap &.to_i(2)と書けるらしい。Rubyの構文をCrystalに持ってくる際に新たな記法に変える必要性が生じて、その結果このような書き方が可能になった、ということが↓のページに書いてあった。これもコードゴルフで役に立つ構文である。

to_proc - The Crystal Programming Language

ラノベの新刊チェックをしていたら、「サイレント・ウィッチ」が書籍化することを知った。

kadokawabooks.jp

またなろうを1つ読んだ。逆行転生して株取引で儲ける話。

https://ncode.syosetu.com/n8435gw/

Qiitaで何か記事を書きたいと思い立ってしばらく調べていたところ、Jelly言語でABSを解いた記事を発見した。Jelly言語はTSGのコードゴルフ大会でしか触れたことがなく、日本語資料がほとんど見つからなくて毎回公式ドキュメントを必死に読んで書いていたが、なぜこの記事が見つけられなかったのだろう。かなり内容があって、よくわからない筆頭であったquickについても詳しく説明されているので、もし当時見つけられていれば非常に役立っただろう。

qiita.com

ECR9を埋めた。Aが信じられないくらい難読だった。Bはよい。Cはa+b<b+aという比較関数でソートするもので、何回か見たことがある。DはLCMの最大値が小さいことを利用して調和級数の要領でカウントする。Eは多項式のべき乗を二分累乗法で行う。Fはbitsetを使用したが、想定解では距離行列となることを利用して最小全域木を取っていた。頭が良い。

ECR10を埋めた。Aはまた難読。BCはよい。Dは適当に書いたら全然違うものをカウントしてしまった。Eは二辺連結成分分解。久しぶりに見た気がする。FはAGC013で既出、と思ったらAGC013の方が後のようだ。AGCのほうは解いてあるからそちらからコピペしてきても良かったが、これも練習だと考えて一から書いた。蟻が座標の昇順に並んでいなくてキレそうになった。そういう面倒さはいらない。それにしても問題名まで一緒であるというのはすごいことだ。

Problem - F - Codeforces

C - Ants on a Circle

昼になったので学食に行きがてら原付を点検に出そうと思ったが、家を出た瞬間雨が降り始めたので、原付を点検に持っていくのは止めにした。歩いて学食に行ったところ、学食は午後1時半でいったん閉店するらしく、食べられなかった。前のセメスターは午後2時閉店だったので、あんまり人が来なかったのだろうか。

AtCoder Jobsに登録し、インターンに応募してみた。インターンの募集は4社が掲載されていて、そのうち3社は機械学習の経験が必要だったので、残りの1社であるところのフィックスターズを選択した。プロフィールに書くプログラミング言語の習熟度について、C++とかPerlはもう4年くらい書いているが、それらはすべて趣味の範囲であるから、最低レベルになってしまう。しかし確かに競プロで身に着けた文法というのは限定的であるから仕方ないのかもしれない。ファイルの読み書きもおぼつかないのは言語を使えるとは言えない、と言われたらその通りである。

ECR11を埋めた。ABCはよい。Dは2点を取りその差を計算して重複カウントをする。Eはまあまあ面白かった。二項定理でシグマを1つ消すやつ。FはCHTになったのでうしさんのLiChaoTreeを貼った。LiChaoTreeはそのうち自前で用意する必要があるだろうが、まだアルゴリズムの詳細も知らない。

ECR12を埋めた。Aはよい。Bは難しそうだがシミュレーションしてよい制約。Cは、変える文字数の最小値を出力する問題をAtCoderで見たことがある。実際の構築も適当にやってよい。Dはありったけの1と偶数を1個以下か、偶数と奇数をそれぞれ1個以下、この2通りに絞られる。Eはbinary Trie。Fは1011以下の素数の個数をカウントする問題になって、これはLibrary-Checkerにある。本当はアルゴリズムを学んで自力で実装しようと思ったのだが、かなり難しそうだったので諦めてうしさんのものをコピペした。

Library Checker

直近のECRは2回ともFで未履修のアルゴリズムが出題されており、かなり教育的であると感じられる。

ECR13のAからDまでを埋めた。ABCはよい。Dはこれも二分累乗法の1つである。Eを解こうとしたがWAで、テストケースを見てもよくわからなかったので諦めた。布団に入って少しだけなろうを読み、午後7時半就寝。

04/14(水)

消えた。

04/15(木)

午前4時起床。TROCを逃してしまった。午前7時くらいまでなろうを読んでいた。

kimiyukiさんによってoj-mini.pyが公開された。ojの機能を制限して単一ファイルに収めたものらしい。

github.com

コードを削ったとされているので、気になって読んでみた。可読性を損なわない範囲でさらに行数を減らせるならプルリクを送るべし、と言われているのでちょっと考えていた。1か所、より良い（と僕が思う）書き方ができると感じた所があり、他に2か所ちょっと気になるところがあったので、それらを書き換えたプルリクを送ったところ、マージされた。

Update oj-mini.py by kotatsugame · Pull Request #1 · online-judge-tools/oj-mini.py · GitHub

さらになろうを読み続けて、正午くらいに最新話に追いついた。

https://ncode.syosetu.com/n5295gq/

面白かった。やはり主人公最強は最高。女主人公なのはよいが百合は好きではないので、そのあたりの描写は読み飛ばし気味だった。百合であるという前評判の作品でも、お互いに想い合っている、くらいの軽い描写なら普通の友情との違いが判らずに読み進めるのだが、この作品は結構直接的な行為に及んでいる。

風呂に入ってAtCoder Jobsを確認したところ、応募したインターン先から返信があった。書類選考ということで、Googleフォームに必要事項を記入して送った。開発経験の有無を聞かれたが、全くないのでかなり絶望的。確かに3週間の短期インターンであるから、何も下地がない人間を採用しても碌な成果が出せないのかもしれない。機械学習の知識もない、ないない尽くしなのでもしかしたら面接に進めないかもしれない。

学食に行った。先日の経験を生かし、今日は閉店ギリギリに到着できた。ラーメンを食べた。学食でラーメンを注文するときは、まずレジの列に並んでお金を払い、出来上がるまで別の列で待つことになる。この2つの列は確かにややこしい。人に、その列はどういう列か質問された。新入生だろうか。

学食へは原付で行った。大学を出てガソリンスタンドに行き給油、そのあとバイク屋さんに点検のために預けた。ガソリンスタンドは交通量の多いところにあるので、いつもかなり緊張して走っている。いつもといっても、原付を購入してから18か月経つが、まだ3回しか給油したことがない。それ以外は交通量の少ない山道を走ってばかりなので、3車線ある道路などには全然慣れない。

そのあとはゲーセンに行くつもりだったが、なんとなく眠いこと、また軍手を忘れたことなどを理由にしてすぐ家に帰ってきた。

僕は寝ていて問題すら見ていないが、ECR107のG問題はTL 5secということもあって愚直が通ったらしい。risujirohさんのコードに$50の懸賞金がかかったと話題になっていた。期限は24時間で、結局誰もそのコードを落とせなかったのだが、懸賞金の$50はチャリティー団体に寄付されたようだ。

Hack risujiroh for $50 - Codeforces

布団に入っていくつかなろうを漁っていたが、どうにも文章が合わないと感じるものばかりだった。2時間くらいそのようなことをして、午後5時くらいに寝落ちした。

04/16(金)

04/15 午後11時に起床。自分で設定した日付が実際の日付を追い越したのはこれが初めてのことであるように思う。

ECR13のE問題を考えたが、どうにも解けなかったので解説でDPテーブルの持ち方だけ確認した。自分が優勝した状態から始める逆順のbitDPであったようだ。考えが凝り固まって、そういう発想は一切出せなかった。コンテスト中のsolvedが150人くらいいる問題が解けなくて非常に悔しい思いをした。

F問題を開くと、LiChaoTreeで直線を削除するクエリもある問題だった。「LiChaoTree 削除」で検索したらこの問題そのものの解説記事が出てきてしまった。もういいやと思って記事を読むと、解説ではクエリ平方分割の方針が想定解となっている、との情報が得られた。そちらについては見ている解説記事では触れられていないので、その方針で解くことにする。

しばらく考えていたがわからなかった。布団に入ったら寝落ちした。午前3時だった。

午前8時起床。TCO21のRound2に進出していた。レートが高い人はR1に出なくてよい、というやつらしい。存在を完全に忘れていた。毎年R1はABCよりも簡単な問題しか出ず、そのくせ全員Ratedなので、とんでもないレート変動になってしまう。parallelがあるが、出ないほうがマシ。

ECR13のF問題のクエリ平方分割解がわかった。今見ているブロックで削除される線分については、最初からLiChaoTreeに入れないことにする。今見ているブロックで削除しない線分についてはLiChaoTreeで管理して、いずれ削除される線分は1つずつ愚直に見ていけばよい。クエリN個、ブロックサイズをWとすると計算量はO(\frac N W N\log N+NW)になって、これはW=\sqrt{N\log N}のとき最小になる。W=500とかW=1000だとTLEしてしまったが、W=2000にすると通った。log(N)が思ったより効いていたようだ。

うしさんのLiChaoTreeはデストラクタがなく、この状態だとMLEしてしまったので、メモリを開放する操作を入れようとした。しかしポインタを辿ってdeleteするコードもTLEしてしまったので、ACコードではvector<Node>で管理し、しかもvectorは使いまわすようなコードを書いている。

atcoder.jp

AGC053Aが縮められていた。$^Tという特殊変数は、プログラム起動時のUNIX時間を表すらしい。これは現在およそ1.6e9くらいで、しかも書き換え可能なのでmaxの初期値として使用できる。この特殊変数を用いてさらに2問ほど縮めることができた。

月曜日に言及していた論理学の履修登録をしてみた。水曜2限のほうはClassroomで350人以上が受講しており、割り当てられた教室の定員334人をすでにオーバーしているので、何人かは履修登録できないことになるらしい。木曜1限はまだ120人くらいしか受講しておらず、教室の定員174人までまだ余裕があるため、こちらを選んだ。どちらにしてもリアルタイムで受講したり講義室に行かなければならない場合はどうせ単位は取れないので、1限でも問題ない。

4時間くらい週記を書いていた。また溜めっぱなしだった。

Classroomに論理学の講義動画がアップロードされていた。少しだけ聞いたところ、どうやらClassroomではなくISTUを使って資料を配布したりするらしい。そちらを確認したところ、ミニットペーパーの提出をする欄があった。どうやらリアルタイムで受講する必要はなさそうで、一安心。

昨日預けた原付の点検が終了したらしいので、受け取りに行ってきた。午後3時半くらいだった。家に原付を停めて、今度は自転車に乗ってゲーセンに向かう。先ほど原付で走った道路はすでに帰宅ラッシュか何かで込み始めていて、危ないところだった。大学近くの道路は、朝夕信じられないくらい込むので、できるだけ避けて運転するようにしている。

立ち食いそばを食べてゲーセンに入る。店頭に閉店の案内が掲示されているのを自分の目で確認したが、まだこの店が閉まるということに現実感がない。

ゲーセンは03/23に行って以来3週間ぶりのようだ。新曲がいくつも追加されたり解禁されたりしていたので、埋めていた。途中ホスフィンと合流して食事に行ったが、夕方のそばがまだ腹に残っていて注文した分を食べきれなかった。ホスフィンとはその後もチュウニズムで遊んで、フルチェインも出た。

「赤壁、大炎上！！」でSSSを出した。6回くらいだったか、結構すんなり出た。「劉備軍の旗～～～！？」までAJで、あとは一所懸命擦ったり叩いたりしていた。何回かプレイしてみたところ、主に端まで手が届いていなかったり早く離してしまったりで抜けていたようだったので、丁寧に譜面を見ることを意識していた。最後の「勘弁してくださ～～～い！」は1-2くらいだった。これはかなりうまくいった方である。

ゲーセンにいる間にyukicoderが始まっていたが、問題を見ていない。夜中にCF div.1もあるが、ひたすら眠いので出ないことにした。

ところが何となく眠る気になれなかったので、ECR14を埋めた。ABCはひたすらつまらない。Aは普通の問題に見えて、恣意的なコーナーケースが設定されている。Bはアルファベットの書体が指定されて、与えられた文字列が左右対称になっているか答える問題。Cは与えられた小数を指数表記に直す問題。本当にカス。解く価値は一切ない。Tutorialを見たら青とか緑が出題していた。レートを上げて出直してほしい。DEは典型だが、まあまあ面白い。Fは……よくわからん。全通りの答えを先に求めるという問題を出したかったのか？

ECR15のABを解いた。特に言うことはない。眠気に耐えかねて布団に入り、午前3時就寝。

04/17(土)

午後零時半起床。まだまだ眠いが、大昔に友達に貸した本を受け取るため、この時間に起きておく必要があった。午後2時、無事に受け取れた。

論理学の第一回講義のミニットペーパー提出は今日が期限である。講義資料を見ていたところ、教室の定員を勘違いしていたことに気づいた。確かに満席まで座れば174人だが、このご時世でそんな密な状態が許容されるわけがない。結果定員は大幅に減って90人。履修登録した時点ですでに超過していたようだ。

とはいえ、水曜1限のほうは倍率がもっと高くなっている。なので、このままこの講義を履修登録しておくことにした。ミニットペーパーには履修希望も含めたコメントを書いてください、とあったので、適当に書いておいた。自分のせいで卒業単位を集めている人が履修できないと罪悪感があるので、自分はこの単位が卒業のために必要ではないことも書いておいた。

続いて数理統計学に出ていた課題を終わらせた。初回なのでごく簡単な計算問題。立式後は計算機を使ってもよいらしいが、むしろそのほうが面倒に思えたので、手で書いた。特に問題なく提出完了。この講義の課題の提出期限は一律セメスター終わりなので、↓のようにずっと放置したまま何もせず終了してしまうことを危惧していたが、幸先の良いスタートを切れた。

課題の締め切りはとうに過ぎ去っていたようだ。結局何一つ提出しないまま終わってしまい、評価はDではなくN/A（？）だった。

週記（2021/02/01-2021/02/07） - kotatsugameの日記

今日は第二回日本最強プログラマー学生選手権がある。それまで30分くらい間が空いたので、ECR15のCDEを解いていた。Cは普通。Dはよくわからないが、サンプルが強めのようで、それに通るような場合分けをしたら通った。車に1回だけ乗るか、全力で乗りつぶすか、最後だけ歩くかしか考えなくてよい。Eはダブリングで全部計算できる。

第二回日本最強プログラマー学生選手権が始まった。Aからちょっと難しいが、YZ/X円より真に小さい整数が求まればよい。これはceil(YZ/X)-1==(YZ-1)//Xになる。49秒かかったがFAだった。

Bは対称差集合で、Rakuに専用の演算子⊖、あるいは(^)がある。ところが出力でちょっと躓いた。ただソートするとsetオブジェクト1つのリストのソートになってしまう。これだとsetのキーの順番は変わらず、ちゃんとソートされていない可能性がある。これでWAを出して、keysを付け加えてAC。

Cはちょっと悩むが、答えを全探索してよい。Dはなんだか見覚えがある。そちらは解けなかったが、今日の問題は順番が固定されているのでほとんど明らか。Eは回文のレベルをしっかり理解するのにかなり時間がかかったが、わかってしまえば文字列を半分に折っていくだけ。折る回数はlogのオーダーなので、愚直にやっても十分間に合う。最後に回文を故意に壊さなければならないことにはちゃんと注意しておく。

Fは行と列をそれぞれデータ構造で持つ。クエリを先読みして座圧しておき、個数と和をBITで持てばよい。最初数列の値がすべて0なのは良心か。Gを見てすぐ行列木定理が思い浮かんだのはいいが、必ず使わなければならない辺をどう処理するか悩んだ。これは実は悩む必要などなくて、先にくっつけて頂点を圧縮するだけ。modint、matrix、UnionFindと3つもライブラリを貼ったのでコード長が6000Bを超えた。コンテスト後のTLで、行列木定理を使うAtCoderの過去問が紹介されていたが、実はその問題は解いたことがない。僕が行列木定理を知ったのはPCK本選の過去問だった。

https://onlinejudge.u-aizu.ac.jp/problems/0314

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

週記（2020/12/14-2020/12/20） - kotatsugameの日記

Hは非常に面倒だった。まずグラフがN頂点N辺の連結グラフ、いわゆるなもりグラフであることを確認する。これはループ部分とそこから生えている木部分に分解できる。荷物配送は、ループを通るか通らないかで2通りに分けられる。

ループを通らないものについては適当に処理できる。解説ではLCAと木上のimos法を使っているが、僕はマージテクを採用した。LCAはライブラリになっていないし、そもそもたくさん木があってかなり面倒に見える。この選択はよかった。かなり実装が楽だった。

ループを通るものについては、ループ上の2点を連結にする問題になって、これはループのどちらを通るかで各荷物2通りの辺の張り方がある。2-SATやフローを疑ったが全然違う。ここで、どこか1か所を通らないと決め打ったとき、すべての荷物の辺の張り方が決まることに気づいた。ほかに考えるべきこともないので、この方針で突き進んでいくことにする。ループを割り開くと列に対する操作になって、適当なデータ構造を用いることができる。それぞれの辺についてそこを通る荷物の個数を数えることにすると、ある荷物における辺の張り方を変えるというのは、区間に対する足し算になる。通る荷物の個数が非ゼロであるような辺について、その重みの総和を取得したい。

遅延セグメント木で普通にやるとまずい。なぜなら、区間に対して作用した結果、通る荷物の個数がゼロの辺と非ゼロの辺両方が生じる可能性があるからだ。これは区間の更新に失敗したということになる。ところで、「区間の更新に失敗する」という文言には見覚えがある。

rsm9.hatenablog.com

segment tree beatsで実装できるのでは！？↑のページを読むと、区間の更新に失敗する回数が上から抑えられるときに役立つと書いてある。今回の問題では、通る荷物の個数が非ゼロからゼロになるような更新が何回あるかを考えればよさそうだ。注目している辺を通る荷物の個数をゼロにしながらループをぐるっと一周するのだから、これは各辺についてちょうど1回である。抑えられた！嘘である。初期状態で0-1、2-3、4-5など1つ飛ばしに辺を使用している場合、そのような更新はO(N^2)回ある。

コンテスト中はこのことに気づかず実装に入った。そもそもなもりグラフの前処理から実装が面倒だが、何とか実装しきってサンプルを合わせた。ACLを張り付けているので7000B超え。提出するとゆっくりゆっくり実行が進んでいく。それに合わせて自分の心拍数も天井知らずに上がっていく。ジャッジにはかなり時間がかかったが、一発でACできた。

結果、全完して3位だった。僕を含め上位3人は全員同い年なので、かなりエモい。エキシビションに参加できるらしい。しばらく時間が空いたので、解説を読んだりコードゴルフをしていた。

Hは非ゼロの辺の重みを求めるのではなくゼロの辺の重みを求めることにすれば通常の遅延セグメント木で実装できたらしい。そのようにして提出すると最短コードになった。

コードゴルフについて。Aは最初に提出したdcの7Bが最短。解説にも同じコードが書かれていて面白かった。Bはコンテスト中のコードを少しだけ変えた。この辺りは実行してみながらでないとわからず、コンテスト中にそのようなことをする暇はなかった。CはAWKかと思ったが、普通にdcで書けた。Dはコンテスト中にdc 24Bを出し、さらに数分使って縮まないか試していたが、縮まなかった。

エキシビションは画面をYouTubeで配信しながら参加した。今見返すと、喋ろうと思っていたことの殆どは言葉になっていない。「あ！」とか「ええ〜」みたいな、なんの意味もない音を発するのが精々だったようだ。

heno239さんも配信していた。E869120さんは後日、編集した画面録画をTwitterに公開した。

www.youtube.com

FAならば点数2倍、というルールをほとんど無視していたのがよくなかった。また一番のプレイミスとしては、B問題のWAを終盤まで放置していたことが挙げられる。これは、問題に対して少し面倒であるという印象を抱いていたため、どこがWAなのかすぐには見つからないだろうと考えていたこと（実際はそうではなかった）、また序盤の問題であるからすでにFAは取られているものと考えていたこと（順位表を見ればまだ解かれていないのは分かっただろうに）の2点が理由であった。唯一解かれなかった問題、Semi Common Multipleは非常に難しい。そもそもこれを15分で解けと言われて解ける人も限られるのではないだろうか？僕は無理だ。考察も覚えていなかった。

コンテストが終了してからはずっとエゴサをしていた。ABC過去問から出題されるのは僕にかなり有利な戦いである、という言説には同意できる。フォロワーが50人以上増えたのにはびっくり。

結構疲れているのでTCOもCSAもサボり、ラノベを読んでいた。まず「超高度かわいい諜報戦」。設定はよい、が、ストーリーはあまり好みではない。主人公の陰キャオタクへの擬態が完璧かつ徹底的すぎてむしろ読んでいてげんなりした。あと誤字や脱字が多い。

次に「精霊幻想記19」。前の巻で主人公が重傷を負い、この巻は代わりにヒロインが頑張る話。ストーリー上必要なのは理解できるが、本能は主人公の無双を求めている。ヒロイン等は敵を圧倒できているわけでもないので、もどかしさがすごい。次の巻からまた主人公のバトルが見られるらしいので、そちらに期待したい。

さらになろうを1作読み始めた。2時間半くらい読んで、午前7時半に寝落ちした。

https://ncode.syosetu.com/n7796fc/

04/18(日)

午後3時、目を覚ます。まだ眠いのだから二度寝すればよいのに、そこから3時間なろうを読んでいた。

途中、昨日のエキシビションのE869120さん視点の動画がアップロードされた。また、昨日のD問題が-1Bされた。やはりO9^7+を2回書くのは長かったようだ。自分でもどうにかしてまとめようとしていたつもりだったが、スタックの一番下に入れておいて必要になるたびに持ってくるだけで-1B。なぜ気づかなかったのだろう。確かスタックの一番下に押し込むコードは書いていた気がするが。

午後6時半くらいになってさすがに眠気がマズいことに気づいたので寝なおした。午後8時半起床。食事してARC117に参加した。

Aは面倒だがまあよい。Bはちょっと難しいがちゃんと考えるとわかる。Cは変換テーブルをどうにかして簡単な式で表せないか考えるのは典型で、ガチャを回して一発で(-a-b)%3が出たのは大当たり。二項係数 mod 3を普通のmodintと同様に計算しようとして0になったのでしばらく悩んでいたが、そういうときの定理があることを思い出した。しかし「二項係数 mod」で検索してもmod 1e9+7しか出ない。最終的に「二項係数 偶奇」でLucasの定理にたどり着いた。Dは直感的には直径の端から端まで移動しつつほかの頂点を訪れる感じになる。順位表を見ると結構WAが出ているようだったのでしばらく迷っていたが、ええいままよと提出したら通った。証明：AC。

そのあとEを考えながら念入りに椅子を温めていた。まず全探索するコードを書いてみた。当然TLに間に合わないし埋め込みするのも時間がかかりすぎるようだったので、今度はvalidな移動における累積和のヒストグラムを全探索することを考えた。これもいろいろ場合分けしてすべてのvalidな移動を検出できるようになったが、やはり間に合わないようだ。残り10分くらいになってFを読んで牛ゲーだと思ってちょっと考えていたが、やっぱりダメだった。

結果は4完速解きで28位、パフォーマンス3033、レートは2670→2712(+42)。ずっと同じレート帯をウロウロしている。

コードゴルフ。A問題は、1..A * sum(1..B)と1..B * -sum(1..A)を出力するのがかなり頭がよい解法。B問題はPerl。sort{$a-$b}glob`dd`が`dc -e?f|sort -n`になるようで-3Bされた。CはN=3k+1のとき0番目、3番目、……、N番目を取り出したN=k+1の列と同一視してよいということを利用したコードを目にして、それを縮めた。これはなぜかというと、comb(3k,1)≡comb(3k,2)≡comb(3k,4)≡comb(3k,5)≡……≡0 (mod 3)だから。適当にPerlで書いていたらBWRを012のどれかにエンコードするところで更新された。