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

07/12(月)

先週の日曜日、週記を投稿してからの話。橙diffを1問開いて考えていたが、かなり面倒そう。目を瞑って細かい部分を考えていたら寝そうになったので、すぐ布団に移動した。午前8時就寝。

午後2時前に目を覚ます。二度寝しようと思いつつ布団でなろうを読んでいたが、今日も寝るのに失敗した。午後5時にあきらめて布団から出た。

atgolferを確認する。昨日90問追加されたにもかかわらずあまり更新が流れてきていなかった。1問、Crystalが縮んでいたが、これはto_i64をto_fに変えたものだった。確かにそうだ。Crystalの/演算子は結果を浮動小数点数で返すので、オペランドを整数にしておく必要はない。あんまり意識していなかった。これでほかのCrystalコードが縮まないかと少し試してみたが、縮まなかった。

しばらく他の人の日記を読んでから、大学院の入試について調べ始めた。確か出願が今週いっぱいだったはずだ。まだ何も用意していない。募集要項や出願書類自体はインターネットでダウンロードできるようだが、教務課で紙の冊子を配布しているそうなので、念のためもらっておきたい気持ちがある。また出願書類が家のプリンターで印刷したペラペラのコピー用紙というのも格好がつかないだろうという考えもある。明日はこれをもらい、ほかにも家の外で行うべき様々なことをする日にしたい。

午後7時くらいになって学食の夜の部に行った。今日はソースカツ丼とカレーを注文。1つだと確実に足りないので、まだ今日1食も食べていないことを鑑み、2食ぶんの購入に踏み切った。結果から言えばこれは正解だった。何とか満腹中枢が刺激される前に食事を完了できた。

家に帰ってちょっとYouTubeを眺めていた。ヒカキンが一人焼肉をする動画がおすすめされたのでしばらく観ていたが、焼けた肉を網の上から取るのにちゃんと箸を使っていて感動した。僕はこれを怠った結果、夜中に腹痛で救急車を呼んだのだった。

www.youtube.com

生肉を網に移したのと同じトングで焼けた肉を皿に移すのもいけない

日記（2020/11/06）あるいは僕が深夜に救急車を呼んだ話 - kotatsugameの日記

YouTubeを見るのはそこそこで切り上げたが、そのあともTwitterのTLをボーっと眺め続けるなど、意味のある行動をできていない。とりあえず風呂に入って、橙diffを1問通した。これは昨日寝る前に考えていたものとは別の問題。

Submission #24185848 - AtCoder Regular Contest 065

考察は簡単。実装にあたって、区間に包含関係がないように整理するのが面倒だなと思ったが、上手い実装方針を選べた。これまで出現した区間の右端の最大値を持っておいて、毎回インクリメントできればしていくというのが、その区間内の文字種類を見るのも含めて上手く書けたと思う。

その後しばらくこの問題のコードゴルフをしていた。最初はRubyで書いていたが、特に速度面で問題があるわけでもなし、Perlに書き直したらグッと縮んだ。未初期化の変数だったり配列外参照をしたら0が得られるのがうれしいところ。

もう1問橙diffを開いて考えていたが、急激に信じられないほどの眠気に襲われた。洗濯機を回している最中だったが、これは耐えられないと思い、素直に布団に移動して就寝。午前0時だった。早寝。

07/13(火)

午前11時に起床。途中何回か目を覚ましたような気もするが、この時間まで寝ることができた。とりあえず洗濯物を干し、ゴミをまとめて出した。

ちょっとだけ院試の問題を見たりTwitterをしていたら午後1時を回った。昼の部が終わる前に学食に行こうと思ったが、昨日開いた橙diffが解けたので、コードを書くことにした。昼食は家で摂る。

Submission #24195772 - AtCoder Regular Contest 072

結構悩んでいた。変更前はよいとして、変更後が問題。変更したところでは、目的地に近づくなら任意の位置に進めるので、そのあとの入力でゴールできないような最も近い点の座標が分かればよい。実はこれは後ろから計算できる、ということに気づくのが本質。d_i=1なる最大のiについて、その入力以降でゴールできないような最も近い点の座標は2であると言いたいが、d_j=2なるj\gt iがあったらそれでゴールできてしまうのでは？と思っていた。実際は、iで2から1に動いてしまうので、jの入力でもゴールできない。

ゴールできない点を計算する式は頭で考えたものが間違っており、サンプルが合わなくて困惑したが、紙に書いたら分かった。

食事してシャワーを浴び、久しぶりに原付に乗って山のキャンパスに向かう。昨日の予定通り、出願書類などをもらいに行く。僕が原付に乗っていたのは主に2019年の後期だったから、原付といえば吹き付ける風の寒さに震えている印象しかなかったが、夏の原付は風が涼しくて非常に気持ちがよい。微妙に曇っていて日光が強くないのもよかった。

