週記（2021/04/26-2021/05/02）

04/26(月)

先週の週記を投稿してからの話。ド深夜にAtCoder Problemsのアップデートがあって、現在開催中のコンテスト、具体的にはAPG4bとABSがProblemsに収録されるようになった（ACL Practiceのほうは以前から収録されていた）。コードゴルフの時間である。

ABSは、まあよい。出典と問題idが一致しているので、同じ問題であるという判定がされる。practiceのA問題はここでしか全員の提出を見れないので、その問題だけ新しく最短コードが生まれるが、これももう縮まないだろうという感じはする。一方APG4bは大量に新規問題として登録されるが、ほとんど手付かずだった。AtCoder Problemsに収録されないならば最短コードとしてもカウントされないということなので、どうでもいいやという考えでいたが、いざ収録されるとなるとまずい。

朝方までずっと問題を解いたり現在の最短コードの粗探しをしていた。他のゴルファーも一度縮めてからあまり触れていないようで、比較的最近のテクニックを適用したりして縮められそうなものはいくつか見つけることができた。

今日イチ押しの提出はこれだ。

atcoder.jp

本来ならbc||echo errorと書きたかったのだが、bcはプログラムのエラーに関係なく正常終了するようで、できなかった。Perlから呼び出して、返ってきた標準出力が空文字列だったときに分岐することで似たようなことが行えた。電卓をつくろうという問題ではあるが、bcという電卓があるのでそのまま使っている。

朝方布団に入って少しラノベを読んでいたが、100ページほど進んだあたりで就寝。午前8時だった。

午後3時起床。夢を見た。

夢をツイートの下書きに記録して二度寝しようかと思ったのだが、先日のJOIG 2021の問題がAtCoderに公開されていたのを発見して飛び起きた。1時間ほど前に公開されたようだ。急いでコードゴルフをし、その後全問解いておいた。

JOIG 2021 過去問 - AtCoder

Aはmax*3-sum。Rakuが良いように見えるが、実はdcのほうが短くなる。後からRakuの新手が出て、同じ長さになった。似たような問題はほかにもたくさんあって、そこからdcの最短コードを引っ張ってくるのが間違いがなくてよい。まずRakuでmax-sumをしているコードを検索し、その問題の最短コードを見てdcがあるか探す、というステップを踏んだ。

Bは見るからにVimを使ってくださいという問題。とりあえず12Bのコードを書いてから全体の提出を見たら、すでに9Bのものがあった。ボロ負け。CはRubyで書いておいたが、この日記を書いているときに試しにRakuで出してみるとギリギリで通ったコードの短縮と同時に定数倍高速化にもなって、普通に通った。Dは答えを二分探索する問題で、これもRuby。

Eからは普通に解くだけにとどまった。Eは頂点にそこまでたどり着くのに逆転させた辺の本数の情報を付け加える、いわゆる拡張dijkstra。Fは各色について上下左右の端を計算しておくと、ピクセルを隠す領域の端はその中から選ぶことになる。これで縦横1000通りあったのが256通りまで絞られる。まず上と左の端を全探索し、下を広げながら右端をデータ構造で管理する。僕はBITを使って、その位置に右端を置くと何種類の色が隠れるか持ったが、これはN=\max A=256としてO(N^2(N \log W+W))かかる。他の提出を見ると、priority_queueで覆いきれなくなった右端を落としていくのが良いらしい。O(N^3\log N)。

昨日ゴルフしておいたAPG4bの問題が、さっそくいくつか縮められていた。どれも昨日の自分の正気を疑うようなミスを咎められており、反省。

今日のサークル解説会も外部に公開する。今日は第二回日本最強プログラマー学生選手権の問題を取り扱う。僕はACEの3問題の解説を担当することにした。前回の反省を生かして、今回は競プロに関する予備知識があまりいらないような問題を選んだつもりだ。ほかにsotanishyさんがF問題の解説役に立候補してくれて、合わせて4問題を解説する。

