05/17(月)

先週の週記を投稿してから、また寝ずに月曜日を過ごした。

まずALPCのConvolutionでゴルフをしていた。Rubyの多倍長整数を使って、16進で20桁ごとに数値を埋め込むと、掛け合わせても20桁から溢れないので、復元できるということらしい。そういうテクの存在は認識していたが、以前確認した時には何やらTLEが取れていなかったはずだった。今見るとACできていたので、自分も同様のアルゴリズムで書いて、縮めておいた。わざわざ16進数で埋め込んでいるのは、.to_iより.hexのほうが短いという理由だ。

atcoder.jp

「転生したらスライムだった件」の本編を読了した。

https://ncode.syosetu.com/n6316bn/

非常に面白い。累計ランキング1位は伊達ではない。これから数十話ぶんの番外編があるので、非常に楽しみである。本編完結後の、何の憂いもなく無双できる番外編は、非常に体に良いことで知られている。

眠気をこらえて典型90問の公開を待ち、解いた。今日は単純なdpで、Perlで縮めていたのだが、一瞬でdcの38Bが出て勝てなかった。現状自力では43Bにとどまっていて、大きく差をつけられている。この長さで5B差がついているのは、何かアルゴリズムの違いがあるのだろうか。スタックにdpの履歴をためているが、最初に9個以上の0を入れたり、また引き算した後のmodを取ったりするところが長ったらしく感じられる。引き算はどうしようもないか？

その後別の問題の最短コードを眺めていたが、眠気に耐えかね、布団に移動。ラノベを読んでいたが、午後8時半就寝。今週からサークル活動の曜日が変更になり、解説会は金曜日に移動した。

05/18(火)

午前3時半くらいに目を覚ましてしまう。典型90問のコードゴルフが更新されていたようなので、縮め返した。これで目がさえてしまったので、なろうを読み進めていた。

「転生したらスライムだった件」の番外編を読了した。相変わらず面白かった。ただ、2つの中編はどちらもリムルの本領がクライマックスまで発揮されないタイプの話だったので、そのぶんのカタルシスはあったものの、やや物足りなかった。もっと読みたいものだ。書籍版を買えばいいのかもしれない。

その後布団から出てコードゴルフしたり、サークル宛てに来ていたメールに返信したり、ゴミを出したりした後、午前10時半に再度寝直すことに成功した。

午後3時半起床。夕方からたいぺーと外食する予定があるので、寝なおす必要があったというわけだ。学食は今の時間開いていないが、購買はやっているので、そこでカロリーメイトをしこたま買い込み、ついでに以前注文した本のうち届くのが遅れていた最後の1冊を受け取った。大学近くの郵便局で原付の軽自動車税を払おうとしたが、窓口が午後4時で閉まってしまうらしく、これには失敗した。

夕方、ラノベを読んでいたら、たいぺーが家に来た。本来はすぐ外出するはずだったのだが、今日の分の典型90問がまだAtCoderに出題されていないため、それを待つことにする。たいぺーを放置してしまうことになるが、僕の本棚を眺めたりして暇をつぶしていたようだ。

待っている間にラノベが読み終わった。「恋は双子で割り切れない」。最近Twitterでよく広告ツイートを目にする。そんなにプッシュされるということは面白いのだろう、と期待して読んだが、正直期待外れだった。双子がいて、両方に好意を寄せられている幼馴染が主人公で、その3人の関係性を描く話。設定はそのような感じだが、キャラ付けのつもりだろうか、視点人物によって地の文に含まれる語彙がかなり難しくなって、ストーリーに集中できなかった。他のラノベから固有名詞を借りてくるとかなら同じラノベとして面白く読めるだろうが、僕の知らないSFとか海外の古典の固有名詞を持ち出されても困る。そういうのは一般書でやったら良かったのではないだろうか。わざわざラノベでする必要性は感じられない。固有名詞だけではなく日本語の語彙でも知らないものがあったが、それは僕の落ち度なので頑張って調べながら読んだ。

読み終わるのとほとんど時を同じくして、典型90問がアップロードされた。サクッと解いてAC、ゴルフは面倒そうなので放置していよいよ外出。仙台レジャーランドが閉店してしまったので、違うゲーセンに行くことを念頭に、その近辺でラーメン屋を探してみたが、どれもピンと来なかったので、結局駅前までズルズル歩いてつけ麺屋に入った。僕は結構来ているが、たいぺーは初めてらしい。なんとなく2玉ぶん注文してみたら、思ったより多かった。つけ汁が早々に冷え切ってしまったが、つけ汁温めサービスがあるのか謎だったので、結局冷たいまま食べていた。熱盛にしてもらえばよかった。

