週記（2021/12/20-2021/12/26）

12/20(月)

先週の週記には、12/20の昼前までのことを書いた。その後のことは今日のこの部分に書こう。

まず、別のハーメルンを読み始めた。これも暗殺教室の二次創作である。かなり面白く熱中して読んでいるうちに学食が閉まりそうになったので、急いで昼食を摂りに出かけ、帰りがけに注文していた本を受け取った。そのまま夕方くらいまで読み続けた後、週記を仕上げているうちにインターン先の定例会が始まった。

今週の進捗報告はヘナヘナ。実は先週の定例会がなくなっていたので、2週間分の進捗を報告できるはずが、もう本当に無でどうしようもない。しかもろくすっぽ内容を練れていなかったので、今週のどこかで久しぶりに1on1を入れてもらい、そこでもうちょっと詳しくお話できればとか何とか言って報告を終えた。

勉強会まで終わってから週記を投稿した。と、直後に特にFFでもなんでもない人にRTされた。不思議に思ってアカウントを見に行くと、先週読んだなろう小説「鷹は瑞穂の空を飛ぶ～プラスチックの専門家が華族の娘に転生したので日本は化学立国になります～」の作者の方だった。どうやって僕のブログ記事に記載があると知ったのだろうか。ツイートは容易に作者に届きうると考えて感想はポジティブなものしか書かないようにしているが、週記には、これを探し当てるほど熱心にエゴサしているならば覚悟もできているだろうと考え、かなりストレートな自分本位の感想を書いている。しかし実際に探し当てられたことを知って結構びっくりした。せっかくなのでリンクをもう一度貼っておこう。

https://ncode.syosetu.com/n1453gs/

久しぶりにがっつりコードゴルフをした。先週、1桁の整数を文字列から数値に直す際にto_iではなくhexを使うという短縮を行ったが、1桁でなくてもhexを使用できる可能性がある。数値の和や差などは保たれないものの、大小関係や等号だけは保たれるため、それしか使わないようなコードは縮む可能性がある。to_iという文字列を含む最短コードをすべて調べ上げて短縮できそうなものを探したところ、結構見つかった。特に、ほぼLISを求めるだけのような問題が7件見つかり、すべて縮んだ。以下はその一例である。

atcoder.jp

to_iを含む最短コード（正確には、僕がAC済みの問題の最短コードすべてのうち、to_iを含む行）は365件存在した。1件1件チェックしている間あまりの眠気で意識を失いそうになっていたが、何とか耐えきって提出までを済ませ、布団に入って寝た。午後9時だった。

12/21(火)

午前3時に起きてしまい、1時間ほどハーメルンを読んでいたが、生活リズムを整えるために強い意志で二度寝した。午前9時起床。夢を見た。

11/20に行われたABC228の賞金でアマギフが来ていた。10000円だった。19位だったから、おそらく7位～10位の学生応援賞に引っかかったのだろう。

今日もコードゴルフを始めた。最近やたら活動的な人がいて、atgolferがその人の更新で埋まっている。しかしいくつか見た感じ、どれも直前の最短コードの改行を1Bにしたり軽微な短縮をしているだけに見え、そのような自明な更新が残っている問題はたいていPythonかC++が最短コードになっているので、言語を変えるだけで縮む。過去何回も言っていることだが、AtCoderにおけるコードゴルフでPythonを使うには使うだけの理由が必要で、そうでない問題に対してはPythonはまったくもって無力である。昔はmod付きpowが強かったものの、言語アップデートでRubyにその利点を奪われ、最近はもっぱらheapqとnetworkxを使うための言語となっている。そういえばscipyというのもあったか。networkxとどちらが短くなるのだろうか、試す元気がないので試していない。