最近、PowerPointのスライド作成時にAlt+セミコロンで数式が入力できることを知り、かなり便利になった。Wordに別のショートカットがあって、そちらはPowerPointで使えなかったので、すっかりないものだと思い込んでいたが、検索してみると見つかった。なぜショートカットキーを変えてしまったのか。

また外部からの参加者も含めて10人ほどが参加してくれた。今回はある程度喋る内容を考えていたはずだったが、今度は僕がひたすら早口になってしまったようだ。また次回気を付けたい。解説会の直後にサークルバチャが控えている。さすがに間が短いだろうということで15分遅らせることになったが、それでも最大限急いでスライドの公開作業やサイトの記事の作成・編集を行った。

2021/04/26 定例会 | puzzleknot 公式サイト

サークルバチャ。今日はCF #573 div.1。問題名に時津風が入っていて、div.2のA問題によればやはり艦これらしい。

https://codeforces.com/contest/1190

Aは、まだ残っている一番近いものがどのページにあるか計算し、同じページにあるものを一気に削除する。Bはおおむね階段状になるはずだが、ソートしたときに隣り合う要素が同じところが2か所以上あるか、1か所しかないがそこを解消しようとすると1つ小さいものに当たってしまうか、あるいは0が2つ以上あるかの3通りで先手の負けが確定する。先手と後手がAlice・Bobやfirst・secondではなく謎の文字列（ユーザー名？）であるような問題は、CFやyukicoderではそこそこ見るものの、正直やめてほしい。

Cは先手と後手が1手ずつプレイして勝ち負けが決まらない場合、相手の操作をそのまま真似ることで勝ちの横取りをしようとする戦略が効いて引き分けになる。先手勝ちの条件は簡単に判定できて、後手勝ちの条件も先手が取りうる手を全探索した上で丁寧に見ていくと計算できる。

Dは、まずX座標が同じ点をグループにする。各グループについて、そのX座標x0が領域の右端となるようなものをカウントする。見ているグループでY座標が最も大きいものをYmaxとしたとき、領域の下はYmax以下である必要がある。領域の下がある値y0であるとき、y0+1との差別化のために、(x,y0)なる点を含んでいる必要がある。そのような点が複数ある場合は、xが最大のものを選んだとしてもよい。このときの選び方は、x==x0のときy0<=yかつx<=x0なる点(x,y)（ただしxに重複があってはいけない）の個数で、これはyに対して個数を持つBITで計算できる。x<x0のときはX座標がxであるグループを見ているときに計算したのと同じ値になるので、毎回x==x0の点だけ更新して、取得はこれにもまたBITを使うことで対応できる。

コンテスト後の反省会で聞いたところによれば、DはY座標が同じ点をグループにして解いた人が多いらしい。ちょっと考えてみたが、確かにそちらのほうが楽な気もする。BITが1本でよいはず。

div.2の問題も解いておいたが、B問題が信じられないくらいカスだった。萬子、筒子、索子のそれぞれ1から9（これらを数牌と呼ぶらしい）、合計108枚のうちから3枚与えられるので、残り何枚引けば面子となりうるか？を答える。艦娘は麻雀しないだろ。

そのあとまたAPG4bを進めていた。昨日見て縮みそうだと思ったが実装が面倒だったものを倒していく。途中Rakuに新手が出た。

atcoder.jp

+<<words~~あたりが新手。これまで$_=hogeとして代入していたのは、ほとんどがhoge~~の形で書ける。これはスマートマッチ演算子~~の右辺がCallableである場合の挙動で、左辺を引数$_にして右辺を実行してくれる。

infix ~~

この更新が適用できる範囲はかなり広い。数えたら17個縮んでいた。ちなみにそのうち自分が最短でなかった問題はたった1つだった。されど1つ、か。

APG4bとJOIG 2021で2900ACに到達した。

TCB35の順位が公開されていた。満点3人のうち、回答時間が最も短かった僕が1位になった。37分09秒で、10位までのほかの人と比べてもかなり速い。圧倒的勝利で非常に気分がいい。