店内で最近話題のアニメOPが流れていたが、歌詞に聞き覚えがなかったので、さては2番だな？と思い、たいぺーにそのことを話した。この際、歌詞の2番のことを方言で「2題目」と言ったところ通じなかったので、大変びっくりした。こういう方言っぽくない（と感じられる）方言はわかりにくいし、使いがち。例えば小説など読んでいても、特にキャラが方言を喋っていることを意味せず「腹がくちくなる」「物を（あるべきところに）なおす」というのが出てくることがあるが、意図せず出てしまった作者の方言だなあと感じながら読んでいる。

食事して少し本屋に寄ったあとゲーセン。しばらくたいぺーとマッチングして、フルチェインが出たりした。たいぺーが帰宅してからはアップデートで追加された曲を埋めていた。Lv.12のOPが99.50%に乗ったほか、追加された13+の両方でSSSを達成できた。運指が固まっていないうちに出てしまい、スコア的にはあんまり納得がいかないが、特にWizdomiotについては発狂が信じられないくらい上手くいった結果のスコアだから、これ以上はそうそう伸びないだろうという予感がある。

Lv12のスコアを詰めていた。スコア的には全体で1000点以上増えたはずだが、OVER POWERのパーセント表示は微動だにしない。99.50%を目指しているが、数値的にいくつになればよいのかが全然わからない。
週記（2021/04/26-2021/05/02） - kotatsugameの日記

Lv.12のOP、99.50%になってた！ pic.twitter.com/axDEibcbp6
— こたつがめ (@kotatsugame_t) 2021年5月18日

BATTLE NO.1 SSS
よくわからんまま乗った pic.twitter.com/ovYeQ87O5S
— こたつがめ (@kotatsugame_t) 2021年5月18日

Wizdomiot SSS
序盤のミス以外何もかも上手く行った。何もわかってない pic.twitter.com/Bz6ny9mYh6
— こたつがめ (@kotatsugame_t) 2021年5月18日

午後11時半、閉店時間になったので帰宅。途中で仙台レジャーランドの跡地に寄った。いつもならこの時間でも遊べたのに……。

pic.twitter.com/qSmoIlAqCc
— こたつがめ (@kotatsugame_t) 2021年5月18日

今日買った本はこれ。

今日買った本たち pic.twitter.com/tgHhFMWP0a
— こたつがめ (@kotatsugame_t) 2021年5月18日

夜中から朝方にかけて、ずっとコードゴルフをしていた。午前6時半就寝。

05/19(水)

午後4時ごろ、ふと目を覚ましてAtCoderを確認したら、典型90問の今日のぶんが公開されていたので、起きて縮めた。RubyだとunshiftとpopでrotateするのはTLEしてしまったので、まずCrystalで書いた。Crystalのdequeには、swapとrotate!というそのものズバリなメソッドが存在するようだ。その後、先頭インデックスを持つ想定解を思いつき、Rubyで通した。最後に、Perlだとunshiftとpopでrotateしても間に合うようだったので、それで書いたのが現在の最短となっている。午後6時に再度寝直した。

午後9時半起床。

「雪中の花は、軍神を偽る」を読んだ。かなり面白かった。異世界に転生して軍師となり、自軍を勝利に導くという話。異世界といっても中華風の異世界で、この辺りは富士見L文庫らしさを感じる（富士見L文庫は最近「あやかし」と「中華っぽい話」しか出してない気がする）。似たようなストーリーの話としては「数字で救う！弱小国家」というのを思い浮かべられるが、転移したらたまたま国の王女と懇意になって軍師になるか、軍神に憑依して軍師とあがめられるか、どちらが自然に感じられるだろうか。どちらも不自然と言われたらそうかもしれない。そういう設定上の不自然さはともかく、ストーリーは面白かった。主人公が男装女子であるという点も僕にとっては目新しく、新鮮。

続いて「才女のお世話」を読んだ。これも良い。まずみわべさくらさんのイラストが良く、これを目当てに購入したが、作品自体も面白かった。自活能力があまりないヒロインがかわいらしい。ラストでは財閥令嬢という設定が実態を伴って現れ、ハラハラした。