しばらくやっているうちにclimpetさんが僕の縮めたコードをさらに縮め、その過程でPerlに新手が出た。十分大きな値として1e9を使う代わりに\0、あるいは何らかのオブジェクトのリファレンスを使うもの。出力するとSCALAR(0x80007eed8)みたいな文字列が出るが、これは見やすく表示しているだけで、内部的に数値演算を行うと内側のアドレスだけが取り出されて、この場合だと34360258264になるようだ。これが効く問題もいくつかあったので、探して縮めた。

atcoder.jp

今日も学食が閉まりそうになったので滑り込みで昼食を摂り、床屋に寄って帰宅した。また少しコードゴルフをした。

atcoder.jp

まず、この問題は現在の計算機性能だと\Theta(N^2)が通る。その元で、列に挿入する方法と列から削除する方法があり、後者がかなり短くなった。1から順番に数列でその値のインデックスを探し、左右どちらが短いかを答えに足して、値を削除する。N回の繰り返しでfindとeraseに毎回O(N)かけるというアルゴリズムだ。挿入の方法だとソートだのが必要になってくるが、こちらではその必要はない。ただやたらと時間がかかるようで、RubyではTLEし、Crystalを持ち出してやっと1600msになった。少し書き方を変えるとまたTLEしてしまい辛かった。挿入の方法ではRubyで500msくらいと爆速になる。

今日はゲーセンに行く。午後5時くらいに到着して、途中夕食を挟み午後10時くらいまで遊んだ。成果としては、14+（特に旧13+）のSSS+が1譜面、14+のSSSが1譜面、14の99AJが5譜面、理論値が2譜面。A Site De La Rueは2回ある速い折り返しフリックのあたりでミスが出るので敬遠していたが、YouTubeの手元動画のコメント欄だったかで原因を知り、今日は1回も出なかった。肝心の原因というのは、フリック後の黄タップに判定が吸われていることで、対策としては思っているより速く擦ることだった。また、数えていなかったが理論値数はすでに2桁に突入していたようだ。

午後9時前にいったん離脱して夕食。目星をつけていた蕎麦屋は営業時間短縮で午後8時に閉店していたため、近くの家系ラーメンの店に入ったが、一口目で後悔した。ありえないくらい濃い。この店にはもう二度と来ないだろうし、より一般に家系の店では薄めを頼むようにしたいと強く思った。家系ラーメン特有の、ラーメンスープをすべて飲み干すことで特典が得られる「まくり」なる制度は頭がおかしいと思う。

午後10時、眠くて精度が取れなくなってきたので帰宅。

「時々ボソッとロシア語でデレる隣のアーリャさん」の重版ツイートが流れてきた。今年出たのにもう14刷らしい。「今年一番売れたラノベ」という3巻帯にあった称号は伊達ではないということか。こうして見ると、1巻の初版を逃したのが悔やまれる。

しばらくコードゴルフをして、午後1時に就寝。

12/22(水)

午前9時半起床。明日の昼に1on1の予定を入れてもらった。そのまま布団でハーメルンを読み続けていた。

途中少し起きて、昨日まで縮めてきた問題がまた更新されているのを見つけ、取り返していたが、これも1時間程度で切り上げてまた布団に戻る。学食にも行けず延々ハーメルンを読み続けていた。

ふとTLを見たらチュウニズム公式からアンケートが流れてきたので、答えた。大型アップデートでエアークラッシュという紫色のド派手なノーツが追加されたのだが、これの視認性が最悪なのでやめてほしいとの想いを込めた。

午後6時半、読了。「【完結】銃と私、あるいは触手と暗殺」。月曜日から読み始めた暗殺教室の二次創作である。非常に良かった。

syosetu.org

オリ主が元傭兵の女子中学生ということで、鍛え上げた戦闘能力で無双するのかと思っていたら、もちろん要所要所でそういう話も挟まれつつ、思いのほかがっつり人情ものだった。原作との絡め方もよい。基本的に起こる出来事はすべて原作準拠で、その中で大胆に確保されたオリ主の出番にも不思議と納得感がある。ネタバレになるが、ラストの殺せんせー生存エンドも非常に満足できた。原作もかなり綺麗に終わった記憶があるけれど、こういう原作の展開を打ち砕くIFは二次創作でしか楽しめないものだろう。エピローグも非常に健康に良かった。原作でもその後の話として1ページ漫画が4本くらい公開されていた記憶があるが、常々もっと読みたいと思っていたのだ。まあこちらでも1話だけだったものの、それでも満たされた気分になった。