今日の典型90問は早いうちにdc 43Bが報告されていた。そのころ僕は53Bで、10Bも差がついていて勝てる気がしなかったが、じわじわ縮めていって、最後に1つブレイクスルーがあって43Bに到達した。一致してしまうとかなり辛い気持ちになるが、ここが踏ん張りどころとさらにコードを睨みつけていたら、42Bになった。コードを公開する気がなく具体的なことは何も言えないため味気ない書き方になったが、43B→42Bには1時間半かかっている。

布団に入ってしばらくハーメルンを漁っていた。午前11時半に寝落ち。

04/27(火)

午後6時、目を覚ます。TLをつらつらと見ていたら、ふとしたことから怖い話のWeb漫画のリンクを踏み、読んでしまった。

ハーメルンで1作読んだ。といってもまだ8話しかない。

syosetu.org

「玄爺」という亀の妖怪が出てくる。旧作の靈夢は玄爺に乗って空を飛んでいたらしい、ということをこの作品経由で知った。玄爺は「東方遺骸王」にも出てくる。読んでいた当時はオリキャラだと思っていたのだが、れっきとした東方キャラでびっくりした。東方遺骸王は本当に徹頭徹尾東方の二次創作なんだなあ、という気持ちになった。

さらに別の作品を読み始めたが、ここらでもう一度寝ておくことにした。しかし起き抜けに読んだ怖い話の印象が強すぎてなかなか眠れない。頑張ってハーメルンに集中しているといい感じの眠気が訪れたので、逃さないよう速やかに意識を落とした。午後9時半だった。

04/28(水)

午前1時、目を覚ます。

ンンンンンｗｗｗ

現状、「えびまのお誕生日コンテスト 2021 Day 1」だけがリストに追加されている。まだあるはずなので追加するPRを送ろうとしたが、スマホからだとUNIX時間を知るのがかなり難しいことに気づき、あきらめた。

そのまま布団で昨日から読んでいるハーメルンの続きを読んでいた。ちょくちょく意識を落としつつ、午前2時から午前5時半くらいまでかけて最新話近くまで来た。

午前7時、布団から出る。AtCoder ProblemsにPRを送るため、トップページに表示されないコンテストを探し始めた。Google検索で「site:atcoder.jp/contests」としてみるととんでもない数のヒットがあったので、加えて「お誕生日」とか「有志」のワードで検索した結果、いくつか見つけることができた。

そのうち「ゆらふなセンパイお誕生日コンテスト」は任意の時間にスタートできる形式のコンテストで、現在も参加可能。しかし以下の参加記によれば、問題はすべてAtCoder ProblemsにおけるOther Contestsの過去問であるようだ。

hyoga.hatenablog.com

結局、そういうコンテストは3つ見つけることができた。追加するPRを作成し、送ったところ、すぐにマージされた。

keymoonさんによれば、さらに次のようなコンテストもあったようだ。コンテストというか、ただジャッジが公開されているだけのページであるので、追加されるべきかどうかは微妙。僕はあってもよいと思うが、自分でPRを作る気はない。

テスト - AtCoder

シャワーを浴びて外出。今日は学食に行って、それからゲーセンで遊ぶつもりだ。そろそろ世間的には連休らしいが、時間の自由がきく身分であるところの僕としてはできるだけ平日に遊ぶようにしておきたい。家から学食までの道の途中に高校があるが、今日はそこで体育大会が行われていた。無観客らしく、フェンスのそばに保護者と思われる人影が数名張り付いておられた。このご時世に体育大会をするというのはかなり挑戦的であるように感じられるが、現在でも高校以下は普通に対面授業をしている、という事実からすれば今更か。

ゲーセンに行く前に本屋に寄って新刊を買った。今月はこれが最初で最後の本屋となりそうだ。財布の中身が心もとなくなったので近場のATMに向かってみると、3月半ばで営業が終了してしまっていた。近くでまだ営業しているATMを案内されるも、未だに土地勘がないためわからない。Google Mapで検索してみると思ったより近かったので、この機会に知ることができてよかった。ゲーセンからの距離を見るならば、おそらく新しく知ったATMのほうが近い。