コードゴルフをしつつ、さらにもう1冊。「クラスの大嫌いな女子と結婚することになった」2巻。非常に良い。外面としては嫌いあっている2人の軽妙な掛け合いが心地よい中、内心で互いに惹かれあっていく様がもどかしく、微笑ましい。高校生夫婦という設定にも描写から現実味が感じられる。

さらにコードゴルフを続けていた。朝になって、典型90問の今日の解説が公開され、dequeが想定でなかったことを知った。dequeのランダムアクセスを定数時間で行うというのは難しいことらしい。僕はリングバッファによる実装を念頭にしていたため簡単だろうと思っていたのだが、実はC++においてもリングバッファではない実装をしているらしく、かなり謎だった。ちょっと調べたところ、STL一般についての要件を満たすための実装らしいが……。

午前9時就寝。

05/20(木)

午後0時半起床。目覚ましを3回くらい見送ったうえで気合の起床に成功した。ゼミがある。

先週の続きからということで、僕が先週終えられなかった分の発表をまず行うことになった。スライド自体はすでに完成しているので、今週はな～んにも準備をしていなかったのだが、するとスライドを作りながら話そうと考えていた内容が頭から吹き飛んでおり、ところどころ口が回らなかった。発表自体は何とか終えられたが、先週と同じページ数のスライドに先週の倍の時間がかかっている。これには、スライドの内容が少し難しくなったことも関係している。

今日の典型90問は最初、 $0$ から $2\times 10^{18}$ を二分探索する中で部分集合のdp $O(2^N N^2+N^3)$ を行って解いた。C++でも1.2secくらいかかっていて、スクリプト言語でのACは難しそう。ここで、TLによれば指数の底を2にできるようだったので、その方針で考えてみる。補グラフの $K$ 彩色問題に言い換えられて、これは検索すると $O(N 2^N)$ で解けるらしい。包除原理を活用する、と書いてあったが、具体的にどのように解くのかわからなかったため、さらに検索していると、解説しているスライドが出てきたので、それを見ながら実装した。さらに二分探索をやめ、答えの候補となる点対の距離 $O(N^2)$ 通りのそれぞれについて計算するようにしたところ、100ms以下と爆速になってくれたので、Rubyでの実装に移った。（実は、答えの候補を絞ったうえで二分探索することで $O(\log N)$ 回彩色問題を解けばよくなるようだ。）

現在の計算量は $O(N^3 2^N)$ で、 $N=15$ で計算してみるとまだマズい。実際 $N=15$ のケースではかなり時間がかかってしまうことが確認できたので、オーダーを落とすことになった。実は包除原理の箇所ではメビウス変換を行っており、このせいで $O(N 2^N)$ だったのだが、実際は配列の最後の値にしか興味がないため、適当に係数 $\pm 1$ を前計算して足し合わせることでも同様の結果が得られ、結果 $O(2^N)$ で $K$ 彩色問題が解けた。……解けているように見える。Wikipediaに書いてあるオーダーよりも良いものが得られてしまい困惑したが、 $N$ ビットの整数演算が $O(N)$ であると考えると、計算量は確かに $O(N 2^N)$ になる。そういうことだろうか。

コードゴルフすると253Bになった。

学食に行き、帰ってきて、すぐ布団に横になったところ、耐え難い眠気が訪れた。実際耐えられず、午後8時半に寝落ちした。

午前0時半起床。サークルのバチャを吹き飛ばし、CF div.2が始まってしまっていた。仕方ないのでベッドでゴロゴロしつつずっとなろうを読んでいた。この生活リズムの乱れ、つまり朝のほうに寄ってしまっている状態はあまり望ましくないため、無理矢理にでも寝ておく必要がある。午前5時くらいに眠気が来たので、すかさず寝た。

05/21(金)

午前11時起床。

syosetu.org

章題が「東方靈異伝」になっていた。ついに旧作突入らしい。感慨深い。

学食に行って、帰りに軽自動車税の支払いもしてきた。今日は成功した。

午後1時からAtCoderJobsで応募したインターンの1次面接があった。1次というのは、ここでは第一回というくらいの意味合いで言っていて、実際には異なる名前がついている。初めての面接なのにかなり主要なエンジニアらしい方に面接していただいて恐縮の限り。面接自体は好感触だったが、相変わらず自分が何をやりたいかということがよくわかっていないため、その点はあいまいで腑抜けた回答をしていたと感じる。そういうのは一回働いてみないとわからないと思っているので、何の準備もしていなかったが、こういう甘えた考えはいけないのかもしれない。直す気は……まだない。