ちょっと前にTwitterで、原作を知らない二次創作を読むのが躊躇われるという話を見聞きした。この作品では原作と同じ展開の箇所はほぼカットされていたため、原作の出来事を知らないと辛いものがあるように感じられた。しかしどうだろう、それは自分が原作を知っているからこそ抱いた感想ではないか？ちょっと前に僕のヒーローアカデミアの二次創作をいろいろ読んだときは、原作を知らないことでの疎外感を感じたりはしなかった記憶がある。知らない作品の二次創作を読んだときは、それなりの読み方があるのだろう。

先にツイートを引用したように、番外編があるらしい。見てみたら14話しかなくちょっとがっかりしたが、読み始めた。しかし午後7時半ごろに寝落ちした。

12/23(木)

午前0時半起床。

TCB43のランキング発表メールが来ていて、今回賞金を得られなかったことが確定した。TCB31から出場して、これまで実に12回連続で賞金を得ていたが、そのStreakが切れてしまった。全完を逃したのも初めて。

火曜日にあったPythonの講義の課題をこなした。実は毎週、水曜日までに講義スライドのキーワードを考えるという課題も出ていたのだが、うっかり忘れて木曜日になってしまった。幸いまだ受け付けているような様子だったのでしれっと投稿しておいた。今日の課題は主成分分析とやら。理論的な裏付けなど何もないしきい値を利用する、それっぽいコードを錬成して提出しておいた。

今日もコードゴルフをする。ハーメルンを読みつつ朝までかなり長いことやっていた。

atcoder.jp

文字列のペアとして一致判定をしたい。最初はローリングハッシュを使おうかと思っていたところ、直接文字列を用意して、それを要素にした配列のhashを取ることでも行えた。なんとなくスマートで気に入っていたのだが、その後適当な区切り文字を加えて連結したものを使ったり、果てには配列をそのまま連想配列に入れても間に合ってしまった。初期のコードではTLEしていたはずなのに、変形の過程で実行時間的にも改善されていたようだ。

朝方、昨日読了したハーメルンの番外編も読了した。「銃と私、あるいは放課後の時間」。どうやらもともと本編の合間にあったものを抜き出してまとめたようで、本編エピローグの余韻を台無しにしてしまうかと思ったが、おおむね日常回で純粋に楽しめた。ラスト数話は本編後の話で、これまた非常に健康に良かった。

syosetu.org

昨日の時点では生活リズムが崩れていないと信じて昼に1on1の予定を入れたのに、今日すでにこのような生活リズムになってしまった。ひと眠りする前に準備をしようと思って、1時間くらパワポをいじり、午前9時半に布団に入った。しかしさすがに今から寝て起きられる自信がなかったため、また別のハーメルンを1作読了した。「BEST ASSASSIN」。

syosetu.org

暗殺教室とゴルゴ13のクロスオーバー。ゴルゴが殺せんせーの暗殺依頼を受けるというストーリーだ。舞台こそ暗殺教室の世界でありつつ、文章や展開はゴルゴ13のそれだった。正直、展開は暗殺教室好きにとって辛いものだったが、非常によく練られていると感じた。

ちょうど読み終わったあたりで予定の時間になり、1on1。頑張って準備したおかげかかなりいい感じの報告をできたし、これからやることも明確化した実り多いものだった。実は自分の体感のみをもとに話しており、同じ業務に携わるほかの人の意見も聞いてみたいなと考えたので、それに向けて少し考え事をしていたら、今日も学食が閉まりかけたので急いで昼食を摂りに行った。