ゲーセン。今日はアップデートがあって、追加された新曲をプレイしてみたが、縦連が全然追いつかなかった。難しいのでいったん放置することにして、適当に別の曲をプレイしていた。Tidal WaveでAJを出して、そのあとはLv12のスコアを詰めていた。スコア的には全体で1000点以上増えたはずだが、OVER POWERのパーセント表示は微動だにしない。99.50%を目指しているが、数値的にいくつになればよいのかが全然わからない。自分で計算するにしてもLv12の定数表とにらめっこする必要がありそうで面倒。

かなり眠くなってきたので、いったん離脱してエナジードリンクを飲んでみることにした。今週末にAtCoderでコンテストを開催するところの商品を購入してみた。500mlの缶を持ったまま音ゲーするのは非常に難しい。この日は足元に置いて、上からゴミが入らないよう缶の口をタオルで覆っていた。

2021/02/19以来久しぶりに「《破滅》 ～ Rhapsody for The End」を連奏して、ついにSSSを達成した。

いろんなところでスコアを落としていたが、ちゃんと譜面を確認したところそこそこ安定させることができて、難所に集中できた。例えばノーツがどういう塊に見えているか確認したり、長い片手トリルについて何分のリズムで何回叩くのか覚えたりなど。以下の2つのうち後者は前から使っていた運指だが、その後ろがよく抜けるのもあって小節全体としての成功率はかなり低い。しかしかなり早い段階でかみ合って、そのままSSSを達成した。たまたまうまくいったとしか思えないが、まあSSSが出たならなんだっていい。

f:id:kotatsugame:20210501181345p:plain
17-18、21-22小節

f:id:kotatsugame:20210501181413p:plain
98、102小節

ほかにも13+の未鳥をちょっと触っていたが、Glorious Crownの最後が間に合ったりContrapassoのお前の弁当地帯が繋がったりして、成長を感じる。脱力が少し上手くなっただろうか？

午後8時半くらいにゲーセンを離脱して食事しようとしたが、見渡す限りすべての飲食店が閉店していて非常につらい気持ちになった。仕方なくドン・キホーテに寄ってパンやお菓子などを買った。

家に帰ってきて、今日買った本を写真に撮ってツイートした。

今日のぶんの典型90問を解いてコードを少し縮めていたが、眠気がすごいことになっていたのですぐに寝ることにした。午後11時就寝。

04/29(木)

午前6時半起床。月曜日にゴルフしていた典型90問・024が42B→40Bになったらしい。かなり信じられない。勝てない。

午前8時半くらいに身を起こし、ほかに寝ている間に縮められていたコードを確認したり縮めたりしていた。

ラノベを1冊読んだ。「私と一緒に住むってどうかな？」1巻。あんまり好みに合わなかった。主人公とヒロインの2人で古民家をDIYする、という話。あんまりDIYに興味がないし、描写に現実感もなかった。倉庫に材料がたくさんあった、というのは高校生がいろいろ作るという設定上仕方ない部分もあるが、スマホでちょっと調べてちょちょいと木を切ってやすり掛けしたらできましたというのは簡単すぎじゃないだろうか。さらに、ヒロインは過去の出来事から主人公以外をどうでもいいと思っていて、それで衆目の中主人公と過激なスキンシップをとることに抵抗がないという設定だが、このほとんど痴女のような描写も見ていられなかった。

朝、APG4bとウクーニャたんお誕生日コンテスト（非表示のコンテスト）でコードを更新したはずだが、atgolferで流れてこない。これの原因を探っていた。サーバでファイルの更新日を確認したところ、クローラはちゃんと予定通り動いているようだが、問題のコンテストにおいては朝方取得した提出を最後に見に行っていないようだ。結局、原因は以下のようなものだった：