予定通り1時間みっちりお話していただいて、終了。典型90問の今日の分が公開されていたので、とりあえず通して、少しだけ縮めてから午後3時くらいに家を出た。青葉山のキャンパスに向かう。卒業アルバムの写真撮影を行うためだ。事前にTLで質問したところ、顔面しか映らないためTシャツとジーパンで何ら問題ないらしい。

家を出てしばらく歩いてから、ひげを剃ろうと思って剃っていないことを思い出したが、後の祭り。しかしカメラマンさんはあまり気にならないと言ってくださったし、実際撮られた写真を確認してもあまり見えなかったので、卒業アルバムになったら解像度の狭間に呑まれて潰れるだろう。

この行き帰りはずっとスマホとにらめっこして典型90問のコードゴルフをしていた。方針がよかったのか、現状で（報告された中では）最短らしい。 $M=46$ とすると、最初は $O(N+M^2)$ で解いていたところを $O(MN)$ で解くようにしたら、大変短くなった。

帰ってきてatgolferを確認すると、以前Perl6でTLEしていた解がRakuで出すことで高速になりACする、というやつで1問縮められていた。慌てて、これまでPerl6でTLEしたコードをすべて探し、縮められるものを縮めておいた。

サークルバチャの時間になったので、参加する。今日はCF #492 div.1。サークルの活動する曜日が変更され、解説会は金曜日、バチャは木・金曜日になった。木曜日は午後9時からだが、金曜日は解説会に押し出されて午後5時半から。

https://codeforces.com/contest/995

A問題は解けなかった。B問題は、貪欲に左端から揃えていってよさそう。

C問題は、 $|x|\ge|y|$ なる点だけを抜き出し、 $|x|$ の降順にソートして2つ組にする。 $(x_1,y_1)$ と $(x_2,y_2)$ が組になったとすると、 $|x_1+x_2|$ と $|x_1-x_2|$ の小さいほうが得られるように符号をつけることにする。こうすると、あとは組ごとでどのように反転しても $|\sum x|\le 10^6$ となるようにできる。例えば $x_1+x_2$ となるように符号をつけたとすると、 $y_1+y_2$ が残るが、これの絶対値の降順にソートして貪欲に足したり引いたりすることで（組にした点の符号をずらさないようにしながら） $|\sum y|$ を最小化でき、具体的には $|\sum y|\le \sqrt 2\times 10^6$ になる。この $\sqrt 2$ は $|x|\ge |y|$ から出ている。

同様に $|x|\lt |y|$ なる点も処理し、最後にそれぞれからできた2つのベクトルを足したり引いたりして、答えとして適切なら出力するようにしたら、通った。しかしこれには反例があって、処理の後にできるベクトルが $(10^6,\sqrt 2\times 10^6)$ だと当然ダメ。具体的にそのようなケースも構築できてしまったが、コンテスト中なので気にしないことにした。バチャだとフルフィードバックであるということもある。

Dは面白かったが、かなりエスパーが効きやすそうな問題に見える。答えは値すべての平均値になる。自由度が小さいケースで確認してみよう。残り1bitが確定していない状況を考えると、先手は値が大きくなるように定め、後手は値が小さくなるように定める。この2つは一致しないため、残り1bitが確定していない状態の期待値は、含まれる2通りの場合の平均値になる。

残り2bitが確定していない状態から1bitを定めるというのは、残り1bitの状態の期待値は含まれる2通りの状態の平均値であるということを鑑みると、候補を2x2のマスに並べて1x2（あるいは2x1）マスを選ぶことに等しくなる。先手は、ここに含まれる値の総和が大きいものを選べばよい。逆に後手は、先手が選ぶのと真逆の状態を選ぶことになる。たとえば??から先手が0?にするとしたら、後手は?0でも?1でもなく1?を選ぶのが最適である、ということだ。これは、それより期待値が小さくなるような後手の選び方（例えば?1）が存在するとしたら、先手が逆にそれと真逆な状態?0を選ぶことで、0?より期待値を大きくできる（2種類の期待値の総和は必ず2x2のマスの総和に一致するため、min=sum-maxという要領でそのようなことが言える）ということからわかる。結局、残り2bitが確定していない状態の期待値も含まれる4通りの場合の平均値であることが分かった。

このことは、確定していない残りのbit数がいくつであっても成り立つ。結局、一番最初の状態の期待値は、含まれる $2^n$ 通りすべての平均値になる。