帰宅して布団に入り、またハーメルンを読み始めたが、午後3時半ごろ寝落ち。

12/24(金)

12/23の午後11時半に起床。思ったよりがっつり寝てしまった。HUPC2021の参加登録が始まっていたので、登録しておいた。

connpass.com

布団でハーメルンを読み続け、1作読了。「仁義ある暗殺」。これも暗殺教室の二次創作である。オリ主のヤクザ口調が過度に感じられてちょっと読みづらい。別のオリジナルキャラが登場するいい感じのところでエタっているのも嬉しくなかった。

syosetu.org

暗殺教室の二次創作は、もうビビッとくるものがなくなってしまった。ハーメルンを漁るのはこれくらいにしておこう。

今日もしばらくコードゴルフをして、午前5時くらいから日記を書き始めた。生活リズムがボロボロのため今週は丸々溜め込んでいて、ラノベを読んだりしながら書いていたらここまで書くのに6時間くらいかかってしまった。TCB43の話を書いている途中、ふと思い出して10問目の解説を探したら上がっていた。

Simple infinite series.pdf - Google ドライブ

へのk氏から「高度知識ではない」という助言をもらったが、コンテスト中に考えているうちに自力では解けないと屈服してしまったので、解説が公開されたら読むようにしたい。

週記（2021/12/13-2021/12/19） - kotatsugameの日記

絶対に形式的べき級数だと思っていたのに、全然違って愕然。高度知識ではなかったのは確かだが、まさかこのような方針だったとは……。ただこの式変形が自力でできるかというとそうでもない気がして、結局どうしようもない。

ハーメルンを1つ読了。「TS動画配信者の飼い猫♂になった件」。なんとなくHIKAKINとまるお・もふこっぽさを感じた。あくまでも猫として動いているので、設定に忠実ではあるが飼い主と通じ合えないもどかしさを感じる。

syosetu.org

学食に行って昼食を摂り、注文していた本を受け取って帰宅。先月末に12月に発売される本のうち購入を考えているものを軒並み予約したが、これですべて受け取ったことになる。次は1月発売のものを探そう、と思ってラノベの販売予定を確認していたら、12月発売のものもいくつか見逃していたようで愕然とした。改めてメモしておく。年末年始は帰省する予定のため、まだ予約はせず、いくつかは帰省先で購入して読むことにしよう。

12月発売のラノベをメインに23冊予約した。

週記（2021/11/22-2021/11/28） - kotatsugameの日記

少しコードゴルフをした。RubyでYesやNoなどの確定した文字列を出力する際は、クオートするのではなくシンボルとして:Yesなどと書くのが短いが、いずれにせよpメソッドではなくputsメソッドを使う必要がある。なぜかというと、pでシンボルを出力するとコロンまで表示されてしまうからだ。では、RubyをVimから呼び出す場合はどうだろうか？今日、出力されたコロンをVimのほうから消してもよいことに気づいた。このことを使うと、これまでputsだった部分をpに置き換え、代わりに出力直後に1文字削除のxコマンドを使うことになるので、都合-2Bできる。3つくらい適用できる問題があったため、縮めておいた。

午後1時過ぎに布団に入ってハーメルンを読みふけり、午後3時にさすがにまずいと思って就寝。といっても昼寝の扱いである。

午後6時からのXmasコンテストに向けて目覚ましをかけていたが、起きられず、午後7時過ぎに意識を取り戻した。このコンテストはまともに戦うことをハナから諦めているので、こうやって気の抜けた行動をしてしまう。

Xmas Contest 2021 - AtCoder

とりあえず布団から順位表を確認して、Bが通されているのを見て通した。頂点数と辺数が固定なので、できるだけ連結成分数を減らすためには森が作れればよい。実際サンプルのように配置するとループが発生しないので、この場合の連結成分数は(N+1)(M+1)-NMとなる。逆に連結成分数を増やすにはループをたくさん作ればよく、これまたサンプルのように配置するとよい。2行目、4行目、6行目……には\lfloor M/2\rfloor個ずつループの中心があり、3行目、5行目、7行目……には\lfloor(M-1)/2\rfloor個ずつあるため、適切に掛け算してループの総数を出し、最初の答えに足すと通る。