教務課で院試の募集要項をもらう。次に数学科の資料室でゼミの教科書をコピーする。同じゼミの人々が大量にコピーするので教授に話が行き、コピー済みの資料が何部か配布されることになったという話は聞いていたが、1か月以上前のことであるからもう置いてないだろうと思って、コピーの申込書を書いていた。すると資料室の職員に「資料が配布された場所を確認しましたか？」「配布されたものの余りがないか教授に確認できないんですか？」「なんでその時取りに来なかったんですか？」など激詰めされ、困惑。資料を受け取れなかったのは完全に僕が悪いのだが、コピーの申込書を提出してからも何か言われたので、もう許してくれという気持ちになった。

山を下りて川内キャンパスに原付を停め、徒歩で地下鉄の駅まで行って、駅前の証明写真機で願書用の写真を撮る。このためだけに、Tシャツの上に羽織る襟付きの衣服を持ってきた。証明写真機の写真を撮ってTwitterに上げたところ、くっついている鏡に僕の姿が映りこんでいることを指摘されてびっくり。慌てて確認したが、顔の前にスマホを構えていたのでギリギリセーフ、か？

写真を撮って、今度は郵便局に行く。入試の検定料を振り込み、書類を提出する封筒を買う。すでに願書を出しに来ている人が結構いてビビり散らかした。検定料の振り込みは、後で書類に貼り付けるためにATMの利用明細票をちゃんと持っておかなければならないが、ペラペラの紙1枚に3万円を保証されるのかとわびしい気持ちになった。

購買で買い物をして帰宅。ちゃんと必要なものはすべて買い集めることができたと思う。あとは書類を作成して、郵便局で出すだけ。とりあえず調査票以外の何も考えずに書ける書類を作成した。大学受験の願書を書いていた時のこと、また当時どんな気持ちだったかなどを思い出してかなり気分が落ち込んだ。正直トラウマである。人はトラウマを増やしながら生きていく。

残すは調査票のみとなった。何を書いたものか全然わからないので、いったん後回しにして、午後8時からのSRM809に出た。EMの2完で18位、レートは2538→2535(-3)。ちょっと前までずっと上がり調子だったはずだが、いつの間にかこの順位でも下がるようになってしまったとは驚き。

Easyは昔のARCで見たことがある。解法も覚えていたので、それを再現するだけだった。

A - 掲示板

Medは3^NのDPを書いた。最大ケースで2secを超えてしまいびっくりしたが、__builtin_popcountをメモしておいたら1secを切るようになって助かった。実は2^Nにいくつかくっついた感じで解けてしまうらしい。Challengeフェーズの終わり際に一気に僕を含む3人に対して失敗している人がいたが、おそらく3^Nが落ちないかイチかバチかで試したのだろう。

昼に解いた橙diffのコードゴルフをした。Perl。入力が5\times10^5\times 2くらいあるので、いくら線形時間でも厳しいか……と思っていたが、なんとC++より速かった。一応endlではなく"\n"を使ったのだが、そもそもcin/coutが遅かったのだろうか。

TCO21のRegional Eventsへの招待メールが来たのでGoogleフォームを入力して参加登録しておいた。いつもはMサイズで出しているコンテストTシャツだが、毎回毎回着丈が長くてケツまでかかっているので、今回はSサイズで出してみた。もし変なサイズが来たところで、1回くらい構わんだろう。

もう1問橙diffを解いた。

Submission #24207952 - AtCoder Grand Contest 015

普通bitの問題といえば上のbitから場合分けすることが多いように思うが、この問題では下のbitで場合分けすることでうまく解くことができた。最下位bitを立てたい場合で、区間の右端の数が偶数の場合にちょっと場合分けが発生する。具体的には、区間の右端の数（を2で割ったもの）がそれ以外の数（を2で割ったもの）のORで作れない場合だけ答えが1減る。ORで作れない場合でも、それ以外の数と一緒にORを取った数についてはちゃんと最下位bitを立てることができる。

ところが、解説を読んだら上のbitで場合分けをしていた。上のbit「から」ではないこともポイントで、なんと場合分けは3通りにしかならないらしい。これで900点か……。最短コードもこの方針だった。試しに僕の方針でも書こうとしてみたが、明らかに想定解のほうが短い。粗があったのでちょっと縮めておいた。

改めて願書の調査票を書く。とりあえずコピーを取って、シャーペンで下書きのように書いてみる。計算機数学で出そうとしているが、ふと調査票の記入例に「理論計算機科学」というものがあることに気づく。Wikipediaで調べてみた限りだと、アルゴリズム論とかを指す言葉であるようで、これはかなり競プロに近いのではないだろうか。この方面で攻めてみたい。