atgolferは高速化のため、AtCoderから直接コンテストリストを取得して見に行く方法と、AtCoder Problemsで最短コードが更新されているか確認してから見に行く方法の2通りでクロールしている。このうちAtCoderに直接見に行くほうでは先に挙げた2つのコンテストを取得できない。よって更新はAtCoder Problems任せになるが、AtCoder Problemsで最短コードが更新されるタイミングは実際の提出があってからかなり後のことになってしまう。それで、6時間経った現在でもAtCoder Problems上では最短コードが更新されていない扱いになっているので、atgolferでも提出を見に行っていないようだ。

原因が分かったところで、atgolferを更新することにした。こちらでも常設中のコンテストを取得し、またさらに非表示のコンテストリストも管理することにした。このコンテストリストはAtCoder Problemsのファイルから引っ張ってくることも考えられたが、APIとして提供された機能でない以上、いつの間にかファイルの場所が変わっていたりしたら対応できない。そこで、僕のやる気が続く限り手動で更新することにした。

1点困ったことがあって、https://atcoder.jp/contests/を読んでもAPG4bとABSが取得できなかった。ここで天啓が降りて、https://atcoder.jp/contests/?lang=jaとしたところ、無事取得することに成功した。この事実はつい最近TLで見たような気がする。それがなければ自力では解決できなかっただろう。確かに英語版が提供されていない以上英語ページからは見えないほうが良いのだろうが、普段日本語ページしか見ない人間にとってそのことに気づくのは非常に難しいことだ。

github.com

ハーメルンを読んだ。かませ犬の描き方が執拗でちょっとイラッとした。

syosetu.org

さらに別のハーメルンを漁ったが、すぐに寝落ちした。午後10時だった。

04/30(金)

午前3時起床。ECR108に参加し損ねた。

1時間半くらい、昨夜から読んでいたなろうを読み続けたが、なんとなく合わなくて読むのをやめた。俺ガイルの二次創作で、八オリ。八オリは一時期Pixivで結構漁っていたはずだが、なぜ今は合わないと感じてしまったのだろう。

syosetu.org

確かこの辺りの時間帯にラノベを1冊読んだはずだ。「この世界、わたしに都合がいいようです！」。これもあんまり面白いとは思わなかった。同じ人物のセリフが連続しているのに、1文1文鍵かっこで分けられているのがかなり気になった。もしかしたら適当に読みすぎて僕が発話者を同定できていなかっただけかもしれない。

ハーメルンの捜索掲示板を漁って作品を探すことにした。いくつかよさそうなものを見繕って、そのうち「竜に生まれまして」というのを読み始めた。

https://ncode.syosetu.com/n5244by/

そのまま読み続けたが、午前8時半から午後1時までまた寝落ちしていた。今日は祝日なので学食が営業していない。食事してコードゴルフしていた。夕方は今日の典型90問のコードゴルフで競っていたが、かなり差をつけたと思ったらあっという間に逆転されて勝てなくなったので諦めてしまった。夜はずっと「竜に生まれまして」を読んでいた。

yukicoderがあったので参加した。4完。

yukicoder contest 293 - yukicoder

Aから難しい。K=3、K=4のときを考えると何となく法則性が見えてくる。縦横2K+1のマス目がだいたい埋まって、下2行が市松模様、それ以外は端までピッタリある行とない行が交互に出現する。適当に計算して通した後、さらに式変形を重ねると、4K^2+2であることが分かった。bashからdcを呼び出すのもRakuも両方13Bだった。

Bはdp。全部持って素直に書くとO(N^4)になる。N\le 100なので投げたら普通に通った。これが通ることはあんまり直感的ではないように感じられるが、計算すれば当たり前か。CはZero-sum rangesの要領でもらう値を引き算していくdp。WAが出たので適当に全部0のケースを試したら大当たりだった。修正に手間取るも、なんとか2回目で通った。Dは木DP。

Eを見たがよくわからないのでFに進んだ。Fもよくわからないが、こちらのほうがsolvedが多いのでチャンスはありそう。と思ってしばらく考えていたが、そもそも「総和がA_i以下であるような連続部分列の個数」を答えるクエリを105回処理する方法もわからないので、あきらめてなろうを読んでいた。