コードゴルフもする。(N+1)(M+1)-NM=N+M+1はよい。次にループの個数だが、N,Mの偶奇で場合分けして慎重に考えると、足す値が\lfloor(NM-N-M+2)/2\rfloorであるとわかった。これにN+M+1を足すと\lfloor(NM+N+M+4)/2\rfloorになるため、割ってから足すのではなく足してから割ることにすればコードが短くなり、結局dcで19Bを作れた。

次にF問題が通されていたので見て、頭だけではどう頑張っても無理そうだったので部分点を取ってみたら、結果がACになるようでびっくりした。Textで5Bであった。残りの問題も一通り眺めたが、何もわからなかったので諦め、しかし再度眠れるほどの眠気もなかったためずっとハーメルンを読んでいた。

1作読了。「ダクファン帰りのエルフさんは配信がしたい」。かなり面白かった。ハイスペック主人公が配信者になって人気を得るやつが好き。魔王とかの設定に絡んでちょっと不穏な話もあったが、今のところはのほほんと進んでいる。

syosetu.org

午後10時ちょっと前に起きだす。コンテスト終了を待って最短コードを確認すると、B問題は取れていたが、F問題は当然コンテスト開始すぐの5Bコードが最短になっていた。またハーメルンを読み続けて、午後11時半からCGR18。

Dashboard - Codeforces Global Round 18 - Codeforces

Aは操作回数を聞かないのが良心的。Bは立ち続けるbitを全探索するのはすぐわかったものの、算数パートに時間をかけてしまった。丁寧に実装していたら8分くらいかかった。Cは同じ位置同士でXORを取って、0と1どちらかを全部1回ずつ使い、他は使わないことになる。操作回数の偶奇が合っているかと、これでちゃんと使いきれるか、つまり元の文字列で0と1がそれぞれ半々になっているかを確認すればよい。正確には、XORを取ると各位置を使う回数の偶奇がわかるのだが、同じところを2回触っても操作回数が増えるだけで0と1の個数を変えたりはできない（適当に実験すると予想がつく）ため、無意味ということ。

Dは全部パリティにしたあと分かっている情報を重み01の辺にして、奇数長の閉路がなければよい。なかなか面白かった。Eは赤く塗る頂点数を全探索できる。毎回、各葉に対してそれを赤く塗ったときに青く塗れなくなる頂点数が最も多いものを選べばよいが、これはだいたい祖先の個数になるため、更新することを考えてもdfsで最初に一気に数えることができる。あとは青く塗る頂点数をスコアが最小になるように選び、それらの最大値を答える。ただし、葉を全部赤く塗ってもまだ他に赤にできる頂点がある場合は、追加で別に考える必要がある。Fは取る・置く操作をその位置で何回行いたいかを持ちつつdpすればよい。

残り1時間あって、solvedが多いHを考えてSlopeTrickだと思って実装していたが、DAGの分岐や合流にすべてを破壊されて終了。結果は6完37位で2837→3887(+50)。

F問題は、偶数番目だけbit反転すると01列の転倒数になるらしい。今年の夏にAtCoderで開催された有志コンで既出で、当時どうやって解いたのか見に行ったら、そちらでも隣接項のXORを取ってなんやかんやするという気合いで解いていた。こういう言い換えが自力でできたためしがなく、辛い。またコンテスト後にEがHackされた。先に述べた「別に考える」部分にミスがあって、うっかり葉を全部赤く塗らない状態を考えていたらしい。

atcoder.jp

