09/20(月)
先週の週記を投稿してからの話。まずECR22の続き（EF）を解こうとした。F問題は諦めたが、E問題について。
Problem - E - Codeforces
全然解けない。しばらく唸って、このレベル帯の問題を取っておく必要性は薄いと考え、諦めて解説を読むことにした。ある要素を取る条件は、それと同じタイプの要素であって
個前にあるもののインデックスを見て、現在処理している区間より左側にあるかどうか、と言える。この言いかえをすると、求める要素の個数は「ある区間内のある値未満の要素の個数」とできて、ソートされた区間を持つセグメント木で数えられる。自分はrangefreqというライブラリにしていた。
次にECR23を埋めた。
Dashboard - Educational Codeforces Round 23 - Codeforces
Aはよい。Bは場合分け祭りかと思ったが、ちゃんと整理するとそうでもなかった。Cは難しかったが、問題タグに二分探索とあるのが見えて、その方向で考えてみると非自明に感じられる単調性が見つかった。興奮してコーディングしたらlong longのつもりでlongと書いてしまい、CFでlongは32bit整数なのでWA。昔一度やらかしてからは常に意識していたので、引っかかったのはかなり久しぶり。Dはmaxとminそれぞれの和が計算できて、答えがその差として表せる。EはBinaryTrieのverify用問題。Fは区間の端だけ取り出し、遅延セグメント木に0と1の個数を持ちたい。実際には個数を持つ必要はなく、0・1が存在するかしないかをboolで持つだけでよい。作用素が微妙に準同型になっていない（単位元で壊れている）気がするが、幅0の区間に作用させることは考えなくていいのか、通った。
布団に移動してハーメルンを少し読み、午前11時半に寝落ちした。
僕の主観において月曜日は消滅したが、実際はこの後日付が変わる前に一度起きている。その時のことは火曜日の欄に書いた。
09/21(火)
09/20(月)午後9時くらいに少し目を覚まし、ハーメルンを読み進め、1作読了。「無自覚な吸血鬼の王」。勘違い物を目指していたのだろうけど、よくわからないなあという感じ。主人公の能力・来歴はその多くが謎のままエタってしまっている。また主人公のキャラもあまりに悲観的に感じられて好みではなかった。
syosetu.org
また別のハーメルンを開いて少し読んだところで再度就寝。次に日付が変わって、09/21(火)午前2時くらいに目を覚ました。
さらにハーメルンを読み進め、午前4時くらいに1作読了。「東方神零録」。主人公のノリがキツいが、直球でハーレムを作っているのが目新しかった。東方は女性キャラが多く、二次創作でオリ主が複数のキャラから好意を寄せられているのはよく見るが、実際に（それも複数と）深い仲になる作品は限られている気がする。
syosetu.org
もう1作読み始め、適当に斜め読みして1時間ちょっとで読了。「東方創造伝」。何らかの評価を下せるほど話が進んでいない。
syosetu.org
東方オリ主古代スタートのほとんどは、最初にオリ主が古代都市の近くに降り立って八意永琳と出会う。それで、しばらく古代都市で生活するのが定番の流れなのだが、正直古代都市の描写にはほとんど興味がない。月に移住してからは竹取物語の時代まで出てこないし、出てきたとしてもキャラクターだけで、古代都市自体は完全に消滅して現代に続く文明には一切関わらないからだ。
午前6時くらいになって布団から脱出した。食事して午前7時からインターンの業務に手を付ける。以前書いたコードは途中でエラーを吐いていたが、その原因となった自分の勘違いを1on1で修正してもらっていたので、コードを書き直す。一度書き始めたらこっちのもので、パパっとやって3時間くらいで一通りの完成を見た。完成というのは、プログラムが最後まで動いているということ。これで今日の午後に予定されている1on1で報告する内容には困らないだろう。1on1駆動開発……。
書いたコードは現在GPUを使用して動いている。試しにCPUで動かしてみたところ、思っていたより何十倍も遅くてびっくりした。こんなに違いがあるのなら、それはインターン先もわざわざPCを送ってくれるというものだ。
ICPC国内予選の競技ルールが発表されていたことを知った。今年はチーム3人がそれぞれ個室から参加しなければならないらしく、びっくり。でもサークルとして参加場所を確保する必要がなくなるから、その点楽にはなるのかもしれない。まあもともとサークルとして参加場所を確保する必要はないのだが、個人的な思想として3人集まって出てほしいというものがあり、それをサークルメンバーに押し付けるならば、義務として参加場所は確保しておかなければならなかった。
2021 国内予選 特別競技ルール | ICPC 2021 Asia Yokohama Regional
ECR24を開いて少し解き進めた。とりあえずA-Dまでを埋めた。
Dashboard - Educational Codeforces Round 24 - Codeforces
Aは算数。Bはやるだけだが、うっかりミスで1WA。Cはsolvedが少ないのを見て身構えていたが、実装がややこしいだけでアルゴリズム的には普通の累積和。4方向それぞれ計算するときの和を累積させる向きとか、ドミノが横に置かれているか縦に置かれているかでコードを変えなければならないとか、面倒さはピカ一だったが、一発で通ってうれしい。
Dは一見してわからなかったが、出かけようとシャワーを浴びていたら思いついた。すべての色について調べても、計算量は全体の要素数で抑えられる。
先週金曜日の日記にも書いていたが、入学意思確認書の提出期限が明日に迫っている。今日提出しに行くことにした。
大学院に合格したはいいものの、入学意思確認書を提出できていない。今週はもう終わってしまった。期限は09/22(水)である。火曜日あたり徹夜して直接教務課に出しに行きたい。
週記（2021/09/13-2021/09/19） - kotatsugameの日記
原付に乗って山に登る。教務課にたどり着いたのが午後1時ちょっと前だったが、その時間帯はちょうどお昼休みだった。仕方がないので食堂で食事した後、ハーメルンを読んでしばらく時間を潰す。ベンチに座っていたら目の前に鳥のフンを落とされてびっくりした。危なかった。
問題なく提出完了。これで本当に大学院への進学が決定したと言える。山を下り、川内キャンパスの生協に行って先週水曜日に注文していたラノベを受け取り、散髪して家に帰った。散髪の間はほとんど意識を失っていたが、時たま頭を起こすよう促されたことを覚えている。
注文したのは6冊で、うち1冊は在庫がなく、取り寄せている最中らしい。それにしてもまだ入荷連絡の音沙汰がないとはびっくり。重版待ちだろうか。
ECR24の続きを解く。今回はEからGまでちゃんと通せた。
Dashboard - Educational Codeforces Round 24 - Codeforces
Eは素因数ごとに尺取り法をする。初期値を間違えていて1WA。Fは何を思ったか、「辺の半分以上が橋」を「頂点数の半分より多く橋が存在する」だと思っていて
算数をしてしまい、1WA。すぐ二分探索に直して通したが、問題タグを見てしまったのが効いているかもしれない。
Gも問題タグを見たのが効いていて、フローを流した。これはECR22-Dの強化版。ECR22-Dはdpでも解けたが、問題タグにフローがあるのにびっくりしていたのを覚えている。今回の問題はフローでないと解けない。
Dは2つの部分列を作るのに、現在見ている要素が先頭になっていないほうの部分列の先頭を持っておくdp。問題タグにflowと書いてあってびっくりした。
週記（2021/09/13-2021/09/19） - kotatsugameの日記
ECR25のA-Dを通した。
Dashboard - Educational Codeforces Round 25 - Codeforces
Aからコーナーケースに引っかかってキレていた。与えられた文字列の末尾が0だと、さらに1桁0が送られていると見なさなければならなかった。Bは実装するだけだが、左下方向の斜めをすっかり忘れていて1WA。CDは貪欲。Eも適当に貪欲しようとしたが、2回ほど嘘解法を投げて、結局わかっていないまま放置している。
午後5時からインターンのメンターさんと1on1。今日の朝やったことを話して、この先数日やることを決めた。また働き方に関して、1on1がないとサボりがちになってしまうので、頻度を増やしたいということをお願いした。1on1が終わってから、微妙にやる気がある今コーディングするべきだと感じ、しばらくバリバリコーディングしていたら、次回までにやることとして設定したものが完成してしまったので、慌てて明日にも1on1をお願いした。
新サークル長から、コロナ禍前の活動がどのようなものだったかについて質問を受けた。確かに彼は今大学2年生で、入部時点で全ての活動がオンラインになっていたのだ。個人的には、僕がサークル長になってから対面で活動していた時期はずっともくもく会と称して本当に黙ってコーディングしていただけだったので、オンラインの活動に移行してからは内容も充実したし、教室の予約の手間もなくなって良かったなと考えていたのだが、それはそれとして対面で活動していた文化が今まさに喪われようとしていることに気づき、愕然とした。
しばらくパソコンの前に座っていたが、眠気がひどくて椅子の上で意識を飛ばしてしまったので、布団に移動して就寝。午後11時だった。
09/22(水)
午前4時くらいに一瞬起きたが、ちゃんとすぐに寝なおすことに成功した。次に、午前6時半くらいに目を覚ます。今度は二度寝できなかった。しばらくハーメルンを読んでいて、午前9時くらいに布団から出た。
ちょっとコードゴルフをした後、最短コードを収集するクローラーを久しぶりに動かすことにしたが、動かない。調べてみたところ、AtCoderProblemsのAPIが変わっていて、個人の提出を全件取得するAPIが無効になり、代わりにある時刻から500件分を取得するAPIが提供されるようになったらしい。
適当にコードを書き直す。提出を全件取得するのに、時刻0を指定して取得→取得できた最後の提出の1秒後からまた取得→……を繰り返すことにした。完全な同時刻に2つ提出があると壊れる可能性があるな、とは思っているが、必要なのはACしたことのある問題リストで、今のところは漏れなく検出できている。経過を出力してみると、どうやら僕の提出をすべて取得するためにはこのAPIを103回叩かなければならないようだ。スクリプトを起動するたびにそのようなことをしているとまずいから、ファイルに書き出しておくべきかもしれない。
昼前に家を出て、大学生協で買い物をし、ゲーセンに行った。今日は3時間くらいプレイした。なかなかいい成果が出た。
まず新しく解禁した曲について。12+、13、13+をそれぞれ1曲ずつ解禁し、12+と13ではAJを、13+ではSSSを出した。特に13+のSSSは（何度も譜面動画を見ていたということもあり）初プレイで達成できた。記憶にある限りでは、13+の初プレイでSSSというのは今日が初めてな気がする。これはAJも狙えるのではないかと思ってもう何回かプレイしたが、結局初プレイのスコアすら超えられなかったのは残念。初見プレイが微妙に上手いというのは音ゲーあるある。
また、HAELEQUINでSSSを出した。これで13+の未SSSは3譜面になった。先週水曜日の時点で敷地帯の運指さえ組めれば出ると言っていたが、実際そのようになった。肝心の運指は餡蜜で、SSSを出したプレイではそれ以前もめちゃくちゃ上手く行き、敷地帯直前で1-0、敷地帯抜けて3-0。今日は最後の変なリズムの交互が下手くそで、案の定1-1出してしまったが、それまでが望外に上手かったので耐えた。
今日プレイした感じでは、敷地帯の運指をちゃんと組むことがSSSを出すことの（必要かつ）十分な条件だろう。
週記（2021/09/13-2021/09/19） - kotatsugameの日記
他に、初音ミクの激唱でAJを出した。13+のAJは2譜面目だが、狙って出したという意味では初めての経験。かなり前に1-0を出してから、ほとんど噛み合い待ちの様相ではあったが、13+のAJに対する現実感がなく、今日まで本気で狙うプレイをしたことはなかった。3ヶ月くらい前に13+のAJがポロッと出たので、今日念入りにやってみることにした。
13+のほうもSSS出しておくか、と思って詰めていたら、なんと一気にAJが出てしまった。13+ではこれが初めてとなる。
週記（2021/06/14-2021/06/20） - kotatsugameの日記
実際、譜面の中で押せない部分はなく、安定しなかった鍵盤も入りの配置を覚えたらほぼほぼ通るようになった。今日詰めている間に一度99精度も出たのだが、AJ時のプレイでは安定を取って縦連を擦ってしまったこともあり、赤はそこそこ出ている。それでも堂々13+の最高スコアであった。
帰宅して急いでシャワーを浴び、午後4時から1on1。昨日コーディングした内容を報告し、微妙に出ていたエラーを解消してもらったり、その結果見つかったバグを直したりした後、さらにやることを決めた。午後5時からはミーティングで、今週も何事もなく終了。
大学生協で本を10冊注文した。新刊のチェック漏れがあって、2回に分けて注文してしまったが、支払いなどは結局のところ大学生協の店舗で行うので、特に損しているわけではない。しかしなぜチェック漏れが発生したのかが謎。漏れた新刊も発売されることは認識していたので、どこかでもう買ってしまったのではないかと購入記録を確認したりしていた。
溜めていた日記を書いた。火曜日の欄にICPC国内予選の競技ルールの話を書いたが、チーム3人がそれぞれ個室から参加しなければならないという文面が消えており、前年と同じく集まっても集まらなくてもよいとされていてびっくりした。
2021 国内予選 特別競技ルール | ICPC 2021 Asia Yokohama Regional
日記を書き終えてからパソコンを弄っていたら、椅子の上で意識を飛ばしてしまった。急いで布団に移動し、就寝のツイートをする。しかし微妙に目が冴えて眠れない。スマホを触って、Twitterで流れてきた「Vtuberの姉はオンラインで生きている」というnote記事を読みふけってしまった。
Vtuberの姉はオンラインで生きている｜しじみ｜note
ところどころにドキッとする言及がある。家にお金を入れないとか、母の日にプレゼントを用意しないとか。特に、僕が親にプレゼントを贈ったことがないことを思い出し、いたたまれない気持ちになった。せっかくインターンを始めたのだし、9月の給料が入ったら何かすることを考えたい。親に諮ってみよう。
日付が変わったあたりになって、決心してスマホを手放し、積極的な睡眠を試みたところ、意識を落とすことに成功した。
09/23(木)
午前5時すぎくらいに目を覚ます。TLにPixiv小説が流れてきて、それを少し見た後勢いに任せてほかのものを色々読み漁っているうちに、眠気がすっかり消えてしまった。ちなみに、主に「転生したらスライムだった件」のリムル愛されSSを読んでいた。
通知が行かない引用ツイートについて。以前まで、ツイートのリンクをコピーした後、URLのユーザーIDの部分を別の文字列に変えてツイートの文面に含めることで、本人に通知が飛ばないまま引用ツイートができるという仕様だったが、いつの間にか使えなくなっていた。そのあとどこかで、ユーザーIDの先頭に@をつけるといいらしいと聞いたので、試していた。kotatsugame_tのアカウントからatgolferのツイートをそのように引用して、atgolferから確認すると、確かに通知は来ていないようだ。しかしツイートのプレビューも表示されないため、引用ツイートとしては片手落ち。
atgolferに久々にログインしたので、ちょっとbotの運用について考えた。具体的には、botからフォローを飛ばすべきか否か。僕はkotatsugame_tのフォロー方針、つまりフォロバ100%を第一義としているので、フォローを返さないのは何となくむず痒い気持ちになるが、一方atgolferを作ったkimiyukiさんにはその方向のこだわりはなさそう。しかし以前から5フォローだけしてあったのがどうにも中途半端に思えて気になっていたので、少しだけ増やすことにした。フォロワー欄を見て、僕がatgolferで名前を見かけた覚えのある人をフォロバした。僕としてはこれで運用方針の統一性があると思えてスッキリ。
今日は午後1時からACPC2021 day1があるが、それまでしばらく時間が空いた。微妙に眠気が出てきたので、眠らないようにラノベを1冊読んだ。「お見合いしたくなかったので、無理難題な条件をつけたら同級生が来た件について」2巻。1巻から少し時間が空いたので話の内容を一切覚えておらず、当時の日記から復元しようと思ったが、設定に関する違和感しか書かれておらずちょっと困った。思えば、日記に本の感想をある程度細かく書くようになったのはそこそこ最近だったかもしれない。
登場人物が軒並み名家の御曹司・令嬢だった
週記（2020/11/30-2020/12/06） - kotatsugameの日記
ただ、1巻の内容をあまり覚えていなくても面白かった。特に、上で引用したように1巻の感想で触れていた設定に関する違和感が解消された。どうやら身分差のある恋を描いているらしい。そういうテーマは童話などではよく聞くが、現代社会を舞台にしたラノベで取り扱おうとすると、登場人物が軒並み上流階級の人間になってしまうのだろう。目新しくて面白い。また合間合間に挟まるやけに不穏な別視点の文章も楽しめたが、受け取り方は読むときの精神状態によりそう。2巻では主人公とヒロインがかなり近づき、いわゆる両片思いになっていると考えられる。その状態は健康にいいが、ここで身分差が火を吹くらしい。3巻が怖いが、楽しみでもある。
↓このツイートは2巻の文章の一部について。
午後1時になって、ACPC2021 day1にソロで参加した。結果は8完4位、個人勢としては2位のはず。説いた順番はABDFGHECなので、その順に感想を書く。
https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2021Day1
Aは、
の分割方法を全探索して、各行で揃った部分を持つbitDPをした。解説の方法がシンプルでびっくりした。Bは319を気合で通す。部分集合を全部舐めるときに、最上位bitだけ取り除いておくとループ回数が半分になることを利用した。ループが足りず1WAしたが、FAだった。OR畳み込みを条件を満たすまで繰り返すのが想定解らしい。Dは、部分集合の全域木の個数をそれぞれ行列木定理で求めておいて（bitDPでなんとかできるかと思ったが、できなかった）、あとは3つの市に分けるのをまた
で行う。市をまたぐ道路をカウントするのに
かけるとまずいと思ったので、頑張ってで引けるようにした。1つの市を取り出すのは
でできて、そのループ内で別に部分集合を渡るループを回し、部分集合からさらに1要素を抜いた時の値を用いて現在の部分集合の値を計算する。実際にはかけてもよかったらしい。
Fはパッと見難しい。前から貪欲かな～など思ったりしたが、よくわからない。しかしこの時点で一番solvedが多いということで、ボンヤリとあれこれ考えていたら、ふと操作2が可逆であることに気づいた。なので、最初に操作2を行えるだけしてよくて、得られた文字列の部分列としてが含まれるかを見ればよい。含まれる場合は当然一致させられて、含まれない場合は、もうこれ以上文字を増やすことができないため不可能。Gは2つのパスとみて、2つの端点を2次元dpのキーにするやつ。復元が要求されていてキレそうになりながら書き直した。
Hは、最初に辞書順を考えずカウントして、後から
未満とより大をそれぞれ取り除いた。よく問題文を見ると
とは書いていなかったので僕の提出は落とせそう。取り除き方は、を考えているときは文字の辞書順を逆転させることで、両方「未満」として扱える。計算についても、例えば先頭文字で大小が決まらない場合は次の文字……と見ていくと、どの文字を選ぶかはだんだん固定されざるを得なくなっていくので、線形時間で計算できる。Eは
が存在するような素数
を選び、
と
を入れていくことで、値の積和についての条件は満たせる。あとはこのペアを9個作れば29=512本の数列ができて、答えの1つとなる。
Cは結構最初のほうに読んで不可能だと諦めたのだが、コンテストが2時間も経過してみたらかなり通されていた。読んでみると、
であることに気づいた。つまりグラフが木かなもりの場合しか考えなくてよいということで、どうとでもなる。
と書かれると、途中まで読んだ段階で
とminを取っていると自分の頭が勝手に補完してしまうので、惑わされた。残り時間はIを考えながらTwitterを見ていた。
では解けた気になったが、定数倍が重すぎて通らないだろう。解説を読んだ感じ、の考察も間違っていそうな気がする。
ECR25のEFを解いた。Gは放置。
Dashboard - Educational Codeforces Round 25 - Codeforces
Eはちょっと前から開いて数度考えていた問題。辞書順最小を求めるので当然前から貪欲だと思っていたが、正しく求めようとすると計算量が抑えられない。試しに後ろから貪欲を考えてみると、辞書順最小が得られることが示せてしまった。ちょっと前のABCで後ろから貪欲する辞書順最小の問題があった気がするが、その時一般には成り立たないことが何度も言及されていて、それで後ろから見ることに恐怖心を抱いていたのかもしれない。FはZ-algorithmとdpで、dpの遷移先を決めようとループするとでは遷移のコストを求められないが、遷移に使う部分文字列を決定して遷移先を2回以上見ないようにすると計算量が落ちる。
あまりにも眠いので午後6時くらいに布団に倒れこみ、そのまま6時間も昼寝をしてしまった。起きた時には日付が変わろうとしていた。
ECR26のA-Fを解いた。Gはこれまた放置。
Dashboard - Educational Codeforces Round 26 - Codeforces
Aはよい。Bは3つの文字が異なることをチェックしておらず1WA。Cはif文を書きまくる。Dはbool値dpを考えてしばらく悩んでいたが、元の次元を1つdpの値に入れるとよい。最大値を保存する。Eは、
が再帰的に呼び出されるごとに
が小さくならないことがわかるが、実装には特に関係ない。
を素因数分解して、今以降で最初に
となるまでの操作回数を計算する。1回で
は必ず半分以下になるので、計算量的に十分間に合う。Fは、まず先頭の0を全部取り除き、残りの数列の長さが4以上の場合はシミュレーション。2と3の場合は、値を式で表して二分探索なりする。
次にECR35のFGを解いた。このコンテストは僕が4年近く前にリアルタイムで出たもので、upsolveをしていないためFGが残っていた。
Dashboard - Educational Codeforces Round 35 (Rated for Div. 2) - Codeforces
Fは難しいが、適当に直径を取ってみたら解けた。直径を残すように葉を削除していくと、すべての葉が最大の長さで削除できるため、よい。Gは置換の様子をarray<short,100>で持ったら2995msで通った。高速入出力を貼って遅延セグ木から双対セグ木に切り替えると1060ms。解説を読むと、普通のセグ木に置換の合成を乗せて、クエリをソートして端から見ていくことで毎回全部の置換の合成が得られるということらしいが、実装したら1169msだった。
以上でCFにおけるここ1年間のAC数が1000に到達した。最近はこれを目指していたため、達成した今何をするべきかがわからない。
TwitterでVSCodeのデバッガの導入ができないというツイートが流れてきたので、VSCodeをほとんど使ったことがないくせに首を突っ込んでみた。最初はTwitterのリプライでやり取りを交わしていたが、途中からさすがに面倒になってGoogle Meetで画面共有してもらいながら進めた。サークルメンバーなのでその辺りの障壁は低いはず。
どうやらQiitaの記事から拾ってきた設定ファイルがWSL向けに書かれている一方で、環境がWindowsのままらしい。いろいろ調べてみたが、結局Remote WSLを導入してもらうことになった。Qiitaの記事ではSSHログインだのなんだの書いてあるが、特に必要はなさそう。というのも、結局WindowsのディレクトリとWSLを連携させようとするから小難しいことをしなければならないのであって、最初から全部WSL側でやってしまえば特に問題ない。これまで書いてきたコード辺をエクスプローラ経由でコピーしてもらい、あとはターミナルで良しなに操作してもらうことになる。デバッガ起動についての設定も、ACLのインクルードのために毎回-Iオプションを渡すことさえファイルに書いておけば、Qiitaの記事からコピペしてくるまでもなかった。これで動くようになって一安心。自動で生成されたファイルはできるだけいじらないのが一番良いと思っている。
ラノベを1冊読んだ。「神々の権能を操りし者」。自分の実力を隠している主人公という前フリが琴線に触れたので購入した。1巻から実力を周囲に知らしめていて、手っ取り早い満足感があった。しかし2巻以降はどういう展開になるのだろうか。なろう原作で、なろうのほうではもう文庫数巻分連載されていそうだが、そちらを読むほど気に入ったわけではなかった。
別のラノベに手を出そうとしたが、明日は夕方から1on1があるし、そもそも何も進捗が産めていなくてまずい。焦りながら午前10時、就寝。
09/24(金)
午後2時起床。昨日シャワーを浴びずに寝たせいか頭皮が痒くて仕方ない。急いでシャワーを浴びた。原付に乗って購買に行き、注文した本を受け取った。今週火曜日の日記で言及した、届いていなかった1冊。重版待ちだろうかと書いたが、確認すると初版だった。
帰ってきてから1on1まではコーディング。最低限の進捗を産んで、何とか報告する内容ができた。最近、悪い意味で1on1に慣れてきたのか、報告と称して特に纏まっていないことをグチャグチャ喋っているだけになってしまった気がする。他の人の1on1を録画で見てみるべきなのかもしれない。少なくとも、今の報告の形態は、相手への甘えが多分に含まれていたと自省している。ともあれ進捗は進捗で、この先やることもこれまでと変わらず決めることができた。今日はあっさり目に終了。
自分の評価しているラノベの続刊が出るのかどうかを常々気にしていた。今日、BOOK☆WALKERというサイトにラノベランキングが日間・週間・月間で出ているのを見つけた。ここは判断の要素として十分だろう。ちょっと眺めていたが、精霊幻想記の既刊が軒並みランクインしていてびっくりした。アニメ化・ソシャゲ化はかなり広告効果があったということだろうか。個人的には、ニコニコ動画で出てくる謎解き風広告の答えがキャラクター名なのはまずいんじゃないかと思っている。そんな固有名詞を答えにするのは、ダメだろ。
bookwalker.jp
しばらくラノベを読んでいたが、午後9時20分からyukicoder 315に出た。全完。
yukicoder contest 315 - yukicoder
Aはよい。Bは得点が
であるという部分をちょっと誤読して時間を取られた。最適な戦略が常に同じだろうと予想していたがそんなことはない。CはDP、DはbitDP、EもbitDP。この3問はほとんど自明。Fは無限場合分けで、その時かなり眠かったのもあり厳しい思いをした。幸い一発で漏れなくパターンを列挙することはできていたようで、あとは場合の数や係数を修正していたらサンプルが合い、通った。特に、一番最初の実行からサンプル1でほとんど正解の値が出たのがやる気に繋がった。
「クラスの大嫌いな女子と結婚することになった。」3巻を読んだ。非常に面白かった。テンポのいい掛け合いが小気味よいと思っていたが、もしかして漫画原作ということが関係しているのか？漫画は読まないので、どのくらいのペースでそういう掛け合い・ギャグが挟まるべきなのかを知らないが、とにかくラノベであまり見ない感じのテンポであることは確かだ。内容についても非常に満足感がある。2人がそれぞれ空回りしている様子は辛かったが、それらの描写があってこそラストシーンが光る。報われた気持ちになった。新キャラが出るようで4巻への引きは不穏だったが、楽しみ。
次に「転生ごときで逃げられるとでも、兄さん？」2巻を読んだ。めちゃくちゃ面白かった。紙城さんは、今のところ代表作「継母の連れ子が元カノだった」で恋愛もののイメージが強いが、個人的にはバトルシーンの爽快感や見せ場の作り方が好み。書籍化作品では他に「最強カップルのイチャイチャVRMMOライフ」もバトルシーンがあって好きだったが、こちらの続刊は……過去の売上ランキングを調べた感じ、望み薄か。そもそも著者がシリーズを複数抱えていて超多忙だろう。また、恋愛ものでもバトルものでも、ところどころにミステリのエッセンスが加わっていて、それがまた面白いのだ。今回の巻では特に学園・順位戦・闘技場でバトル、とテンプレ設定が余さず盛り込まれており、間違いのない面白さだった。
日記を書いてからちょっとコードゴルフをしようと思ったが、全然縮まない上に画面を見ているつもりでしばしば意識を飛ばしてしまったため、諦めて布団に入った。午前7時就寝。
09/25(土)
午後0時半起床。眠気と戦っているうちにACPC2021 day2が近づいてきてしまい、昼食のために用意したパックご飯やみそ汁を食べられないままコンテストに突入した。30分ちょっとして一段落した頃合いにようやく食べたが、冷えていて悲しい気持ちになった。その頃はコンテストでも冷えていたが、最終的には10完9位と、ギリギリ面目を施せた気になっている。順番はABCDEFGIKH。
https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2021Day2
Aはよい。Bは
の制約から
も小さいものだけ考えてよいことを導くと、2次元dpができる。昨日に引き続きFAだった。Cは線分と点の距離を求めるだけなので幾何ライブラリにある……が、誤差が怖かったので整数の範囲で計算を行うライブラリを持ち出してみた。結果、verifyしていなくて式が違う上にオーバーフローしており、2WAしてC++で通すことを諦めてRubyを書いたが、typoでさらに1WA。合計3WAも出してしまった。聞いた話によると、どうやら普通にlong doubleで通るらしい。何のための問題だったんだ……。Dは
でソートして実家dpをした。
Eは難しかった。タイプ1のクエリはオイラーのφ関数そのまま。タイプ2が問題だった。結局、
で
と互いに素なものを求めてφ関数の値を引くことにした。互いに素なものを求めるのは、square-freeにして包除でできる。計算量が怖かったのでメモ化しておいた。Fは二分探索やるだけ。Gは木で個上の祖先が欲しくなったが、これはdfsで潜るたびにvectorにpushして、上がるたびにpopすると得られる祖先リストで求まる。Iは同じ人を含むサークル同士に辺を張ると重み付き最大安定集合になり、半分全列挙で解ける。
Kは腕前をどれだけ上げるかを決め打つという発想で、まず各ステージについて手動でクリアするレベルとそれに必要な腕前を計算しておき、腕前の値で降順ソートして、どのパターンでクリアするかを変化させながら計算する。これは優先度付きキューに入れて、腕前をだんだん落としつつ足りなくなったらパターンを切り替えるという方法でシミュレートできる。Hは2次元セグメント木で、0の処理が怖かったので書き換えた場所の4近傍も構築するようにしたら2.79secで通った。実装は↓のページを参考にしたが、updateの時にちゃんと下2つの値を見るように書き足す必要があった。
blog.hamayanhamayan.com
今日はCodeChefのコンテストがあるらしい。先週気になっていると言ったばっかりだし、また今日はコンテスト尽くしの1日にしてみようという思いから、アカウントを作った。練習問題を3問ばかり解いて、どんな感じなのかを探る。main関数の型がなくてもCEにはならず、longは64bit整数らしい。
最近いろんな人がCodechefに出るようになっている。最初出会ったときに謎インドコンだと思って敬遠したっきりなのだが、やっぱり自分が出ていないコンテストがあるとちょっと焦燥感がある。今からでも始めるべきかもしれない。
週記（2021/09/13-2021/09/19） - kotatsugameの日記
新しいラノベを読み始めたが、そこそこで置いておいて、先に食事やシャワーを済ませておくことにした。今日は朝の5時までコンテストがあって、次の日の午後1時からもまたコンテストがあるからだ。
午後8時になって、ARC127に出た。ギリギリで5完して24位。
AtCoder Regular Contest 127 - AtCoder
Aは
それぞれについて数える。数える方法もちょっと考え込んだが、桁を決め打てばそれぞれ単純なminで求まる。Bは難しい。
の先頭1文字が2であることは確定する。そのあとはできるだけ0を置きたいので、
なる
を取って、後ろ桁を弄る（
を3進数と見て展開した）ことで通りの文字列を作ることにした。無事通りの文字列が作れたら、それらの先頭に2000...を足し、012を適当に巡回置換することでもう
通りも得られる。作り方から各桁の文字の分布についての条件が満たされる。
Cも……難しい。先頭の桁から決めていくと、1を置くときは2のべき乗だけ辞書順で大きくなるらしいことがわかる。これは
の対応する桁から1を引けるかどうかで判定可能。0を置くかどうかを判定するため、をデクリメントする必要がある。デクリメントは106回くらい行われる可能性があるが、そう何度も上のほうの桁まで見に来ることはないと考えられるため、愚直にやっても間に合う。これに関連して、maspyさんの「next_permutationを105回呼んでも問題ない」というツイートが興味深かった。
Dは、まず
を
に緩めてもよい。最終的に出てきた答えを2で割れば正しい値が求まるからだ。そうして、各
のペアについて、相方となる
がどんな値であればどこの桁で大小関係が定まるのか、を全探索する。大小関係が決まる桁より前は
と
が一致するので、これをキーに使えばペアの情報はかなりまとめられる。まとめた値をvectorなどに溜めておく。次に、逆にを全探索して、先ほどまとめた値とXORを取った和を計算する。これは事前に桁ごとに立っているbitを数えておけば計算できる。計算量が
として
で、2secくらいかかったが、問題なく通った。
Eも難しかったが、何とか解けた。連続するpopを、その前のpushと組み合わせて見る。もしpushがpop以下であるようなら、どんどん前に遡っていって、必ずpop>pushであるようにしておく（後で見るように、これは不可能な場合があった）。こうすると、popが組になっているpushより前の値を壊してしまうことがなくなる。ある特定の集合を作れるかどうかは、小さいほうから順に「集合に入っている→push」、「入っていない→pop」に対応付けてみて、pushと直後のpopの大小関係が壊れていないことを確認すればよくなる。popと次のpushの大小関係は問題ではないため、そこに自由度がある。ここで、「現在の集合に入っている要素より大きな値をpopしたのが何回か」をキーにして、そのpopの間に埋め込むようにpushするdpが考えられる。
実装したらサンプルが合ったが、残念ながら計算量が
になってしまった。しかもdp遷移にcombinationが出て、高速化できそうもない。そこで、先ほどまとめたpushを分解することにした。最初はpopも分解しようとしたが、以前の値を壊してしまわないようにまとめるのが本質だったようで、全然答えが合わなかった。pushだけバラバラにしてみると、先ほどのcombinationはpushに対応するものだったから、1個ずつ考えているということで消え、後にはただ範囲加算のみが残った。これは容易に
に落とすことができる。
提出したらWAとREが出た。焦りながらコードを確認した感じ、popをまとめている部分しかREが出そうな箇所がない。努めて冷静に考えると、一番最初まで遡ってもpop=pushとなってしまう場合を見落としていることに気づいた。うまいことemptyのチェックを挟んで書き直し、サンプルを試さずに投げたらAC。コンテスト終了3分前だった。
直後にCodeChef。今日はLunchtimeという種類のコンテストの9月号らしい。初参加なのでdiv.3。当然のように優勝した。レートは初期値1500→1766(+266)。
https://www.codechef.com/LTIME100C
VDATESはよい。TWODISHは全探索。UNQEQはが4の倍数でないと総和が2で割れず、逆に4の倍数なら構築できる。
と
のように組み分けするのを繰り返して2つの数列の総和を等しくできる。この時、prefixの総和の差を広げるような要素を優先的に配置すれば、途中で差が0になることはない。SOD3は自明。
ここからはdiv.1と問題が共通らしい。ALBOFACEは、最初にメモ化再帰を書いたらTLEしたので、grundy数を考えることにした。手計算で小さい値を調べていたところ、遷移の自由度がほとんどないことに気づき、計算方法も思いついた。2進表記にして、連続する0をまとめて考えると、上位桁から順にgrundy数を考えていける（冷静になるとgrundy数ではなく真偽値でよい）。INTREPはしばらく詰まっていたが、
ならば
が答えになることに気づいて解けた。
であった場合は、奇素数
であって
なる最小のものを探し、
が答えになる。
は
とより小さい奇素数の積なので、
が従う。またそのようなは
に必ず存在するので、出力の制約も満たせる。
以上6問がdiv.3の問題だったが、それ以降の問題も解けはするようなので、解いていた。SUBLCSは選択したペアの位置も含めた一致を答えるのだと思って何度もWAを重ねた。単純に各値が連続して何度出現できるかを見ればよい。RARRAYは尺取りをする。後ろから前に戻ってくる感じに実装して、前に1つ進めたとき新たに考慮する要素が順序を壊すようなら、考慮しないようにもう一方の端を前に進めてくる。順序を壊す判定はセグメント木で、値→インデックスとインデックス→値を両方区間minで持つ。謎の勘違いを繰り返し、これもたくさんWAを出した。最初のコードはACしてから見ると何を考えていたのかと呆れざるを得ない。MXMNSSUMは答えが負になる場合の処理ができず解けなかった。bitsetでできるなあと思っていたら、立っているbitが区間になるらしい。
div.3の全完には1時間かからなかったが、結局そこから2時間みっちり問題を考えていた。今日最後のコンテストまで1時間あったので、その間に日記を書いていた。午前2時からFHC R2に出た。
Facebook Hacker Cup - 2021 - Round 2
ABcCを通して59位。R3進出、Tシャツ獲得に加え、上位200人なのでTシャツが何か特別仕様になるはずR3の上位200人に対する褒章らしい。ぬか喜び……。
Aは難しそうな見た目をしているが貪欲でいい。マッチングにあぶれた人たちは着替える必要があるが、その時まだ着替えたことがない人を優先的に使う。そうしない場合に比べて損をしない、という事実が初回から順番に成り立っていく。Bは各辺ごとに同じ周波数の2頂点を分割しているかをチェックする。部分木の周波数をカウントして全体の個数と比較することにすると、マージテクで全ての頂点に対して計算できる。スタックオーバーフローが怖かった（どう考えても再帰dfsしたら落ちる制約だった）ので、最初にBFSしてその逆順にループを回し、再帰関数を使わずに計算した。
cは、1つの車を消す操作は最後にまとめて行ってよいこと、上と下にずらすのは片方しか行わなくてよいことがわかるので、あとはずらす幅を全探索。基本的に、ずらしすぎて開けたい列まで埋まってしまった場合を検出すればよいが、ちょうど開けたい列に車をずらしてしまった場合もケアする必要がある。
Cはこれの1点更新。簡単のため、上にずらす場合だけ考えて、下にずらす場合は盤面を反転させて対応することにした。ある場所に車が増えると、「ずらしすぎて開けたい列まで埋まる」場合のずらし幅が少なくなる。列の車の場所をsetで管理しておくと、今のずらし幅に対応する車が必ず存在して、その1個上の車になる。ということで、対応する区間に1加算すればよい。車が減る場合も同様。ずらしたときにちょうど車が来てしまう場合の1点更新も含め、遅延セグメント木で処理できる。解法を思いついてからしばらくはやりたくないと駄々をこねていたが、実際書いてみるとなかなかシンプルになった。それでも2000Bを超えているが。
今日は3h+2h+3h+3hで合計11時間コンテストに出ていた。立派な競プロ戦士になれた気がする。日記を書き上げて午前6時半就寝。
09/26(日)
昨日と同じく午後0時半起床。さすがに疲れがひどいが、昨日の経験から布団の上で眠気で戦っていると食事できなくなることがわかっていたので無理やり身を起こす。カロリーメイトと冷蔵庫にあったフルーツを手早く用意したが、フルーツだけ食べたらコンテストの時間になってしまった。
午後1時からACPC2021 day3。今日はABDCEFGの7完8位。難易度順らしかったが、それよりはsolvedを見て解いた。結果F問題までは爆速で6完最速だったが、G問題で勘違いを繰り返してしまい爆発した。
https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2021Day3
Aはどうにでもなりそうだが、ちょっと怖いので丁寧にやった。Bは素因数を数えて2で割る。Dは頂点を追加しながら期待値を求めればよい。Cは
をブロックに分けて
と対応付け、そのブロックの作り方を考える。
より大きな要素がブロックに2個以上存在するなら0通り、1個存在するなら左右の順番でcombination、0個なら真ん中をループで決めて1個の場合を足し合わせる。特に3番目の場合分けはちゃんとやると2のべき乗になるらしい。ブロックごとの操作列を組み合わせる時もcombinationを考える必要があることを見落として1WA。
Eは昨日のFHC R2D（の解法ツイート）で見たばっかりで、先頭24個を取り出して全探索すると鳩ノ巣原理から必ず見つかる。Fは怪しげな操作をしているので適当に累積和を取ったらswapになった。つまり累積和の転倒数。一瞬で解けて有頂天になりながら出したら、末尾の要素を変更できないことを見落として1WA。
Gは難しかった。サイクル基底かと思ったがそんなことはない（一般に頂点属性でサイクル基底はやりにくそうだ）。もっと自由な操作ができる。具体的には、いったん
までたどり着いてから「任意の頂点
に行く→戻ってくる」を繰り返すことで、
をコストにXORすることができる。これを2回セットにすると、任意の頂点2つを選んでXORすることに言い換えられるから、適当に
をほかの
にXORした状態で基底を計算し、からへの適当なパスのコストにXORして最大を求めればよい。パスを求めるのはdfs木とLCAを使ってやった。
……WA。手元で作っていたグラフを眺めていると、
パスに含まれる辺の本数の偶奇を任意に定めることができた場合はさらにやりたい放題できることに気づいた。上で頂点2つをセットにする必要がなく、最大値を達成するような頂点たちが決まったら、それに沿うようにパスの本数の偶奇を定めればよい。二部グラフ判定を書き加えるとようやくACできた。結局5WA出してしまった。
さて、これでACPC2021の全日程が終了した。今年はオンライン開催で、僕は3日間ともソロ参加かつ、3日間ともボス問題だけが倒せなかった。大学の合宿のボス問題を自分が解けるビジョンが見えないが、昨年の日記（この日記は1年以上続いているので去年の同時期のことが読める！）を読み返した感じ、椅子を温めていない時間は長くなっていそう。
ちょっと食事をした後、午後5時からOpenCupに出た。チームで5完。
最初30分くらいdiv.2の問題ページを見ているというハプニングがあったが、幸い気づくまでに自分が読んだ問題（A-C）はどれもdiv.1と共通の問題だったので、助かった。div.2の順位表を見て、Aは解けなそうと思っていたのに、div.1の順位表ではバカスカ通されていてたまげた。まごまごしているうちにチームメイトが瞬殺したので、実装もしてもらった。連続する正の数を3つ以上足すと素数にはならない、というのは超最近のyukicoderで見たばっかりなのに1ミリも頭に思い浮かばなかった。疲れている？
No.1657 Sum is Prime (Easy Version) - yukicoder
そのあと、B問題を念入りに詰めて、solvedが1桁のころに通すことに成功した。ギャグではない問題を通したのは初めてかもしれない。自分が行動できる回数は高々
種類くらいしかないので、全探索する。そのあとは丹念に場合分け。2次関数の（整数としての）最大値を何回も求める必要が出てきて、ああ……終わった……と感じたが、試しに平方完成して睨みつけてみると、それらによって得られる値が答えに全く影響しないということが分かった。実数範囲に制限を緩めて考えると、たくさんの最大値「の」最大値が直ちにわかって、ほかのケースで考えている値と本質的に一致あるいは小さくなるためOKという感じ。サンプルが合わなくてドキッとしたが、ちょっとした範囲のミスで、エイヤと直して投げたら1発で通った。
E問題が飛んできたので考えてみる。チームメイトの残した考察があまりピンと来ていなかったが、ACした後に見ると大体同じことをやっていたように思える。連続する同じ扱いの値を纏めると考えやすくなって、下から貪欲……と思ったらWAを出した。合計3回くらいWAを出していたら、さっきまでE問題を考えていたチームメイトがコードを読んでくれたらしく、Hackケースを教えてもらった。それで何を抜かしていたのかに気づき、AC。助かった……。
他の人がいろいろ実装している間にJ問題を考えていたら、それなりによさそうな性質を見つけた。パソコンも空いたので実装するか、と思ったが、入力を受け取ったあたりで思ったより実装がヤバいことに気づく。このとき午後8時半を回っていて、ABCまでそんなに時間がなかったのもあり、焦って考えが全然まとまらない。結局ABCまで残り10分くらいになったところで逃亡してしまった。
AtCoder Beginner Contest 220 - AtCoder
7完97位。Fまではそれなりにいい調子だったのに、Gで8WAして何もかもが台無しになった。
Aは
で解いた。dc。Bを開いたらあまりにもdc向けの問題すぎてたまげた。自明な5Bコードを書いて提出し、順位表を見に行ったところ、dcを書ける人がすでに通していたため、絶望。CからはC++。適当に和で割って残りを
……と思ったらWA。問題文の不等号が等号なしだった。Dはdp。Eは上って降りる幅を全探索し、それぞれを気合いで計算した。サンプル1が合わなくて大変だったが、一度合ったらそのままACできた。Fは全方位木dp。
Gは、まず線分を全探索して傾きでグループ分け。この時点で答えを求めてしまい、サンプル1が合わないのを見て、等脚台形という条件をすっかり忘れていることに気づいた。等脚台形にするためには、2つの線分の中点を結ぶ線分が元の線分に直交する必要がある。ということで、傾きでグループ分けした中で中点（を適当に移動させて正規化したもの）でさらにグループ分け。重なる線分を選ぶとまずいので、中点も一緒に持っておいて判定する。最後に各グループに対して答えを求める。……WA。かなり面倒なコードを書いたので、解法ミスではなくどこかにバグがあるのだろうと思って探す。数か所ミスを見つけたものの、それらを直して提出したつもりなのに、最初の8WAから一歩も先に進めない。残り20分を切ったころ、大きいほうから2要素を持つ変数の初期値が
だとマズいことに気づいた。これだと、
が2個あったとき、組になって答えが0で更新されてしまう。これを
に直したら通った。重みは2つまとめるところまではint型に収まるな、と思ってわざわざint型を使ったのが裏目に出たらしい。適当に
とかにしておけばよかったものを……。
コードゴルフ。Aはコンテスト中のdcコードが最短。Bも5Bコードで、こちらは案の定提出時間で負けていた。CはRubyで書いてからdcで縮めたが、僕がdc 50Bを作って出したころには44Bが提出されており、完敗。しばらく睨んでも縮みそうにはなかった。DはRubyで書いて負け、Perlで縮めたがそちらでも負けた。以上前半4問のうち1問しか最短を保持できていない。最近コードゴルフが盛んで負けまくり。
Hを通した。半分全列挙で、2つの集合との間をどうするかが問題。コンテスト中は時間がなくて全然考えられなかったが、じっくり取り組んでみると、で「選ばなかった頂点」の組から、の「選ぶと監視されている辺の本数の偶奇が変わる頂点集合」が求まることがわかる。今度はの選び方を全列挙して、先ほど求めた頂点集合との共通部分の要素数を見たい。これは、現在監視されている辺の本数の偶奇に対してから作ったの頂点集合との選び方をそれぞれカウントしておき、2×2通りAND畳み込みをすることで計算できる。
H問題で面白いコードがあった。1900msくらいかかっているので想定TLE解法だろう。まずすべての頂点を選んだ状態から初めて、ある頂点を監視するのをやめたとき、隣接するより頂点番号が大きな頂点それぞれに対してフラグの状態を変える。これは隣接行列の行をXORすることで計算できる。逆に、フラグが立っている頂点を監視するのをやめたとき、「隣接するより頂点番号が小さな頂点のうち、奇数個がすでに監視されていない」ことがわかるので、それらとの間にある辺は監視されなくなり、監視されている辺の本数の偶奇が変化する。今見ている頂点、現在監視されている辺の本数の偶奇、各頂点のフラグの3つでdpを行う。3次元目の値はmapで扱う。
atcoder.jp
この解法でコードゴルフするとかなり短くなった。mapを使うのに#import<map>とすると、入出力のライブラリが使えないので困る。そこで#import<regex>とすると、2B増える代わりにC言語由来の入出力関数が使えるようになる。mapを使う場合はこれかbits/stdc++.hしかないと思っている。
ラノベを1冊読んだ。「精霊幻想記」20巻。最近やっていた話が一段落する巻だと思っていたら、ラストに衝撃的な展開があり、まだ心の整理がついていない。またそれに向けての加速だったのか、最後のほうは展開が目まぐるしくて狐につままれたような気分だ。主人公・リオはこれからどうなってしまうのか……。次巻を怖がりつつも楽しみにしている。