コンテストが終了してからFの解説を読んだところ、誤読に気づいた。条件のうち「最小値がi」を「最小値がi以下」だと思い込んでいた。「最小値がi」ならばそのような部分列はかなり限られてきて、その中で上で言ったクエリを解くなら短いほうを舐めつつ尺取り法短いほうの端点を固定してもう片方を二分探索するので間に合いそうな気もする。実際間に合うらしいことが解説に書いてあるものの、具体的にどう示すのかが非常に簡潔に書かれており、よくわからなかった。

布団に入ってなろうを読んでいたが、午前零時半寝落ち。

05/01(土)

午前5時起床。先々週のコンテストの賞金が来ていた。過去最高額でうれしい。

なろうを読んだ。最近読んでいた「竜に生まれまして」を読了。ついでに主人公の妹竜をメインとした外伝「黄金竜外伝」も読んだ。

https://ncode.syosetu.com/n5244by/

https://ncode.syosetu.com/n9993dp/

良かった。最初は、上位生命体である竜の主人公視点で、幼いころから一緒に過ごしていた女の子がドラゴン使いとなって冒険者として大成するのを見る感じの話かと思っていた。それはそれで素晴らしかったのだが、実際はこの女の子はかなり早い段階で寿命で亡くなり、その後主人公竜が主体となって世界を旅したり戦ったりするのがメインになっていく。これも良い。人間たちの竜に対する無理解などのもどかしさがいい感じ。

別のなろうを漁っていたが、午前9時から午前11時までと午前11時半から午後4時までは再度寝ていた。

起きて、4月分の読書や書籍購入の記録をつけ、ツイートした。今年は全体的にあんまり読めていないが、4月それらに輪をかけて全然読めていない。積読が増えるばかりで非常にまずい。

また今セメスターの時間割が確定しているので、それもツイートしておいた。時間割のツイートをリプライに連ねていくのももう4年目である。

そのあとは夜までずっと週記を書いていた。溜めすぎ。

午後9時からZONeプロコンに出た。38:58全完2WAで35位、日本人順位だと31位。全然ダメ。

Aはよい。Bもちょっとびっくりするがやるだけ。CとDは点数が逆転しているようだが、かまわずCから解いた。二分探索すると各人のデータは25に圧縮できて、判定にはDPが使える。Dは親の顔より見た。この類の問題はマジで面白くない。EはO(R^2 C)本の辺を張ってdijkstraするとTLEしてしまったので反省して頂点倍加した。TLE解を書いている途中に頂点倍加するとよいことに気づいたが、通るだろうと思ってしまった。

Fは適当に基底を取るまではよくて、復元がよくわからなかったので適当にやったら1WAした。ACした僕の方針はこうだ：noshi基底をとる。基底ごとに、それの元となった値を覚えておく。i=1..N-1に対し、xorして0にするために必要な基底のうち最後に並んでいたものの元となった値をuとしてi^u <-> iなる辺を張る。これでよい理由は、i^uが基底のうち今使ったものより前に並んでいるものだけで表現できると言えるからだ。これを繰り返すと最終的に0と辺が張られることになる。

コードゴルフ。Aは最初Perl 22Bを書いていたが、冷静になるとbash 18Bが存在する。ここでZONeではなくONeを数えてもACできるようだが、climpetさんに1分弱負けた。お互い全完後のコードゴルフなのにこんなに僅差になってびっくりした。Bは適当にdc。最近全然書いておらず、累積maxを取るコードは自分が思っていた最短より過去の提出をさらって見つけてきたもののほうが1B短くて冷や汗をかいた。CはRubyで、一度は取ったものの負け。Dは適当にPerl。Eは手つかずで、Fは上で述べた解法より↓の解法のほうがかなり短くなるらしくclimpetさんに取られたが、取り返した。

Submission #22244053 - ZONe Energy Programming Contest

さて、E問題は僕がTLEしてしまった愚直に辺を張る解法でも通るらしい。これについて以下のようなツイートをした。