ラノベを1冊読了。「美少女とぶらり旅」。シンプルな題名と題材が旅ということでキノの旅を思い浮かべつつ購入を決めた。あまり面白くなかった。高嶺の花とされるヒロインに対して平気で通じないネットスラングを使っているのが気に入らない。ヒロインの事情が重く、それが主人公との関わりによって救われるというストーリーだったが、主人公がかなり軽薄な人間に感じられてあまり納得感がなかった。

しばらく別のラノベを読み、布団に入ってハーメルンを読んで、午前7時半に寝落ちした。

12/25(土)

午後7時起床。第9回PASTの通常受験が終了したらしいことをTLで知ったので、またURLを推測して定期的にリロードする作業が始まるようだ。前回は数日後だった記憶があるが、今回はどうなるだろうか。

さらにしばらくハーメルンを読んで、布団から這い出し、午後9時からABC233に出た。今回からH問題ではなくEx問題になるらしい。確かにGとHの間に壁があるということはよく言われていたか。

AtCoder Beginner Contest 233 - AtCoder

Aはdc。FAだった。やはり最近問題文の難読化が激しく、なかなか意図が取りづらかった。タイムは25秒。Bはちょっと前のJOIにほぼ同じ問題があって、そこから最短コードをコピペしてくることも考えたが、それは自分のコードではないことを覚えていたためとりあえずC++で解いた。CはRubyのproduct。DはZero-Sum Ranges。Eは繰り上がりを考えずに桁ごとの値を求めて、後から正しくする。Fはグラフが木だと勘違いして2ペナ。森になるように取って、葉から順にそろえていけば、制約から毎回愚直にdfsしても間に合うし操作回数も足りる。Gは直感的に2次元で区間dpをしたら通った。今回のExは簡単で、答えを二分探索することを考えると45度回転した状態で正方形内部の点数を数えるクエリがある程度高速に解ければよい。セグメント木に列を乗せると、区間内である値未満の要素の個数を数えるクエリがO((\log N)^2)で解けるため、これを2回使えばよい。Xを座標の最大値とし、答えの二分探索と合わせてO(Q(\log N)^2\log X)で3250msくらいだった。

42分23秒で全完、4位だった。2ペナ生やしたが、それがあってもなくても順位は変わらなかったようだ。久しぶりにかなり成功したと言えるだろう。

コードゴルフをする。Aは最初の提出が10Bで、すぐスタック操作を弄って9Bに縮め、これが最短。Bは先にも言ったJOIの問題から拾ってきたコードを全完後にしれっと提出していたが、同じコードがすでに本人から提出されていた。Cは適当にPerlで書いておいた。Rakuならかなり短くなるだろうに、あえなくTLEしてしまった。DはAWK。Eは多倍長整数のまま無理やり計算するとどうあがいてもTLEしていたところ、10XからXの桁和を引いて9で割るというコードが通っていた。なるほど、確かに10^iの位は(10^{i+1}-1)/9だけ答えに寄与し、これを全部足し合わせると10^{i+1}の部分が10Xになるのか。これくらいなら多倍長整数で計算できるということらしい。Rakuで書くとTLEしてしまい、Rubyでは負けている。桁和をchars.sum(&:hex)で取るのではなく、普通に?+でjoinしてevalするとその周りも巻き込めてさらに短くなるようだ。残りは手付かず。

atcoder.jp

午後11時半からCodeChef。今日はDecember Lunchtime 2021。

https://www.codechef.com/LTIME103A