表面は希望を少し書くだけで埋まるが、裏面の「興味がある数学の問題」と「進学後の抱負」はかなり悩みどころ。表面との関連を考えできるだけ競プロに近いことで埋めようとしているが、「なぜ工学部の院に出願しなかったのですか？」など聞かれると困る。英語の試験を受けていないからです……。ウチとは違うんじゃないの、と言って落とされるかもしれないのも怖いところである。

全然書きあがらないので、日記を書いて布団に入り、すぐ寝た。午前3時半だった。

07/14(水)

午前9時くらいに目を覚ましてしまう。すぐ二度寝しようと思ったのだが、うっかりスマホを触り始めてしまい、眠気が吹っ飛んでしまった。

そういえば、昨日のSRMでbit DPを書いたわけだが、1<<N-1とかk-1&rとかの記述に警告が出て、それを消すのに非常に苦労していた。このくらいの優先順位はわかって書いているので、むしろ謎の基準で警告を出されているように感じられ、どこを注意されているのかわからないため。と、このようなツイートをしたら、実は警告を消さなくても（Appletなら）コンパイルされて、提出もできるということを知った。知らなかった……。コンパイルエラーが出るのと同じような感じで表示されるとビビる。

昼過ぎ、学食に行った。本当はこの時間までに調査票を書き上げて、願書の発送まで済ませるつもりだったが、二度寝に失敗し続けていたので昨日から1文字も進んでいない。学食ではつけ麺を頼んだ。つけ汁に黒胡椒が効いていておいしい。最近見なかったメニューだが、タイミングが悪かっただけだろうか。

購買で買い物をしている間に数学科の同級生と会い、少し話した。やはり院試のことが話題に上がるが、そんなに不安視はしていないようで、お互い頑張りましょうという感じで別れた。この会話によって僕もそこそこ元気が湧いてきた。昨日までは調査票と、それをもとに質問されるだろう面接について悩んでウジウジしていたが、どうせ面接は10分程度のことだし試験ができていれば問題ない、という気持ちになった。調査票で悩むのはそこそこに留めておくべきだ。

家に帰ってきて、朝方メールが届いていた東北大学のワクチンを予約した。とにかくAtCoderのコンテストに被らないように、と月曜日を選ぶことだけを意識していたら、うっかり院試の直前に2回目の接種が予定されそうになって焦った。1週間遅らせることで対処。2回目の接種は院試後になる予定だ。ワクチン接種券というのが何を指すかよくわからなかったが、住民票を移していないのでどうやら富山の実家に届きそう。

最近本屋に行けていないし、これから先もしばらく行く予定はないので、大学生協で新刊ラノベなどを注文しておくことにした。17冊で14000円弱。生協の割引で1000円以上浮くはずだ。

調査票が1文字も進まない。うっかりYouTubeやニコニコ動画でスマブラの淫夢実況を見始めてしまった。動画を見るのを切り上げることができた後も、書く内容が決まらずうだうだしていた。ホスフィンからの情報によれば今セメスターで開講されている計算機数学Bではラムダ計算をやっているらしい。ちょっとClassroomにお邪魔して資料を見るくらいなら許されるようなので、見てみたりもしたが、本当にチラッと眺めた程度で参考になるわけもなく。

しかし昼間にもあんまり悩むべきではないという結論に至ったのだから、もうそろそろ本当に覚悟を決めねばならない。決意したらそこそこスルッと書きあがった。悩んでいたのは、主に「興味がある数学の問題」に何のアルゴリズムを書くかということであり、「進学後の抱負」は競プロの話をしていたら終わった。一応面接対策として書いた内容を写真に収めておく。

そのあと、封筒に宛名を書いたり書類をまとめて入れたりして、ついに願書が完成。郵便局で封筒を買ったときに貰っていた速達簡易書留の申込書も記入して、あとはこれを郵便局に持っていくだけとなった。結局今日の日中はすべて潰れてしまったが、完成することが第一。これが午後11時くらいのことで、30分後からECR111に出た。

Dashboard - Educational Codeforces Round 111 (Rated for Div. 2) - Codeforces

コンテスト終了時点では全完12位。

Aはできるだけ値を大きくしていきながら総和を求めて、ギリギリ超える場所を探す。Bはbの値だけ気にすればよくて、1文字ずつ分解するか同じ文字をできるだけまとめるかの2通り考えればよい。

Cから難しい。a_iについてa_j\le a_iなる最大のjとa_k\le a_j\le a_iなる(k,j)が存在するか、またこの2つの不等号を逆向きにしたものについても判定しつつ尺取り法をする。前者はセグメント木、後者はBITで、kを削除するときにjから1引くような実装で実現可能。実際には両方セグメント木で書いた。