ちなみにこのツイートにある理由を説明するリプライには間違いがあって、rが「小さい順」で探索することで高速になっている。そのあといろいろな言及があって、「ゴールに到達した瞬間終了する」「costが等しいときはrが小さいものを採用する」「costが等しいときはcの大小で比較する」のいずれかを選択すれば愚直に辺を張って通るらしいことが分かった。まあもともと1ケースしかTLEしなかったのだから、たまたまそのような比較関数に対するテストケースが入っていないのだろうと考えていたが、どうやら遷移の特徴からちゃんとオーダーレベルの削減になっているらしい。証明はわからない。

ZONeプロコンの2nd Roundに出た。問題があまりにも簡単すぎてびっくりした。僕の環境ではChromeから見えなかったのでMicrosoft Edgeを使う必要があったことや、長めの入力を手で選択してコピペしてくることなどのほうが難しかった。しばらくの間404エラーで先に進めなかったのにもびっくりした。

Crystalのコードゴルフで新手が出た。macroを使う。

04. マクロ | Introducing Crystal Programming Language - Your awesome subtitle

atcoder.jp

CやC++のマクロよりは柔軟らしいが、コードゴルフで使うときは高機能なことはしない。普通にdefで関数定義すればよいじゃないかと思うかもしれないが、例えば上の例では変数名をそろえることで引数に渡すのを省いていたりする。さらなる利点として、上の例では使用されていないが、マクロ展開場所から見える変数を断りなしに使用できるのが効いた。Crystalにグローバル変数がない以上、関数定義の内部で使用したい外部変数はすべて引数として関数内部に持ち込む必要があった。

昨日のyukicoderのFを解いた。計算量解析の理由もちゃんと自分なりに理解できた。あるインデックスiが右側にあるインデックスr_1\lt r_2\lt r_3の計算時に使用されるとき、r_2から左に進んでr_1に邪魔されずiまで到達することなどからP_{r_1}\gt P_{r_2}\gt P_{r_3}が成り立つ。ここでr_1の左右でP_{r_1}より小さいもののインデックスを探すと、これは左がi、右がr\le r_2になっていて、このうち左のほうが短いという仮定からr_1-i\le r-r_1\le r_2-r_1となる。同様にしてr_3-r_2\ge r_2-i=r_2-r_1+r_1-i\ge 2(r_1-i)がわかるので、間隔が倍々になっていき、iは左右合わせても都合\logのオーダーでしか使用されないという寸法だ。

昨日は短いほうを見て長いほうは尺取りすればよいと思っていたが、それは結局長いほうの線形時間がかかることになってよくないらしい。毎回二分探索すると、logが増えるだけで計算量的にははっきりしている。

布団でラノベを読んでいた。4月から商品の税込総額の表示が義務化されたが、書籍では多くのレーベルで帯に表示することになったようだ。確認できた分では、ガガガ文庫だけがカバーに表示していた。

午前8時就寝。

05/02(日)

午後3時起床。午後4時半就寝。午後5時半起床、即就寝。午後8時起床、即就寝。二度寝を繰り返しつつネットサーフィンをしていた。

本格的に起床したのは午後11時。今日はCGRがあるので、それに参加するために目覚ましをかけていた。下書きに夢の記録があったのでツイートした。

またこれとは別の夢の記憶もある：皇太子に逆行転生して御幸（調べた限りでは皇太子には使わない単語らしい？）のために駅まで車に乗る。モタモタしていたら周りの人に置いて行かれたので、切符と未来のラノベを掴んで残されていた車に乗り込んだところ、付き添いの人が僕の逆行転生について知らない人だったので、車内でラノベを取り出すことが出来なくなった。道の前のほうを、外国の貴賓を護衛する戦車が走っている。我々も急いでいたため戦車を煽るような形で走ることになってしまったが、急に戦車が速度を落としたかと思うと後ろから数台の車が出てきて我々の前を完全に封鎖してしまった。こちらの車の運転手が車外に走り出て、この車に皇太子が乗っていることを説明すると、道を開けてくれたので、戦車を追い抜かすことができた。