解説を読んでAを通し、Cの正しい解法を実装した。Aは、中央の2xNマスをターンテーブルとみてぐるぐる回すことで、目的の駐車場と隣接する瞬間が来る。一度も回せなければ答えは-1だ。

Cは、長さが $r$ 以下のベクトル3つがあると、適当に2つ選んで足したり引いたりすることで長さが $r$ 以下のベクトルを作れる、ということを利用して、すべてのベクトルの長さが $10^6$ 以下であるという条件を満たしたままベクトルの個数を減らしてくことで答えが得られるようだ。実装はちょっと面倒。

バチャに参加する直前と直後で、サークル解説会の準備をしていた。今日は解説に立候補してくれた人が2名、計3問の解説役が決定しているので、かなりありがたい。自分もF問題のスライドを作成した。

2021/05/21 定例会 | puzzleknot 公式サイト

yukicoder 296に出た。全完。

yukicoder contest 296 - yukicoder

Aはよい。Rubyで書いて、提出前にぐっとにらむとxorだとわかったので、慌ててRakuで書き直した。Bも面倒だが、文字列の先頭と末尾と長さだけ保存しておいて最長経路のようなことをすると解ける。Cはすぐに直前2数を持つdpが思いつくが、書いてみると $O(NK^3)$ になっていてびっくりする。累積和で書き直すことができて、数列の総和についても新しく足された分は通り数のdpと掛け算することでわかるので、OK。

Dは各数の平方因子をエラトステネスの篩の要領で計算し、square-freeとなった数の出現頻度をカウントすれば求まる。EはABCで見た、dp配列は $K\times K$ だけど毎回の更新が $O(K)$ 箇所で済む、というやつ。各次元に沿ってmaxを計算しておくのもABCで出たものと同じ。FはCと問題設定が同じということだけ先に言われていて、C問題を数学で高速化するのかな～と嫌な気分になっていたが、ふたを開けてみれば行列累乗だった。微妙に遷移行列で混乱したが、問題なくAC。

そういえば、昨日の典型90問はk-meansで解けないだろうかと思っていたのだった。そのことをツイートしたところ、実際に試してダメだったという報告が寄せられた。小さいケースだから厳密解が求まってもおかしくないと思っていたが、そもそも重心との距離はあんまり関係ないのかも。

日記を書いた。今週はなんとこれまで5日分を溜めており、真夜中から朝方までかけて書くことになった。書き終えてからちょっとコードゴルフをして、布団に入り、開いているいくつかのなろうを適当に読んで、午前7時就寝。

05/22(土)

午前11時57分の目覚ましで起床。正午からのAHC003に備えたものだ。このとき具体的に何をしていたかというのは、まだコンテスト中であるから書けない。20分くらいパソコンの前に座っていたが、そのあとすぐ布団に入った。少しだけTLを眺めていたが、またすぐ寝た。

午後4時くらいに再度起床した。生協の弁当受け取りを念頭に置いた起床時間だったが、それ以外にも典型90問が投稿されたことを確認したという理由もある。今日の典型は、適当に文字を置換して足し、Zalgorithmをする。星7がつけられていたが、かなりすんなり解けた。実装も簡単。ただコードを縮めようとすると、どう実装したものかわからなくなる。

C++のACLを使うコードを書いていたら、Rubyで通せたことが報告された。自分もRubyでZalgorithmを書いてみたが、実行時間が全然お話にならない。考え直して、ローリングハッシュを用いることにした。Zalgorithmで行っていた判定というのは、つまるところ文字列のprefixとsuffixで一致するものを数えていたのだから、引き算すら存在しないかなり単純な実装で書ける。手元で動かすと2secを微妙に超えてしまうようだったが、AtCoder上では1sec前後で安定した。ローリングハッシュに用いるmodについても考える必要がある。長さが $10^6$ 文字の文字列を区別する必要があるため、基数の位数の関係でmodは7桁以上にする必要がある。そこで7桁の素数を大きいほうからと、基数として1桁の数を選んで投げまくってみたところ、 $9999971$ と $2$ で通った。コードの書き方によっても通る素数と基数の組は変わるらしく、文字列の判定方法が変わるコードの改善があるたびにそういう組を見つける作業が発生して、大変だった。ほかにも、理論的に通らない6桁の素数を試したりもしていて、かなり無駄な提出が多かった。

そういうことをしていたら夜になった。ちょっとラノベを読んだり食事したりして、ABC202に参加した。19位。

AISing Programming Contest 2021（AtCoder Beginner Contest 202） - AtCoder