Dは信じられないくらい難しい。a_i-iを考える。これを何らかのkについて\pm kにそろえることになるので、kとしてありうる値の数と符号の割り振り方を数える。負にする最小のインデックスと正にする最大のインデックスを固定して立式すると、2項係数と最小値関数の積になる。適当に場合分けして最小値関数を消し、負にする最小のインデックスのほうを変数xとしてみると、\binom{N-x}{M-x}やx\binom{N-x}{M-x}の和の形になる。これをWolframAlphaに投げると閉じた式になってくれたので、あとは正にする最大のインデックスを全通り試す。いちいちnの偶奇で場合分けしていてかなりヤバいコードになったが、すぐサンプルが合ってくれた。

Eは二分探索。判定については、先に達成可能なインデックスを求めておいて、巡回セールスマン問題のようにbitDPっぽくdijkstraをする。よく考えたらbitDPのままでよかった。

Fも二分探索。今度は並列二分探索をした。辺を全通り張っているとどう考えても間に合わないので、いくらか絞る必要がある。これについては、自分の左右の頂点から辺を張るよりも短くできるような辺（これは区間になる）と、その左右1個ずつを見ておけば通った。

コンテスト後のTLで他の解法をいろいろ見ていた。A問題は交差2の等差数列になるが、これの先頭からの和はある平方数になる。よって答えは\left\lceil\sqrt s\right\rceilになるらしい。Cは、実は長さ5以上の列が必ず条件を満たさないということが確認できるので、毎回愚直にチェックしながら尺取りしても間に合う。DはLaycrsさんの解法がシンプル。kとしてありうる値を座圧するという話もあって、腑に落ちた。

Rubyのコードゴルフで新手が出た。入力の1行目を読み飛ばし、2行目以降にmapを適用するようなコードは、injectで代替できる。適用できるものを探して縮めておいた。

atcoder.jp

午前4時就寝。明日は早く起きてゼミの前に郵便局に行かなきゃな、と思っていたが、寝る直前になって明日のゼミが休みだったことを思い出し、心地よく眠ることができた。

07/15(木)

午後0時半起床。昨日縮めたコードのうち1つに粗があって縮められていた。ブロックの最後で評価した値をそのまま返せることは、先に掲出した提出でも利用されているが、見落としていた。悔しいのでしばらく考えていたら縮んだが、代わりに学食の昼の部が閉まってしまった。

昨日のECR111はopen hackingフェーズも終了し、まだ落ちていないようだ。この後hackケースを追加してシステスがあるのかとも思ったが、よくわからない。

郵便局に行って願書を発送し、購買でパンなどを買って帰ってきた。家で食事し、荷物を整理してゲーセンに向かう。

今日も午後3時から夕食を挟んで午後11時半までみっちりプレイした。チュウニズムデュエルが1日で終わってしまった（ところでキャラのイメージとCV：釘宮理恵がミスマッチすぎる）。5月頭にホームにしていたゲーセンが潰れてしまったため、今通っているゲーセンは微妙に遠くなったのだが、そのせいでせっかく一度行ったのなら目いっぱいプレイするべきだという認識になってしまい、毎回閉店までプレイし続けている。

今日の成果は上々。13+のSSSが1つ、13のAJが6つ増えた。

先々週頑張っていたもの。

Halcyonをプレイしていたのだが、3時間くらい連奏しても出ずに閉店時間となってしまった。

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

先々週の週記ではツイートを引用してタップスライド（25、90小節）について触れているが、その部分は確かに一度手を離してちゃんと擦ることで驚くほど通るようになった。今日の最初のほうは、週記の記述を完全に忘れて親指やら人差し指で擦ろうとしていたが、大きな間違いだった。

あとはラスト、特に105小節の右手拘束交互も先々週非常に苦労していたところ。ここについては、意識的にスライダーに顔を近づけて判定線と手元を睨みつけるようにしたらかなり安定した。結局、先々週の時点でこれら合計3か所が通るかどうかというところまで持っていけていたので、安定してしまえばAJはすぐ出た。

今日3回で出た。意味不明。何もかもが上手くいった。ほとんどの部分は見たまま押していた（これができるようになっていたことが成長）が、これまでのプレイ経験から意識していたことや運指は一応ある。

17、25小節にある速い交互は擦る。これはリズムが良く分かっていないから、また緩急の差に対応できないからで、それ以外にもこの速度（32分）の交互は擦っているが、あとのほうに出てくる24分はある日急にできるようになったので押している。

48小節は前まで右手のリズムを意識していたが、それは直前2小節とまったく変わらないのだからむしろ左手を意識するべきだと考えてやってみたところ、上手くいった。

f:id:kotatsugame:20210717054156p:plain
97小節

逆餡蜜という話は聞いていたが、そのまま階段として押そうとして、結果ここで大量に出してしまっていた。逆餡蜜と見て擦るのが正解、のはずだが、そもそもこの運指を試した一回目でうまくいってSSS達成してしまったので、まぐれ当たりの可能性を否定できない。

これで解禁済み13+の未鳥は4譜面、パッソ・ハーレ・神威・大鳥居。全部定数13.9だ。13.8以下は全鳥ということになる。