CGR14に出た。7完31位で2743→2821(+78)。かなり良い順位だったが、B問題で詰まって1WA+19分もかけてしまったのが非常に痛い。31位はギリギリTシャツ確定ではなかったようで、さらに悲しくなった。

Aはソートしてヤバいところを後ろとswap。数列の要素がdistinctというのは優しい制約だが、なくても同様に解けるはず。面倒になるだけか。Bは平方数の2倍、または4倍のみがYES。最初は1より大きな2のべき乗のみがYESだと思っていた。今から思えば完全に頭が回っていない。Cは難しいが、priority_queueで一番低い山に積むのを繰り返すとよい。Dは適当に貪欲。

Eは解法ガチャで一発で当たりのO(N^3)を引けた。今いくつ見たかとそのうちいくつを自力でonにするかの2次元DPで、自力でonにするものの連続している区間を一気に遷移して3乗。遷移の係数は、別の区間の石と混ぜて並べる順番のほかに、区間内の順番も考える必要がある。これは、区間の長さLのうち最初に置く場所を決めるとあとは左右に伸ばしていくしかないことから、どの順で伸ばすかを考えて\sum_{i=0}^{L-1}\binom{L-1}{i}=2^{L-1}となる。この\sumは消さなくても3乗に変わりない。

Fは、まず操作してよい辺を貪欲に操作してよいらしいことが感じ取れる。しばらく考えていたが反例が見つからないので、これは認めてしまうことにした。この反例を考えている過程で、結局アスファルトの量をならしつつ広げていってしまうのだから、適当な全域木を取ってもよいのではないかと考えた。サンプルを試したところよさそうなので、実装してしまうことにした。行きと帰りで操作できるか試すdfsは、1回だとアスファルトを持ち上げて下すケースに対応できないが、2回実行すればよさそう。これでpretestが通った。0ケースもあるので結構安心感がある。実際、システスも通った。

GはまずSCCする。強連結成分内にはたくさんのループがあって、2つのループの長さが互いに素なら1刻みでどのようなメーターの値も取れそう。ループとループをつなぐ余計な辺もまた別のループの一部であるからには、そちらも適当に周回しておけばよい。ループはたくさんあるので、適当にサイクル基底を取り（これはdfs木の後退辺がそれぞれループに対応する）、それぞれ長さを計算して総gcd（gとおく）を求めておく。g=1ならどんなtに対してもメーターの値を自由に動かせる。

では1でなければ？このとき\gcd(g,t)=1ならば\bmod tの条件下で値を自由に決められる。さらに\gcd(g,t)=h\gt 1のとき、sとtをhで割ることで\gcd=1の場合に帰着できる。h\nmid sならばNOだ。以上のことは実はすべて\gcd(g,t)\mid sという条件にまとめられる。

ラノベを2冊読んだ。まず「D級冒険者の俺、なぜか勇者パーティーに勧誘されたあげく、王女につきまとわれてる」2巻。軽いセリフ回しが心地よい。それでいて途中かなり重いシーンがあって、落差にびっくりした。主人公がめちゃくちゃ強いのも好み。りいちゅさんの挿絵も非常に良い。

次に「やはり俺の青春ラブコメはまちがっている。」14.5巻。書下ろしストーリーが非常に良かった。これまでの積み重ねみたいなものを感じてエモーショナル。また、比企谷八幡と雪ノ下雪乃がちゃんと付き合っているようで微笑ましい。「い・ろ・は・す」と一色いろはがコラボしたのは記憶に新しい（一色いろはの誕生日である04/16のことだったようだ）が、そのコラボ短編も収録されていて非常にびっくりした。よくもまあ印刷が間に合ったものだ。折り込みチラシではこの本の表紙は「NOW PRINTING」となっていたが、案外これが原因かもしれない。いや、表紙データだけならすでに上がっているのが普通か？

2021/05/03追記：コラボは2年目だったらしい。収録されたのは2020年度版の短編で、2021年度版も新しい短編があった。以下にリンクを張っておこう。上が2020年度版、書籍に収録されたものだ。

www.i-lohas.jp

www.i-lohas.jp