RMNTREVは手元で実験したらそれっぽい規則が見えた。変換を戻すのではなく変換後の文字列を求めようとしたり、細かい部分を詰めるのが微妙に遅くなった。OPTSORTは何かしらdpするかと思ったが、冷静になると触らなくてよい場所を巻き込む必要はないため、ちゃんとやると操作は一意に定まる。具体的には、すべての値の移動前と移動後のインデックスを組みにして、重なるものを全部マージしたものがそう。SLEEPTECHは、イベントソートすると「A\dots Bの値の部分和で[L,R)に収まる値が存在するか？」という問題を高速に解ければよくなる。使う値を1\le k\le B-A+1個とすれば、kA+k(k-1)/2\dots kB-k(k-1)/2が全部作れるようになるので、この区間と[L,R)の交差判定を考える。kA+k(k-1)/2\lt RかつkB-k(k-1)/2\ge Lが同時に満たされるようなkを探すということ。ここでkが絡む式がどちらも単調増加であることに気づけば、前者の式を満たす最大のkだけチェックすればよいことがわかる。最大のkは二分探索で求まる。INTREENCLRは面白かった。ウニグラフを考えたりすると、方針としてはN回のクエリで1頂点ずつ色を確定させ、のこりN/2回で色を揃えることになるだろう。最初に1回クエリを投げておき、あとは葉から順に色を確定していく。葉に対してクエリを投げると、直前のクエリとの差分から葉と親の色が同じか違うかわかる。クエリを投げた葉はどんどん削除していけばよい。頂点の色のグループはsetで愚直に持ち、データ構造をマージする一般的なテクでマージした。

NOL_LESSは解けなかった。どうやらAの制約がAB\le Dの形で与えられていたのが超重要らしく、このことからAの上限は高々O(\sqrt D)種類、しかもその総和は調和級数でO(D\log D)になっていたようだった。dpの遷移は愚直にやると2乗かかるが、畳み込みで高速化できる。4完30位でレートは2516→2518(+2)。何とか色落ちは免れた。

コードゴルフをする。スペシャルジャッジの問題で、出力の最後のほうに同じ値が連続するような出力を出すことになったが、試しに個数を増やしてみても通った。さては入力をまともにチェックしていないな？と思い、試しに1個だけ出力してみると、これも通ってしまった。恐らく問答無用でK回cin>>Rしていて、入力が存在しない場合は直前の値がそのまま使われてしまう、ということだろう。

atcoder.jp

ハーメルンを1作読了。「妹の配信に入り込んだらVTuber扱いされた件」。タイトルの通りのVTuberモノである。主人公のハイスペぶりが気持ちいい。セリフ回しがパロディ多めかつハイコンテキストでちょっと置いて行かれ気味だった。実際のところ企業系VTuberの実兄が定期的に配信に出演するようになって同期や先輩と仲を深めていたら大炎上間違いなしだろうし、作中でも微妙に燃えていたという描写はあるが、そこは創作なので気にしなくてよい。

syosetu.org

ラノベを1冊読了。「才女のお世話」2巻。今回もかなり良かった。1巻は良かったという記憶だけが残っていて、内容を忘れており、キャラクターの設定などが微妙にわからず困った。1巻はラストにハラハラするシーンがあった一方、今回は徹頭徹尾ラブコメで非常に良い。1巻のメインヒロインはあまり登場しなかったものの、出てくるたび嫉妬心を持て余しているようで可愛らしかった。みわべさくらさんのイラストも相変わらず良い。

日記を書きつつまたハーメルンを1作読了。「憑依系多重人格ライバーとは俺のことで私のこと！」。セリフのフォントで発話者を区別するのはなかなか見ないが、そもそもそうしなければ区別できないような文章を書くべきではない気もする。

syosetu.org

布団に入ってからも別のハーメルンを読み続け、さらに1作読了してから寝た。「男性Vがコラボするってよ【完結】」。炎上を題材にしているだけあって辛い展開が多かったし、特にラストの大会配信についたコメントなんかは直接的な物言いで心にキたが、ハッピーエンドでよかった。確かに話は一段落しているものの、正直これで完結するのは寂しい。続編も期待したい。

syosetu.org

午後3時半就寝。

12/26(日)

午後8時半起床。最近目覚ましをスヌーズすることを覚えたので、午後8時から10分ごとに意識を取り戻しつつ何とか覚醒できた感じ。午後9時からARC132。

AtCoder Regular Contest 132 - AtCoder