帰宅してシャワーを浴びたら日付が変わっていた。酷使した腕が痛むが、そもそもここまで長時間プレイし続けられているのも成長で、自分の脱力意識はある程度の成果を見せているはず。

数理統計学の講義資料を3回分くらい読んだ。正直あんまりよくわかっていないが、式変形は追ったつもりなので講義資料はこれで完走できたとしてよいことにしよう。期末課題が出ていて、期限ももうすぐだが、今日は講義資料を読むだけにしておく。

うっかりまたスマブラの淫夢実況を見始めてしまう。以前見た覚えのあるシーンがもう一度見たくなり、どの動画だったか探して一度見た動画をもう一度見返すフェーズに入ってしまい、そのまま3時間が経過した。ちなみに探していたシーンは無事見つけることができた。この動画の4分29秒から始まる対戦で使用される御伽原江良の語録と、

nico.ms

この動画の4分46秒から始まる対戦で使用される自分を大蛇丸と信じて止まない一般男性の語録が見たかった。

nico.ms

午前6時半就寝。

07/16(金)

正午くらいに目を覚ます。追跡サービスで昨日の願書が大学に到着していることを確認した。二度寝するつもりでゴロゴロしていたが、失敗。午前中に届いていたメールで水曜日に注文した本が大学生協に届いたことを知り、受け取りに行くことにした。大量なので、高校の時に使っていたサブバッグを持っていく。競プロ合宿に行くときに着替えを入れたりもしていたが、最近とんと使っていないので、埃が積もっていた。

かなり重かった……。サブバッグで肩に斜めに掛けながら自転車に乗ると、本が入っている場所が腰や自転車に擦れるので、できるだけ片手を開けて支えるようにしながら持って帰ってきた。

安くなるのはいいのだが、大学生協で本を買うとよく微妙に角が潰れていたりするので、かなり気になる。生協の本の扱いが雑なのかとも考えたが、どちらかというと本を1冊1冊扱うことによる傷という感じがしてきた。本屋で平積みになっている本の下から掘り出したりするのが、状態的には一番良いのだろう。

invertは七夕あたりに出た相沢沙呼さんの新刊。せっかく大きな本で買うのだから初版本が欲しかったが（といっても現在の流通量で初版本に価値があるかというと……）、確認したら再版だった。Twitterで、発売日前にすでに再版が決定しているというような話は見聞きしたので、横着せずリアル本屋の在庫を狙うべきだった。

サークル解説会の準備をする。今日はABC209。CとDの解説スライドを用意した。Cをどのように思いつくべきか、というのはなかなか難しい話であるように感じられる。つまり、自分のコンテスト中の思考をうまく言語化できない。方針ガチャで当たりを引かなければどうしようもないと思っているため、これが灰diffというのには驚かされたのだった。

E問題の解説を行ってくれた人がいた。文字列の末尾3文字に対応する頂点を特別作らないことによって、探索の始点=ゲームの終点を1点に絞るのは面白い実装方針であると思った。

2021/07/16 定例会 | puzzleknot 公式サイト

毎週Google Meetの会議リンクを生成して、解説会の直前にSlackに貼っている。これは何とかしたほうがいいかもしれない。来週の解説会からは固定されたリンクで活動できるように準備しておきたい。

yukicoder 304に出た。全完。

yukicoder contest 304 - yukicoder

Aは、実はグリッドの左上と右下に半々に人を配置するのがよい。これは2人の時は明らかで、3人目をどこにおいても値が変わらないことを確かめ、4人目に思いを馳せるとわかりやすい。Bは先頭から貪欲に揃えていく。どこから揃えようとしても、結局必要な操作回数はあまり変わらないように感じた。これは解説でうまく説明されていて、逆順列を考えると隣接swapによるソートに帰着されることからわかる。Cは行列のサイズを有向グラフと見て、始点と終点が決まるか、大きなループになるかを調べればよい。Dは列を鳥で分割すると、合間にどちらの動物を詰めるかでdpができる。Eは二分探索。

Fは面白い。いつものように蟻がすれ違うと読み替えておく。最後に落ちる蟻の時間と端を固定したとき、向きが決まる蟻と自由な蟻の2種類に分かれる。向きが自由な蟻のうち何匹が左向きか（あるいは右向きか）を固定したとき、右から落ちる蟻と左から落ちる蟻の数がわかって、この状態で元の問題に戻ると、蟻の順序が変わらないことから左から何匹目の蟻が最後に落ちるかがわかる。最後に落ちる蟻を決めるのと、向きが自由な蟻を考えるのでO(N^2)。Gはいったん?を無視して考えると、実は（全部?の場合以外）その時の操作回数が達成できる。具体的には、最後の操作で消される文字列を計算して、間にある?を直前の文字（存在しない場合a）に揃えるようにすればよい。これで、すべての?は最後の操作に巻き込まれて消える。その前に消えてしまうかもしれないが、ともかくこれが辞書順で最小なのでよい。