Aはよい。何とか最短を取れた。逆にBはrevを忘れてWAを出してしまい、速度差で最短を取れなかった。CからはC++で書いていた。Cは特に言うことなし。Dも自明だと思ったが、なぜか3回もWAを出してしまって大変な目にあった。Kと比較する値とKから引き算する値が異なっている提出を繰り返していたようだ。Eはオイラーツアーを考えるとわかる。

Fは大変。まず点は $X$ の昇順→ $Y$ の昇順でソートしておく。 $ccw(i,j,k)$ で「 $\overrightarrow{P_iP_j}\times\overrightarrow{P_iP_k}\gt 0$ 」を表すことにする。反時計回りになっているということを判定する関数だ。凸包だから、直前の2点 $i,j$ を持っておいて、次の点 $k$ は $ccw(i,j,k)$ であるように決めれば作れる。面積が整数であるという条件も、外積の偶奇を見ていけばよい。これで $O(N^3)$ のdpが書けるが、しかし凸包の内部に含まれる点を考慮するのが難しい。

ここで、凸包の隣接する3点 $i,j,k$ について、それぞれ点 $P_l$ であって $ccw(i,j,l)\land\neg ccw(i,k,l)$ となるような点の個数を数えると、その総和が凸包の外側にある点の個数になる。外角ごとに外側にあるとわかる点を数えている。このことを用いると凸包の内部に含まれる点を考慮できるが、ただし凸包をスタートする部分のカウントが難しい。最初は1点決め打ってスタートしていたが、これだと外側の点を漏れなく数えることができない。1周して戻ってきたとき、最初に使った辺の情報を復元できないから、決め打った1点の外角を考えられないため。そこで、仕方なく2点（つまり1辺）決め打ってスタートすることにした。

結局、 $O(N^3)$ のdpを $O(N^2)$ 回行うことになった。最初の提出ではTLEしてしまったが、直前の2点 $i,j$ から $k$ を選ぶループのために $i,j$ に対して $ccw(i,j,k)$ を満たすような $k$ を事前に列挙しておいたり、また $ccw$ や $\overrightarrow{P_i}\times\overrightarrow{P_j}$ を最初にすべて計算して配列に保管しておいたりといった改善を加えたところ、2回目の提出でACできた。1500ms。 $ccw(i,j,k)$ を満たすような組 $i,j,k$ の個数はそんな多くはならないだろうから、5乗といっても定数倍が小さくなるだろうと考えてはいたものの、TLEした後の改善中は、実際にはどれくらい惜しいのかがわからなかったため、大変に怖い思いをした。

Fの想定解は、1点決め打ったあと各辺との三角形を作って内部の点を数えており、頭が良い。これだと2点の情報だけでカウントできるので、最初に決め打つ部分が $O(N)$ になって、合計で4乗になる。

コードゴルフ。ABはコンテスト中に出したものが最適であろう。

CはPerlで書いていたが、AWKで書くとかなりいい感じになって、縮んだ。3行目と4行目を一気に読みこんだのがミソで、1つのループを使いまわし、2行目においては1..Nの集計を、3・4行目においてはN+1..2Nを回して答えを求めている。このインデックスの連続性により、ループ変数の初期化が必要なくなって、処理が無駄なくまとめられている。会心の出来。

atcoder.jp

DはRuby。combination.sizeで二項係数を計算するやつ。EもRubyで、よくわからないが少しばかりのバトルが発生して縮んだ。Fは手つかず。

TCO21 R2Aに出た。以下のリンク先は、この日記を書いている段階ではまだ表示されない。

TopCoder Statistics - Match Overview

EMの2完で33位、レートは2556→2567(+11)でhighestを更新した。赤が多いのでこんな順位でもレートが上がった。

Easyはカス。問題文が5400文字くらいある英文で、題意を把握するのにかなり苦労した。

台座が3つある。駒A、B、Cと武器グー、チョキ、パーがあり、各台座に駒と武器が1つずつ並べられている（重複はない）。この並び順はずっと不明。

"AB"と宣言すると、駒Aと同じ台座にある武器が駒Bと同じ台座にある武器に勝つ（もちろんじゃんけんの意味で）、という表明になる。失敗する（宣言が誤りである）こともあるが、この宣言を80%以上の確率で成功させたい。