Aはちょっと実験すると確かに一意に定まってくれることがわかる。ここで実験のためのR,Cをソート済みにしておくと規則性が読み取りやすい。R_r+C_c\ge n+1であることが'#'である必要十分条件になるだろうと予想がつき、投げたら通った。Bは最初、操作によって必ずソートできるという条件をよく理解しておらず全然解けなかった。冷静になると操作のパターンが限られてくるため、全体を反転する必要があるかないかで場合分け、あとはどれだけシフトする必要があるかを調べた。サンプル3は反転を2回行うケースで、優しいなあと思っていた。CはbitDP。瞬殺。

残り100分をすべてDに捧げてしまった。何とか通ったはいいものの、Cまでがほぼ最速のため順位はあまり変わらず。まず「間にある」という条件を考えた。これは1だけを取り出してインデックスの対応を見ると、ちょうどその間のどこかに1が来ればよいということになる。そのもとで、できるだけ同じ文字が連続するようにしたい。実は「どこか」ではなく左端か右端と固定していいんじゃないか、追加として真ん中で現在進行中で連続しているものも1つ考えておけばいいんじゃないか、連続する文字数ではなく連続しなかった位置をカウントしないと貪欲できないのではないか、などしつつ5ペナと40分を溶かした。

ここでふと、そういうi文字目の1が位置すべき区間[l_i,r_i]に対し、[l_i-i,r_i-i]を考えると、「連続する値」ではなく「等しくなる値」を数えることになって扱いやすいのではないかと気づいた。区間スケジューリングを考えれば、これは貪欲で解ける。意気揚々と実装してみると、細かい値が合わない。どうやら端の扱いが難しいらしい。サンプルを睨みつけつつどうなってほしいのか手でいろいろ確かめて、何とかサンプル1、2まで合わせたが、3が合わなかった。この解き方だと1だけを取り出す代わりに0だけを取り出してもよく、そちらでは合う。逆にサンプル1だったか2が合わなくなったので、そちらをより細かく見て、やはり端の扱いを間違えていることに気づいた。値が端に揃った場合だけボーナスがあり、それを考慮しつつ貪欲するのは難しい。そのため、特にスタート地点である左端の扱いは2通り両方試すことにした。これでサンプルが全て合ったので提出、WAするも、適当に全部0とか全部1を投げると落ちてくれたので、それだけ別処理してようやくAC。

6ペナで4完ほぼ最遅、どうしようもない。コードゴルフをする。Aは適当にPerl。CはRuby。

Bは非常に頭の良い解答がいろいろあって、アイディアだけもらって縮めた。まず、僕はシフト回数を調べるのに1の位置を検索したのだが、これは数列を反転するかしないかで値が微妙に変わる。ここで驚くべきことに、nの位置を検索すると、数列がソート済みでない場合は場合分けが必要なくなる。自分でも何種類か手で試してみると確かにうまくいっていて、nのインデックスが0-indexedでiだとすると、答えは\min(i+1,n-i+1)になっている。ここからさらに縮む。実はこのiはp_1（数列の先頭要素）またはn-p_1と一致し、このどちらであっても\min(i+1,n-i+1)=\min(p_1+1,n-p_1+1)が成り立つ。つまり検索の必要すらなく、先頭要素（と数列がソート済みであるか確認するための2番目の要素）を読み込むだけで答えが出てしまうのだ！

ハーメルンを1作読了。「コミュ障ロリ魔王様のVtuber生活 in地球」。魔王様なので当然ハイスペックである。それを見せつけている序盤はよかったが、途中から過去の知り合いなど出てきて、そういう話はあまり好みではなかった。もっと無邪気に無双していて欲しかった、とはいえ、コミュ障克服というテーマゆえ仕方のないことか。

syosetu.org

その後また別のハーメルンを開いて、布団に潜り込んで朝までずっと読んでいた。さすがにまずいと思って起きだし、こうやって週記を書き上げた。次回更新は年明けか、それまでに今年読んだネット小説まとめを書きたいが……。