買ってきたラノベから1冊読んだ。「お隣の天使様にいつの間にか駄目人間にされていた件」5巻。非常に良い。Web版のころからこの辺りの展開は本当に好みであった。以下ネタバレになる。

4巻のラストでヒロインが公開告白もどきを行う。ここまで焦れったかった関係が確定するのもよいし、それまであまり目立たなかった主人公が一気に注目されるようになるのもかなりドキドキした。4巻はそこで終わって、5巻の冒頭からその後しばらくの学校生活が描かれる。これまで主人公は、ヒロインとお出かけするときだけ髪をセットし、ヒロインの隣に立っても恥ずかしくないような恰好になっていた。ついにこの度ヒロインと交際を始めたということで、学校でもその恰好をするようになって、いきなり格好よくなった主人公に対する周囲の反応がまたいい感じでニヤニヤできる。

読んでいる最中、あまりの良さに耐えられなくなり、精神の安定を取るためしばらく院試の問題を眺めていた。院試を解くゼミが発足して、そろそろ第1回目が近づいている。僕に割り振られた問題を解いておかないとそろそろヤバい。しばらく考えた感じ、まあまあ解けそうだったので、安心して読書に戻った。

ラノベの新刊チェックをする。「転生ごときで逃げられるとでも、兄さん？」の2巻が出るらしい。1巻がかなり面白かったのだが、1年以上続刊が出なかったので打ち切りかと思っていた。作者が忙しすぎたのだろうか？ほかにもいくつか新作をほしい本のリストに追加していたら、また来月も20冊ペースになってしまうようだ。大量に本を買うのは楽しい。願わくば、このようなお金遣いをずっとできるような生活をしたい。

日記を書いて布団に入り、午前6時半就寝。

07/17(土)

午後2時くらいに目を覚ます。布団でしばらくYouTubeやニコニコ動画を観た後、ラノベを1冊読んだ。

「幼馴染で婚約者なふたりが恋人をめざす話」2巻。1巻からあんまり合わない感じはしていたが、2巻でその印象を強めた。出てくる女の子が怒るときの描写がいっつも「怖い笑顔」系統なのが肌に合わない、と思ったが、そのような描写は別にこの作品に限らないことに気づいた。ここまで癇に障るということは、坊主憎けりゃ袈裟まで憎いということで、そもそもキャラたちの性格が気に入らなかったのだろうか。

午後6時くらいに二度寝に入り、午後7時半に目覚ましで起床。睡眠時間は1時間半の倍数が良いという話を昔に聞いて、今でも意識しているが、そのようなことは関係なく1時間半で起きるとクソ眠い。

第7回PASTが終了したようなので、過去問公開を待ちながら院試の答案を作成していた。結局公開されずABC210の時間になったので、出た。全完26位。

AtCoder Beginner Contest 210 - AtCoder

A問題はちょっとした場合分け。kコマンドを使えばdcでもかなり簡単に書けそうだが、ちゃんと縮めきるのは難しいように思う。Rubyで通して、ゴルフは後回しにした。B問題は制約が優しい。とりあえずPerlで@-を利用しちょっとだけ縮めておいた。C問題から面倒なのでC++を使う。適当にmapで管理して、毎回ちゃんと要素をeraseすることで要素数も得られる。

Dはかなり難しく感じた。下の行を固定すると、上の行からその行まで一直線に下りてくるときの（駅の建設費用も含めた）最小コストは上から順に求まる。このもとで、今固定している行内の2点を選んで同じ問題を解けばよくなる。実際に解くには区間add・区間minの遅延セグメント木を用意して、自分の左右に分けてコストを足したり引いたりしながら求めればよい。Eは簡単。操作iを使って目一杯操作すれば連結成分の個数がN\rightarrow \gcd(N,A_i)になるので、N=1となるまでC_iの小さい順に使えばよい。

Fは面倒。2-SATに落ちるまでは良いが、辺の数が大爆発する。実はそれぞれ直前の要素との関係ぶんだけ辺を張るだけで再現できたりしないか、と思って実装してサンプルを合わせたが、当然のようにWA。適当な超頂点を用意するにしても、意図せず自分から￢自分に辺を張ってしまったりして、まずい。この時点で「区間に辺を張るテク」のことは思い浮かんでいたが、さすがに面倒すぎるのでしばらく別の方法を考えていた。残り時間が40分くらいになって、諦めて区間に辺を張るテクを実装する。自分のライブラリのセグ木を参考にしたら以外と簡単に書けた。うっかりセグメント木ぶんの辺を張り忘れてさらに1WAしたが、何とかACできた。

Dは数値を106個読み込ませていて、なかなか攻めている。Fはもっと頭が良い辺の張り方があったらしい。