具体的には、次のようなゲームが進行する。まず自分が1度宣言を行い、それが成功したかが知らされる。これは入力で与えられる。その後、これも入力される文字列に従って、「駒の入れ替え」「武器の入れ替え」「駒か武器の入れ替え」「宣言」が行われる。入れ替えの具体的な内容は知らされない。「宣言」のタイミングで宣言を行い、ゲームを通しての成功率を80%以上にせよ。

解法は簡単で、最初の宣言である2つの駒の間の勝ち負けがわかるが、そのあと駒や武器が入れ替えられると勝ち負けも毎回逆転するので、それを見て答えるだけ。ちょっと面白く感じるが、それを圧倒的に上回る問題文の難読さで、非常に嫌な気持ちになった。

Medは、DAGが与えられるので、ある頂点 $u$ であって、それ以外のいかなる頂点 $v$ に対しても「 $u$ から $v$ にたどり着ける」か「 $v$ から $u$ にたどり着ける」のどちらかを満たすような $u$ をすべて求めよ、というもの。解法はいろいろあるようだ。以下は僕の解法。

トポロジカルソート順で、 $u$ であって $u$ より先にあるすべての頂点にたどり着けるようなものを求められれば、辺の向きを変えつつ2回計算することで答えられることがわかる。よってこれを考える。トポロジカルソートの逆順にみていき、今見ている頂点よりも先にあるすべての頂点にたどり着けるために到達しなければならない頂点の集合を管理する。ある頂点 $u$ を見ているときは、 $u\rightarrow v$ なる辺について集合から $v$ を削除し、最後に集合に $u$ を追加して、集合の要素が $u$ ただ1つだった場合に条件を満たすとわかる。

集合はbitsetで管理した。bitset.count()==1だと最大ケースで1secくらいかかったが、集合に $u$ を追加する直前に判定することにしてbitset.none()を使うと爆速になった。

Hardはわからず。ラプラシアン行列を書いて行列木定理を考えていた。

ラノベを1冊読んだ。「午後九時、ベランダ越しの女神先輩は僕だけのもの」2巻。

内容は……よくわからない。良いか悪いかでいえば、良い。ヒロインの描写がなんとなく淫靡でドキドキした。
週記（2020/10/19-2020/10/25） - kotatsugameの日記

1巻は確か、恋愛ものとしてはちょっと異色のイベントがあって衝撃を受けており、評価がよくわからなくなっていたが、2巻は（紆余曲折あったものの）真っ当に恋愛しており、非常にエモーショナル。はっきり良いと言える。ただ、情緒を増すための表現かもしれないが、時系列を頻繁に前後させて書かれた文章はちょっと読みづらかった。

日記を書いてシャワーを浴び、布団に入り、ちょっとだけなろうを読んだがすぐに寝た。午前8時半だった。

05/23(日)

午後5時起床。

昨日の典型90問の解説が投稿されていたので読んだが、ローリングハッシュが想定解らしくびっくり。自分の中で、ローリングハッシュというのは、文字列の中途半端な位置同士をマッチングする羽目になったときに渋々持ち出す信用ならないアルゴリズムというイメージだから、Zalgorithmで解ける以上これが想定だろうと信じ込んでいた。

昨日のコードも縮められていた。解説を読みつつちょっと考えてみると、どうやら文字を入れ替えるところで無駄な場合分けがありそう。RGBと012を対応させる（正確には文字コードを3で割ったあまりを見て120と対応させる）と、文字cとdについて(c+d)%3がすべてのインデックスで一致していることを判定することになる。これはdを-d..2-dのどれかに入れ替えることで文字列の一致になって、d==R ? R : G+B-dみたいな場合分けが必要なくなる。あと、昨日必死に素数をいろいろ試していたが、別に素数じゃなくても通るようだ。適当な数を適当に累乗すると、そこそこ大きな数が7Bよりも短く書ける。

ACL Beginner Contest: E - Replace Digits
tonakai さんが自身のショートコードを更新しました！ (8 Byte → 1 Byte)https://t.co/dTHpba7lIx
— atgolfer (@atgolfer1) 2021年5月23日

テストケースがなくなっていたらしい。

夜は本を読みつつARCを待とうと思ったが、緊張からあまり読めないまま時間になった。ARC120。

AtCoder Regular Contest 120 - AtCoder

5完28位でパフォーマンス2929、レートは2741→2761(+20)でまたも最高値を更新した。実は次回赤チャンスらしい。今日は結果としては良かったが、他がよかった分Cで詰まりまくって50分もかけたのが残念でならない。

kotatsugame's replay of AtCoder Regular Contest 120