コードゴルフ。Aは残り時間を使ってdc 17Bを書いておいた。X(N-\max(N-A,0))+Y\max(N-A,0)。Bはsedで書くのが短い。CはPerl→AWKに書き換えた。EはRuby。ソートをbashで行うことも考えたが、入力の1行目だけ取るのが難しくて諦めた。

CF #733 combinedに出た。6完48位、レートは2843→2852(+9)で微妙に最高値を更新した。

Dashboard - Codeforces Round #733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine)) - Codeforces

Aは数字列と見てmax。Bは適当に貪欲に詰めても良さそうだった。自信が持てないので、提出する前に適当に縦横の偶奇をいろいろ手で試していた。Cは勝つまで試合数を増やしていってもよい。O(n)回で解が見つかる。Dは貪欲にマッチングしたあと、余りも貪欲に詰め込む。最後に自己辺が残る可能性があるが、これは条件を満たしている頂点から適切に選んで行き先をswapすればよい。見た目に反してかなり簡単だった。

Eは最初辞書順最小を見落として1WA。次に、答えを必ず1以下にできることに気づかず1WA。答えを1にするときは、aababacacaのように詰めるか、abaaaaaacbcのように詰めるかの2パターンあって、どちらも辞書順最小の文字を先頭に持ってくることができる。abbaaaaに注意。

Fはよくわからない。1マスずつ決めるdpの計算回数を適当に見積もると、持つべき情報が列が揃っているか・2本の対角線が揃っているか・今の列が揃っているか・これまで揃った列が存在するかの25bit必要になってしまった。ここから少し減らす。まず、揃わない確率を計算すれば、これまで揃った列が存在するかの情報は必要ない。次に、列ごとにdp配列を保存しておいて、1列終わった段階でその列が全部揃う場合の遷移を抜くことにすれば、今の列が揃っているかの情報も必要なくなる。これで23bitになって、2^{23}\times 21^2\approx 4\times 10^9。気合を入れたら行けそうな気がしないでもない。

実際はかなり時間がかかってしまうようだった。まずmodintを書かず、直接modを取ることにする。これだけで結構希望が持てる時間になったのではなかったか。あとは遷移をいじる。遷移は、行・列によって決まる特定のbit（3つ以下）をそのままにするか一気に落とすか、という風に読める。よって、関係するbitだけ取りだし、他のbitで部分集合を走査して毎回計算することにしてみた。ほかにdp配列をin-placeに更新するようにしたりして、多少は速くなったが、むしろ部分集合dpにしてしまったことによってこれ以上の高速化が望めなくなってしまった。

ここで、消えるbitが3つ以下であることに注目する。どれが消えるかで場合分けし、それ以外のbitを上位桁からまとめてループすることで、一番内側のループにベクトル化を効かせられないだろうか。とりあえずゴリゴリ場合分けしたところ確かに速くなった。手元では間に合うくらいの時間になったので、以降こどふぉのコードテストに移る。こどふぉではまだ間に合わないようだ。そこで、一番多く入る場合分けの部分にさらに手を入れた。具体的には、ループを分割し、毎回の演算を軽いものにする。また、in-placeに更新していたdp配列を一度別の場所に移し、計算順序を任意に変えても問題ないとわかりやすくした。これで最大ケースでも7秒に間に合うようになったので提出、AC。

Submission #122848521 - Codeforces

システスを見つつ、明日に迫った院試ゼミに向けて答案の作成を再開する。昨日は案外解けるな……と思っていたが、実は全然解けていなくてびっくりした。

熨斗袋さんからファンアートを頂いた。嬉しいのでカラーで印刷し、部屋の壁に飾っている。

院試は、担当する問題2つの最後の大詰めが解けないまま、午前8時に就寝。

07/18(日)

午後2時起床。寝ている間にいくらか考えが整理され、ゼミの開始までに何とか回答を作成しきることができた。

午後3時から午後7時半までゼミ。非常に有意義な時間だった。あと、自分が思ったよりヤバそうであることに気づいてちょっと焦る。あと1か月で仕上げていきたい。

途中、第7回PASTの問題が公開されたので、最初の数問を通しておいた。この辺りはたまにコードゴルフが自明な問題があって、激戦区。とりあえずE問題まで読んだ。ACEは面倒そうだが、B問題は\min\left(\frac A B,C\right)、D問題はsedで一発だった。どちらも取れて満足。Eもゼミ中に縮めていた。

ゼミが終わってからしばらくAとCを縮めていた。午後9字からARC123に出た。

AtCoder Regular Contest 123 - AtCoder

5完18位、パフォーマンス3178、レートは2774→2821。赤コーダーになった。

A問題はちょっと難しい。場合分けで攻めようとしたが面倒に感じ、しばらく考えていたら、A_1+A_3-2A_2=0という式に気づけた。

B問題は簡単。直感的な解法としては、次のようなものが思い浮かぶ：3つの列をそれぞれソートし、Bを見つつ先頭からAとペアにし、相手が見つかったものを残す。こうして残った要素を新しくAとし、B\leftarrow Cとしてもう一度繰り返す。これで正しいことも簡単に確かめられる。つまり、これで残る要素を残さないことで得しないことが言えればよくて、これは要素数の面でも、値の大きさの面でも小さいものから貪欲に取った時が最適になることから従う。実装も同じことを2回する部分をループにするといい感じにシンプルになる。

C問題は桁dp。答えの最大値は、それぞれの桁で3ずつ引いていくようなことを考えたとき、3×18でだいたい60くらいあれば安心だろう。答えを1ずつ増やしつつ桁dpでチェックする方法を実装してみたところ、サンプルは合うようだが間に合わないので、いくつか並列で計算する。61回bool値のdpをするので、long longに情報を詰め込むことで一度にdpできる。また遷移を少し工夫することで、簡単に間に合うような計算量に落とすことができた。ちゃんとサンプルも合ったままだったので安心して提出、AC。

D問題は最初、Bが必ず非負の数になる！と思い込んでしまった。このとき、B_{i+1}=B_iとC_{i+1}=C_iのどちらかが成り立つことはかなり簡単にわかる。それで実装したらサンプルが合った。あまりにすんなり書けたので疑って順位表を確認したところ、結構通っていたので自信を持って提出、WA。残念！しばらく考えると、先ほど考えていたことが大嘘だったことに気づく。しかしこれは良い点もあった。B_{i+1}=B_iとC_{i+1}=C_iのどちらかが成り立つことはまだ成り立ちそう。先ほど考えなかったB_i\le 0\le C_iのときが怪しいが、このときは数列の先頭のほうから押し縮めていくようなイメージでわかる。このとき、B_0の値を変数とすると、それ以外の値はすべてB_0に適当な値を足し引きしたものとなる。それらの絶対値の和の最小化をするには、いつもの中央値とすればよい。これでACできた。

DのAC時点でもそこそこいい位置につけているが、Eがたくさん通されるとまずい。実際floor_sumが効きそうでそれなりに通されそうな見た目をしていたので、頑張って考える。あまり考察がまとまらないまま、やっておいて問題はないだろうと思ったこと、つまり適当な場合分けと、あとは{\rm lcm}(B_X,B_Y)の倍数だけギリギリまで動かしておくことを実装した。しかし問題そのものは変わっていない。

場合分けしてB_X\lt B_Yとしている。このとき、f(n)=\left\lfloor\frac n{B_X}\right\rfloor-\left\lfloor\frac n{B_Y}\right\rfloorが特定の値になるようなnを求める問題だった。ここで、f(n)の値はそう簡単に減らないことに気づく。一度-1されたら、次は必ず+1されるという意味。このとき、f(n)=Kとなる最小のnとf(n)=K+1となる最小のnの間では、f(n)の値はKまたはK-1であることがわかる。そのような範囲は二分探索で求めることができて、範囲内では2通りの値しか取らないので、f(n)=Kを満たすnの個数はf(n)-(K-1)の総和に等しい。これはfloor_sumで求めることができる。やっとfloor_sumに帰着することができた。

最初に書いておいたコードは、場合分け以外は必要なかった。実装して提出するとWA。範囲を二分探索で求めるところにミスがあった。直接nを求めるとf(n)が単調でないためWAとなるが、実は求めるnはB_Xの倍数なので、それだけ調べれば単調性が表れそう。すぐに修正することができて、今度こそACした。残り時間はFが結構絶望的だったので、コードゴルフをしていた。こうやって諦めるのはあまりよくないんだなあ。

コードゴルフ。A問題は適当にdcで解いておいた。B問題はRubyで、うえで説明した解法だとinjectが効く。

かなりうまくいったので、もしかしたら赤になれるかもしれないと思っていた。実際のレート更新が来るまでは自分がどうなったか知りたくないので、predictorの結果がツイートされている可能性のあるTwitterは開かないようにして、PASTの問題をいくつか解いていた。Hは適当な嘘を何度か投げた後、1004のdpを投げたら通った。浮動小数点数を扱っているし、そこそこ攻めた制約に感じられる。コードゴルフとしては、FはPerl、IはRuby、Jは取り合えずALPCのSCCの最短コードを移しておいた。networkxの関数をいくつか試していたが、どれもTLEしてしまうようだ。

午前0時半くらいにレート更新が来て、赤になっていることを確認した。

しばらくPASTのコードゴルフをしたりTwitterしたりした後、午前3時くらいから色変記事を書き始めた。前々から、色変記事を書くときはGoogleフォームで質問を募集しようと思っていて、実際に行動に移したのだが、ありがたくも公開時点で59個の質問が集まっており、書くのにかなり時間がかかった。

kotatsugame.hatenablog.com

記事を公開して布団に移動し、午前8時半就寝。