最大瞬間風速は 15位 (08:08, arc120_b AC) だよ！https://t.co/FdFe0l8y6H #AtCoder_Replay pic.twitter.com/eS0kixjnKc
— こたつがめ (@kotatsugame_t) 2021年5月23日

A問題は、操作した数が新たな最大値になることに気づけばあとはいろいろ和を持つだけ。持つだけだが、紙に書かずフィーリングで実装したら合わせるのに手間取った。合ってからもまだ怖いので別のケースを試したりしていた。サンプルの数列が昇順に並んでいるのが怖いポイント。Bは、斜めに文字がそろっているのが必要十分っぽいことは見た瞬間わかって、証明もすぐつく。グリッドを斜めに走査するのになぜか手間取ったが問題なくAC。

Cは、適当に隣接項の和・差や先頭からの累積和を取ってみて操作の影響を確かめていたが、全然わからなかった。そこで一度操作そのものを純粋な気持ちで眺めると、項の元の値に左に移動した回数が足され、右に移動した回数が引かれていくことに気づく。また4 3という2項に操作しても値が変わらないことを確かめると、先頭から順にどん欲に合わせて良さそうであるとわかった。最初に、最大まで左に移動したときの値としてA_i+iを考えておいて、B_1と一致するもののうち最も左にあるものを除いてそれ以外を右にずらす……ということができればよい。この右にずらす操作は、全ての値から1引くことになるので容易に実現可能なはずが、コンテスト中はB_1のために持ってきた値より左にある要素にしか影響がないと勘違いしてしまっていた。これだと区間加算・値の検索をする必要が生じる。どうにもまともな方法ではできそうになかったので、仕方なく平方分割を書いたが、サンプルが合わない。ここで初めてサンプルを手で試し、勘違いに気づいた。自分に失望しながら書き直してAC。コンテストは残り65分で、順位表を見ると300位、さらにD問題もすでに100人以上に通されていて、顔が真っ青になった。

翻ってDは一瞬で解けた。上界を考えると、数列の値の大きいほうから半分と小さいほうから半分をうまく組にできればよくて、大きいほうに必ず(を割り当てるなどするとかっこ列が対応しなくなるが、折れ線グラフで下にはみ出た分を折り返すことを考えるとできる。

EはかなりWAが出ているようだったが、通さないと命がないため考える。幸いDを瞬殺したので時間は1時間くらい残っていた。まず、移動するなら左か右に全速力で動いたほうがよいことがわかる。二分探索することにして判定問題として見ると、まず人1はずっと右に全速力で移動し、その次の人2は途中まで行って、戻って、パーティーが終わる瞬間人1と会う。人3は人2が途中まで行くのに合わせて会い、残った時間は適当に右に進んでいればよい。ここまでは良いが、人4がどのタイミングで人3と会うのかについて、2通りある。つまり、人3が人2と会う前か、後か。とりあえず2通り考えることにすると、人5は4通りあり得ることになりそうだが、実は「できるだけ右に進んでからパーティーが終わる瞬間に人4と会う」か「人4がパーティーが終わる瞬間に人3と会う前のどこかで会う」の2つ、つまり最も極端なものだけを考えておけばよいだろうと感じた。この直感が順位表で散見されるWAの原因か、とも思いつつ、丁寧に実装して提出したら通った。快哉を叫びそうになったがぐっとこらえ、指パッチンにとどめた。後から電車のダイヤグラムみたいな図を描いてみたが、どうやら他のケースは、確実により右に進めたり、最終的な位置が同じになったりして、この2ケースのどちらかに吸収されてしまうようだ。

Fを開いて自明なdpを書いてみると、以前似たようなdpを頑張って高速化したような覚えがあったが、よくわからなかったので放置して、残りの時間はコードゴルフをしていた。

コードゴルフ。Aは負け。Bは久しぶりに#!perl -pで対応しないかっこを書く見た目が奇妙なテクが使えて嬉しい。DはRubyで書いておいた。

atcoder.jp

本を1冊読んだ。「犯罪社会学者・椥辻霖雨の憂鬱」。主人公のキャラが好み。主人公が准教授として在籍する大学の生徒で、重要そうな感じに登場するキャラがいたが、結局話の本筋には関わってこずじまいだったので、次巻があれば期待したい。ミステリパートはあまり面白くなかったが、吉川線の話で、トリックに関係する器物から受ける印象に対し、それを用いた殺人が行われたというギャップにちょっとゾッとした。