04/18(月)

04/17 午後11時半ごろ起床。ちょうどCF div.2が始まったころだが見送った。

すぐ日付が変わって、TCB46の結果が出た。3位と1点差で2位。1位とはかなり差を付けられていてショック。問題ごとの減点を見返してみるに、やはり2度以上提出するのが大きく響くようだ。スコアの計算式を改めてよく見ると、まず提出回数によって基本スコアが減らされて、さらにそれを元にボーナス2種類が計算されているらしい。つまり得点全体を減らしているようなものなので、影響が大きいのも納得。

https://techful-programming.com/faq/problem#q2

ちょっとカクヨムを開いたらかなり面白い場面で、そのまま午前1時半まで読んで最新話に追いついた。「自作3Dモデルの素材を宣伝するためにVtuberになったら予想外に人気出てしまった」。

kakuyomu.jp

Vtuberではなく中の人とその周囲をメインに描いている。複雑に絡み合った人間関係が徐々に明かされて行って、そのこんがらがった様子がかなり面白かった。Vtuberと中の人の関係は一般に秘密にされるということも効いている。一方配信活動の描写はそれほど力を入れていなさそうで、その分特に大きなイベントが起こったりもしない安定したVtuber活動が見れるのは安心感がある。以上がVtuberモノとして見た時の感想。他に、主人公がめちゃくちゃ鈍感なのが僕の好みだった。女性に粉をかけられているのに全然気づいていない描写など最高にニヤニヤできた。

そこから午前4時半くらいまでは別のカクヨムを読んだりハーメルンを読み返したりしていた。いい加減二度寝するのを諦め、布団から起き上がって食事した。

ちょっとコードゴルフをしたところ、提出制限が「2つ前の提出から5分間提出できない」になっていることに気づいた。以前は間隔が1分間だった。一応、1つ前の提出からは相変わらず5秒でよいようだ。これは先週の週記でも触れた、無限ループを延々投げられることへの対策だろうか。5分だとさすがにちょっと辛いので、コンテスト中だけでも制限が弱まったりすると嬉しい。

かなり久しぶりにラノベを1冊読了。「男子だと思っていた幼馴染との新婚生活がうまくいきすぎる件について」。至って普通のラノベではあるのだが、上流階級出身でお見合いでヒロインと結ばれるという設定と、幼馴染だったヒロインを昔は男子だと思って接していたという設定が、それぞれ同レーベルの現在売れている別作品と被っているのが気になってしまった。まあ前者はお見合いをする必然性からどうしても入ってしまう設定か。似たようなことを、その別作品を読んだ時にも考えていた。後者に至ってはタイトルからわかることだし……。内容としてはラストで祖母との確執がスムーズに解決するのが良かった。

作中では結婚可能年齢が男女とも15歳に引き下げられていた。あと、登場人物が軒並み名家の御曹司・令嬢だった。この2つの設定はどちらも単独で主人公がお見合いをすることの理由になりうるが、2つ合わさっても別に最強には見えない。その設定両方いる？
週記（2020/11/30-2020/12/06） - kotatsugameの日記

先週遅れて課題を提出した講義に、その課題の講評が投稿されていた。そこに僕の回答も紹介されていて嬉しくなった。真偽が明確に定まる文を自分で作り、その真偽を判定せよという問題。定義があいまいな事物を持ち出したり、断りなく変数を導入したりした回答がダメ出しされていた。さらに真偽の判定についても、例を挙げるなら具体的でなければならないということを突っ込まれていた。一方、僕の回答である「『この課題を遅れて提出した人がいる』は真である、何故なら自分がそうだから」は完璧だったらしい。

すでに期限が過ぎた課題を見つけた。今週分のようだ。遅れると1日ごとに点数が引かれていくシステムだったので、慌てて提出しておいた。
週記（2022/04/11-2022/04/17） - kotatsugameの日記

昼前まで先週分の週記を書いていた。完成させて投稿、さらに今日の分の日記を少し書き進めもした。また、上で触れた講義の今週分の課題を提出した。そうやって時間を過ごし、いい感じに昼休みが終わったのを見計らって学食に行って食事。予約していたラノベを受け取り、床屋にも寄ってきた。

帰宅してから1時間ほどかけ、「研究倫理教育」という大学院ガイダンス時に貰ってきた書類に書いてあったものをこなした。ネットでテキストを読み、選択問題の小テストを解く。もう全然やる気がなくてテキストはまともに読んでいなかったが、小テストはそれっぽい選択肢を常識に基づいて選ぶだけでそこそこ正解できた。合格点に届かなかった場合も、解答を確認した後即座に再挑戦できて、今度も問題の並ぶ順番がシャッフルされるくらいの違いしかないので、覚えておけば簡単。

今週は午後4時からインターン先の定例会。普段より30分前倒しになっていることに気づいておらず、予定アプリの通知が来なかったら危なかった。先週の分の進捗報告は本当にみそっかすみたいな内容しかなくて、自分で振り返りながら唖然としていた。一体自分は先週何をやっていたのだろう。まあ僕のうっすい報告以外は特に何事もなく、勉強会まで終了。勉強会では思わぬところから圏の話が出てきて、その枠組みで取り扱おうという気持ちすら全然わからなかった。

健康診断のため、ライフスタイル調査というものに答えていた。食生活に関する質問で、朝昼夜のどれをよく欠食してしまいますかだとか、間食・夜食はどれくらい摂りますかとか聞かれた。これは非常に難しい。そもそも朝昼夜という枠組みで食事をしているわけではなく、お腹が空いたら食べるということを繰り返しているから。時間帯も深夜が多く、何とも言えない。食べた順番に朝昼夜か？その場合、間食は原理的に発生しなくなるが、よいか？深く考えても仕方ないと思ったので、適当に朝食にしておいた。そういえば、「朝ごはんを食べると一日元気に過ごせますよ」とは、起きてからすぐ食事すればよいという理解でいいのだろうか。

日中耐え難い眠気がありますか→日中は寝ているため、ない
— こたつがめ (@kotatsugame_t) 2022年4月18日

定例会が終わってから少しラノベを読んでいたのだが、あまりに眠くまともに読み進められないため、とっとと寝てしまうことにした。ただ、布団に入ってからもうっかりハーメルンを読むなどしていた。午後9時就寝。

04/19(火)

午前2時半ごろに起きていた形跡がある。午前3時にはまた二度寝できたようだ。次に、午前7時半起床。

ハーメルンで1作読了。「ディストピアゲーに転生したら行政側だった件について」。連載が始まったばかりで10話しかなく、一口サイズ。内容はかなり面白かった。ワクワクする設定が大量に散りばめられている。

syosetu.org

起きて、健康診断の予約をした。そのまましばらくパソコンを触った後外出。まず原付に乗って生協に行った。以下で言及した教科書が届いたらしいので、それとラノベ1冊を受け取り、あとはミールカードを使い切るためお菓子や飲み物を買って帰宅。またすぐ、今度は自転車に乗って街のほうに出た。

ゲーム理論の講義を取ったのだが、これは教科書が指定されていて、来週からその演習問題が課題として出るようだ。今のうちに手に入れておく必要がある。
週記（2022/04/11-2022/04/17） - kotatsugameの日記

今日はゲーセン。食事を挟んでちょうど40クレ、実に9時間ほどプレイした。アップデートで追加された新曲を埋めていた。今日はかなり上手で、低難易度を埋めていた時に初見AJを10連続で達成した。しかも初見理論値を3譜面含んでいる。特にカウントもできていないが、Lv.14までの新曲は全部99AJを出したはず。

10連続初見AJ pic.twitter.com/N67tvx2Oe9
— こたつがめ (@kotatsugame_t) 2022年4月19日

14+はまだ埋め切れていない。頑張って初音天地開闢神話のAJを出した。レートの最高値も16.93に上がった。プレイする度に赤が増えていく。それでも99AJを達成できる精度くらいなら頻繁に出ていたのに、いざAJする時だけギリギリ足りなくなってしまって悲しい。毎回毎回アウトロが苦手で、この時も2個出して絶望していた。

初音天地開闢神話　AJ！！！
99AJ欲しかった…… pic.twitter.com/9cFm0J6JZ1
— こたつがめ (@kotatsugame_t) 2022年4月19日

時間は前後するが、午後4時半ごろに食事した。油そば。大盛300gという記述を見て、朝にパンを食べたきりだから余裕かなと思っていたのだが、僕が注文した太麺の商品は大盛が400gになるらしい。食べている最中にそのことに気づいて、一気に満腹になったような気分を味わった。何とか腹に押し込んだ。麺が硬かったので、300gも400gも体積はほとんど変わらなくて、密度の違いが表れているのだろう。

朝早く起きたので眠気もあり、疲れ果てながら帰宅。買ってきたプロテインの写真を撮ってツイートした。これまでバニラ味とココア味を食べたことがあって、バニラのほうが好みだったので大袋で購入。蓋つきの容器に入っているプロテインは300g弱で2000円ちょっとする一方、大袋だと1000gを超えるのに価格は5000円と、めちゃくちゃ安くなってびっくりしてしまった。一体なぜなのだろう。

ザバスざます pic.twitter.com/QFkE3sUiy0
— こたつがめ (@kotatsugame_t) 2022年4月19日

先週、あるアカウントがABC248-Exに無限ループを延々投げ続けるということがあった。今日のこの時間にまったく同じことがVjudgeを経由して行われていた。AtCoderはノックアウト形式ではない、つまり一度ACではないとわかっても変わらず以降のテストケースを実行してくれるし、TLEは念のため後2回実行されるしで、こういう攻撃には他のコンテストサイトより弱くて大変そう。

We have detected a malicious source code submission to atcoder via “Vjudge” and have temporarily frozen Vjudge.
— AtCoder (@atcoder) 2022年4月19日

午前10時くらいにABC248に提出するとめちゃくちゃジャッジが詰まっていて、何かと思って全体の提出を見ると、Ex問題に延々無限ループを投げ続けているアカウントがあった。
週記（2022/04/11-2022/04/17） - kotatsugameの日記

シャワーを浴びたら少し目が覚めたので、コンテストに出ることにした。午後11時半からCF #783 div.1。

Dashboard - Codeforces Round #783 (Div. 1) - Codeforces

Aは250点がつけられており、瞬殺しなければならないという意気込みで臨んだ。 $b$ はどこか1か所で必ず $0$ になるべきなので、その位置を全探索する。すると残りは左右それぞれ貪欲で良い。一応、値があまり大きくならないことも確かめた。素直な考察で解けて安心。Bは難しい。まず考察として、総和が正にならない連続部分列は1要素ごとにバラしても損しないことがわかる。あとは総和が正になる場合。累積和を座圧してインデックスにしたセグ木があれば、1点更新区間MAXで貰うdpが計算できそうだな、しかし $n\le 5\times10^5$ だしちょっと不安だな……と思いつつTLを見たら、なんと4secだった。これに気付いて、解法が正しいことの確信を得た。

Cは実験。まず、他の駒を飛び越えてよいのか気になったが、代わりに飛び越えた駒が移動すると考えればよいことに気づいた。左上から埋めていく枝刈り全探索を書いて回し、出力を図に書いてみると、何となく構造が見えた。左上に駒を固めて置いて、縦横の移動で行と列をある程度潰し、最後に残った長方形領域を斜めの移動で潰す。どのような置き方をしても残ったマスは（間隔の空いた）長方形みたいな形をすることになるので、この考え方は不変。残る長方形を効率よく埋めるにはできるだけ固まってくれたほうが嬉しいので、左上に駒を固めて置くのもそう決め打ってよい。駒を $k$ 個置くとすると、残った長方形は縦横 $n-k$ で、対角線の本数 $2(n-k)-1$ は $k$ 以下である必要があるため、逆に $k\ge \lceil(2n-1)/3\rceil$ とわかる。実験の範囲では、この下限が達成できているようだ。

あとは、それを満たすような構築を探る。 $k$ が奇数の場合が一番ギリギリなので、それをいろいろ試してみると、右上から左下の向きの線を2本引く感じに置けばよいことが分かった。それぞれ $(k+1)/2$ 個と $(k-1)/2$ 個で、縦横が被らない範囲で詰めて置く。 $k$ が偶数の場合は、 $k\leftarrow k-1$ の場合の構築をした後 $(k,k)$ に置けばよい。念のため $n\le 1000$ を全部試してから提出した。

Dは当然難しい。そもそも眠気が強くなってきて、考察しながら意識を飛ばしそうになっていた。しばらく考察して、頂点の次数に着目するといい感じなことに気づく。次数は、最初の時点での偶奇により、偶数→奇数の変化の回数と奇数→偶数の変化の回数がそれぞれ固定できる。この変化が辺の両端点で一致するときにその辺を削除できる。木dpすることを考えると、変化のどちらが余っているかを状態として持つことになりそう。dpした後もう一度dfsすることで復元も可能に見える。書いて、2ペナかけ残り10分時点で通った。復元するときに操作列を連結する操作が必要になると思ってlistのマージテクを書いたのだが、うっかり片方を反転してしまう実装になっていたのが1ペナ。実際は操作列を後ろに伸ばすことしかしないので、完全に無駄な工夫だった。

4完49位で2881→2887(+6)。結果的には出てよかった。

午前2時から日記を書き始めた。途中で昔読んだハーメルンを読み返したりしつつ、午前5時くらいに切り上げて布団に移動。そこからハーメルンの更新を読み始めたが、耐えられずすぐに寝落ちした。

04/20(水)

正午くらいに起床。

そのまま布団でハーメルンを読み、1作読了。「解説の宮永さん」。原作は少しだけ読んだことがあるはず。その内容の記憶はないが、面白かった。主人公が強いので。相手の能力に対するメタの強さというのもまた一味違った無双で良かった。

syosetu.org

この作品の「読者層が似ている作品」から別のハーメルンを1作読み始めた。午後5時くらいに寝落ち。

04/21(木)

04/20 午後11時半ごろ起床。水曜日がほぼ終わってしまっている。先週木曜日、先生からグラフ理論の論文を紹介してもらって、次の次の週に少しセミナーしてくださいということを言われていた。つまりまだ1週間猶予があるわけではあるが、それにしても1週間読んでみてどんな感じだったかは言えるべきだろうし、もし手も足も出ないほど難しかったらそのことを伝える必要があるので、今週のうちにある程度読んでおかなければならなかった。ということでスマホにPDFをダウンロードし、ハーメルンと交互に読み進めていた。

午前6時に再度入眠し、午前10時に目覚ましで起床。それからもまた同じことをしていた。論文のほうは飛ばし飛ばしで1つを眺め終えた。眺めているだけでは何もわからない、というのはそれはそうとして、別に読めないわけではなさそう。ただ用語がところどころ怪しくて、少なくとも何か参照するべき教科書が必要と分かった。

午後1時に布団から脱出。とりあえず学食に行って食事し、予約していたラノベを受け取って一旦帰宅。荷物を置いて、今度は山に登った。

今週は、博士課程の留学生の方が研究していることについてセミナーしてもらうという内容。もうめちゃくちゃ大変だった。まず英語が聞き取れない。統計学の話のため語彙が全然なかったことが一番の問題じゃないだろうか。数式をいろいろ書いてもらい、ようよう理解していくような形だった。そんなことをしていたら当然発表は先に進まず、先生の指示でかなり序盤のほうで切り上げることになり、最後は線形代数に関する単純な事実を一つ確認して終わった。これについても学部時代の知識がほとんど抜けており、大変苦しんだ。

院生室に寄ると人がいたので、一緒に学食で食事し、路上で1時間ほど駄弁って帰宅。即座に布団に入り、午後8時半就寝。

04/22(金)

午前2時半起床。ハーメルンを読み続け、1作読了。「プレイしていたゲームの能力で転生するやつ」。

syosetu.org

「魔法先生ネギま！」は途中まで読んだことがある。大変面白かった記憶。ではなぜ途中で止まっているかというと、その漫画が自分のものではなく、途中から自分で買う気力もなかったため。中途半端にしか内容を知らないので、二次創作を読むのを微妙にためらっていたのだが、ついに手を出してしまった。こちらもめちゃくちゃ面白かった。設定としては、オリ主が大量の別ゲーキャラの能力をネギま世界に持ち込むといういかにも地雷っぽいものである。しかし原作キャラとのバランスが良かった。オリ主が当然強い一方で、原作で強いキャラも強いままに描いてくれている。

そのあとPixiv小説やノクターンノベルズをいくつか漁り、午前8時くらいに起き上がった。YouTubeを見たりカクヨムを読んだりしていたら午前11時。学食に行って食事し、予約していたラノベを受け取って帰宅。

食事 pic.twitter.com/UKU66VG9rF
— こたつがめ (@kotatsugame_t) 2022年4月22日

昔、個数制限なしナップサック問題の解って言われたことがある
— こたつがめ (@kotatsugame_t) 2022年4月22日

「個数制限なしナップサック問題の解」と言われた。
週記（2021/05/10-2021/05/16） - kotatsugameの日記

帰宅して即座に布団に倒れこむ。しばらくラノベを読んで、午後1時就寝。

04/23(土)

04/22 午後11時起床。ラノベを2冊読んだ。

1冊目、「鴉と令嬢」。面白かった。主人公が強くて嬉しい。学校では実力を隠していて、さらに嬉しい。テロリストが襲ってくるシーンがあって、1巻から隠された実力が明らかになるかと思ったが、今回は陰からのサポートにとどまった。どのタイミングでどれだけの人に実力が知れ渡るのか、以降の展開が楽しみ。またヒロインに学校で声を掛けられて目立ってしまうシーンも好み。様々なラノベで使われるだけの良さがある。

異能強度という10段階の指標が用意されていた。これの分布についてはちょっと疑問が残る。下から3段階に7割がいて、下から6段階では9割になる。一番上の段階は0.00001%らしい。正規分布の上側だけで考えれば、順に $0.5\sigma$ 、 $1.3\sigma$ 、 $5.2\sigma$ くらいで、間隔がよくわからない。また、上から4段階までの人間は1割もいるのに希少と言っていたのも正しくは見えない。その位置にいるヒロインに訓練の相方が見つからないという描写があったが、複数クラス合同の授業でそのレベルの人間が1人しかいないということはないだろう。ただ、冒険者ランクなどの分布に言及している作品で感覚的に正しいことを言っているものを読んだことがないので、仕方ないのかもしれない。

この作品はカクヨムコンの受賞作らしい。ということはカクヨムで探せば続きが読めるのでは？と考えてコンテストページを確認して、もとになったものを見つけた。しかし1巻分しか連載されていないようだ。残念。いや、最近こうやって見つけたネット小説に時間を吸い取られることが多かったから、そうならなくてむしろ良かったのかもしれない。ところでこの作品は書籍化に当たって改題されていて、もともとはネット小説にありがちなあらすじそのままのタイトルだったらしい。シンプルなタイトルからあらすじタイトルへの改題はよくTLで話題になっているが、逆は初めて見た気がする。知らなかっただけか。

2冊目、「俺は星間国家の悪徳領主！」5巻。相変わらず良かった。ただし何が良かったのか言語化するのが難しい。設定とキャラがめちゃくちゃ気に入っているから当然好き。仕方がないのでこの巻で好きだったシーンでも挙げておこう。やはり第七話「剣聖」とその前のバトルシーンだ。主人公が存分に無双しているのは読んでいて楽しい。

さらに別のラノベを開いて少し読んだ後、午前10時に就寝。次、午後4時半に生協の弁当を受け取るため起きて、そのあと二度寝できなかった。ハーメルンやカクヨムの更新を漁っていると時間が過ぎて、午後7時くらいになって布団から出た。

食事したりちょっと日記を書いたりして、午後9時からABC249。

Monoxer Programming Contest 2022（AtCoder Beginner Contest 249） - AtCoder

Aはどう見ても短くはならないので、先にBを解いた。sedで条件を3つ書く。次にAに戻って、とりあえずC++で通すことにした。 $X$ 回ループを回すのが一番簡単そう。以降もC++。Cは「ちょうど」 $K$ であることに気づかず1WA。Dはサンプル3が合わなくてしばらく苦しんだ後、どこにも $(i,j,k)$ が相異なるとは書かれていないことに気づいた。優しすぎ。この場合出現回数をカウントした配列 $c$ を作って、 $c_ic_jc_{ij}$ を $1\le i,j\le 2\times 10^5$ で単純に足し合わせるだけでよくなる。調和級数。

Eはなかなか難しい。適当にdpを書こうとすると、 $X$ の長さと $Y$ の長さを次元に持って、さらに遷移が $O(N)$ になってしまう。ここで遷移をよく見ると区間加算の形で書けるため、imos法で高速化。Fは簡単で、 $t=1$ の操作を決め打って、以降の $t=1$ の操作を全部無視した後 $y\lt 0$ の操作もできる限り無視するのが良い。後ろから計算し、無視できる $y$ の集合を優先度付きキューで管理することで $t=1$ の操作を全部試せる。 $(t_0,y_0)=(1,0)$ という操作を追加すると実装が簡単になる。キューの中身を正しく動かすのに失敗して1WA。

Gは難しい。しばらく考えていると $A_i\times 2^{30}+B_i$ の基底を取ればよさそうなことがわかってきた。 $A$ の上位bitから決めて、あるbitを入れない代わりに残りの基底をどれでも使っていい状態を計算する、というのを繰り返すことになる。最後、 $A$ の総XORがちょうど $K$ になる場合も別で計算しておく。カードを1枚も選ばない状態を検出するのが難しい。まず基底が $N$ 個未満だった場合は、総XORを $0$ にできるので、答えの最小値は $0$ になる。そうでない場合に $B$ も含めた総XORが $0$ になることはないので、逆にそうなったら1枚も選んでいないとわかる。判定の位置をミスしたため1回目にACした提出にはHackケースが存在するが、通った。

Exは全く分からず、7完8位。賞金が得られそうでうれしい。

コードゴルフ。Aはdcで $O(1)$ 解法を書いた。Bはコンテスト中にテストケースハックで少し縮んでいた。大文字と小文字が両方出現することをチェックするとき、大文字と小文字がこの順で隣接していると決め打ってよい。「この順」というのが嘘。CはRubyだと思っていたらPerlで縮んでいた。粗探しして-1B。DはAWKで、カウントのループと答えを求めるループをまとめた。といってもループの最初のほうでカウントして、カウントが終わってから答えを求め始めるだけ。ちょっといじってループ回数を少しだけ減らし、何とかTLEの回避に成功した。以降は手付かず。

午後11時半からCGR20。

Dashboard - Codeforces Global Round 20 - Codeforces

Aはよくわからなかったのでgrundy数で解いた。解説を見たら、操作によらずゲームが終了するまでのターン数が決まるようで、確かに……という気持ちになった。Bは'B'よりも前にある1個以上の'A'と一緒に消すと考え、後ろから見て「まだ'A'とくっつけられていない'B'の個数」を管理すれば判定できる。末尾が'B'でない場合は場合分けで取り除いておく。Cはdpしそうになったが、面倒そうだったのでちゃんと考察して解いた。1回以上操作するなら最後に操作した位置で必ず $a_i=a_{i+1}$ となるので、もともと同じ値が隣接していた位置をすべて含むように操作しなければならない。そのような位置の両端を調べて間を埋めるための操作回数を計算する。調べた値から1回も操作しなくてよい場合も検出できる。

Dは操作を、 $a_r$ の直前に $a_l=a_r$ を挿入すると捉える。両方の数列を後ろから比較していって、異なった場合はこの操作で前から持ってきたことにするか、もしくはそこから後ろに飛ばしたことにするか。前者を優先的に使う。Eはまず $h_w=1$ となるような最小の $w=w_0$ を二分探索で求め、以降は行数を全探索する。行数 $h$ に対しては $w=\lfloor (w_0-1)/h\rfloor$ として $h_w=h$ であることをチェックするだけでよい。もし $h_{w-1}=h$ だった場合、1行にまとめたときの幅が $hw$ 以下と分かって $w_0\le hw\le w_0-1$ になってしまうから。この問題はシステスで結構落ちていて、みんなうっかり $w=0$ でクエリを投げてしまっていたようだった。自分は $h=1$ をスキップしていたので助かった。

F1は簡単。2点swapなので、値たちを頂点とし、操作前と操作後を辺で結んだときの連結成分数を最小にしたい。値ごとの出現回数 $cnt$ を求めると、連結成分数は必ず $\max cnt$ 以上になって、これが達成可能。実装は、値ごとに出現する位置をvectorで持ち、それらの先頭 $1\le i\le \max cnt$ 番目だけを取り出してループにするのが簡単だった。F2は同様の考察から連結成分数が必ずこの値であるか調べればよい。連結成分数がこれより増えるときは、必ず1つ以上の閉路が ${\rm argmax}\;cnt$ を含まないので、逆に ${\rm argmax}\;cnt$ からスタートして同じ値を2度含まない閉路だけで全部の辺を取り切れるかチェックすることになる。よく考えると、これは ${\rm argmax}\;cnt$ に接続された辺を全部削除した後のグラフがDAGであるかチェックする問題になる。

ここまで1時間もかかっておらず爆速で、F2まで通した時点では全体5位だった。その時点ですでにH問題にそれなりのsolvedが出ていたのでGを飛ばすことにした。しかし以降2時間手も足も出ず、そのまま終了。最終的にH問題は100人以上が通したため87位まで落ち、レートは2887→2868(-19)。Eのシステス落ちが結構いて少しだけ傷が浅くなった。

コンテスト中のHの考察について。010...や101...のグループに分割して、左端から貪欲に繋いでいくのがよいと考えていた。ある2つを繋ぐときは、その間にあるグループを先に全部削除しておく必要があるので、繋ぐ関係が交差してはいけない。「現在末尾が0・1のグループが左にあるか」を持つ4状態のdpを書いてみると、遷移が足し算とminの操作によって行列とみなせる（トロピカル半環）ため、これをセグメント木なりに乗せればクエリに答えられる。しかし5ケース目で落ちたまま一生先に進めなかった。ランダムケースを書いてみるも、そもそも正しい答えを計算するのが難しい。誤った考察を元にコードを書き、ランダムケースの出力もその方法で作っていたので、当然それで落ちるわけもなかった。

正しくは00や11の個数に着目して、その多いほう $+1$ らしい。一度の操作ではそれらを最大2つ巻き込むことができるが、00と00を巻き込んだ場合は残った0と0がくっつくので00は1個しか減らず、00と11を巻き込んだ場合はどちらも1個ずつ減る、という考察で示せるようだ。考えもしなかった。

夜中、日記を書きつつハーメルンを1作読了。「とある転生者の遊興日記」。前世の知識で競馬で大儲けする話だと思ったら、あれよあれよという間に雑誌記者になっていた。物語として面白かったが、逆行転生大好き人間としては最初1、2話の雰囲気が良かった分、後半はあまり……。

syosetu.org

布団に入ってラノベを開いたら即座に寝落ちした。午前8時前のはず。

04/24(日)

午後2時半起床。布団にラノベが落ちていて焦る。特に曲がったりはしておらず、安心。食事して、午後3時からAHC010に出た。

ALGO ARTIS Programming Contest 2022（AtCoder Heuristic Contest 010） - AtCoder

とりあえずコードゴルフ。0を900個出力するより $10^{899}$ を出力するほうが短くなった。dcやbcは途中で改行されてしまい使えないため、Ruby。以降は普通に参加した。ビジュアライザが手元で動かず、Rustをアップデートした。

大まかな方針としては、外側のループと内側のループに分けるというもの。左上にある右と下に繋げられるパーツを決め打ってループを作りたい。ただし道が互いに干渉しないようにする必要がある。そこで、スタート位置から $i-j$ が一定になるような直線で領域を切り、右上と左下からはみ出ないようなパスを作って最後に繋げることにした。パスを作るのはBFS。BFSで状態を溜めるqueueをstackにしたらよいのではないかと思っていたら、これまでの道と干渉してしまった。

何とかループを作れるようになった後は、外側と内側に分ける方法を実装する。ループを作るときに「使ってよいマス」を指定できるようにして、外側のループは端から何マス、内側のループはさらに端からもう何マス……とする。どうしてもBFSということから真ん中を通る最短距離のループを作ってしまいがちなので、手動で真ん中を通らないように指定している。これで見つかった解を出力すると411868点、スコアを計算する関数を実装してmaxを取ると2205256点に爆増した。

BFSを何とかする。とりあえずstackに置き換えて、これまでの道と干渉しないように一度踏み入ったマスは二度と使わないようなコードを書いた。もちろん「これまでの道」ではないマスも使えなくなってしまう場合があるが、しょうがない。この変更を入れると結構ループが伸び、また実行時間にも余裕が出たため探索範囲を拡大することができて、3062504点になった。

以降はループの途中を切って伸ばすための実装していたが非常に難しく、結局REが取れないままコンテスト終了。直後に正常終了するコードが書けたものの、点数は伸びていないので、おそらく実装が正しくないのだろう。55位でパフォーマンス2118、レートは1836→1910(+74)。

seed0 なんでこんな風に分けたんですか？ pic.twitter.com/VTud6t35iP
— こたつがめ (@kotatsugame_t) 2022年4月24日

TLでAHC002と似ていたという話をよく見た。言われてみれば確かにそう。さらに、マス目をいくつかの区域に分割してそれぞれdfsし、適当に接続するという方針を取った人もいた。これは僕のAHC002における解法とほぼほぼ同じであり、非常に悔しい気持ちになった。分割しなくてもdfsは効くらしくて、時間を決めて回すとか、一度訪れたマスのフラグを消さないとかの方法を見聞きした。

午後9時からARC139。

AtCoder Regular Contest 139 - AtCoder

Aは簡単。先頭から条件を満たす最小の数を求めていけばよい。基本的には $A_i=\left(\lfloor A_{i-1}/2^{T_i}\rfloor+1\right)\times 2^{T_i}$ になる。ただこれだとサンプル4で落ちる。括弧内が奇数でなければならないことに気づき、 $1$ とbitwise ORした。

Bは難しい。 $kA+lB\le N$ なる $0\le k,l$ に対して $NX+k(Y-AX)+l(Z-BX)$ の最小値を求めることになる。まず $Y\leftarrow \min(Y,AX)$ 、 $Z\leftarrow \min(Z,BX)$ としてよい。このとき $l=\lfloor(N-kA)/B\rfloor$ とできる。 $0\le k\le N/A$ を全探索するのは不可能なのでもうちょっと考察が必要。 $N$ は $AB$ で割ったあまりを考えてもいいんじゃないかと思って実装し提出するとWAになった。これがなぜか全然わからず、ずっと紙でいろいろ計算していた。どうしてもわからないのでランダムケースをたくさん試すと、 $(7,2,3,10,5,5)$ というケースで落ちるのを発見した。もうダメダメ。

$k=k_1+k_2B$ と分解する。 $0\le k_1\lt B$ を全探索すると、 $k_2$ としては $0$ か上限ギリギリだけ考えていいようだ。このことは、スコアが $k_2$ の一次関数になることからわかる。探索回数は $\min(N/A,B)$ になって、 $A\ge B$ となるようswapしておけばこの値は $\sqrt{N}$ 以下になることがわかる。これで解けた。

Cはめちゃくちゃ難しい。選ぶ点のどのペアも、 $(\pm 1,\mp 3)$ と $(\pm 1,\mp 3)$ で互いに移り変わらない必要がある。片方だけ考えると、幅3の棒とそこから横に生える幅1の棒みたいな領域の点集合になるようなので、これをうまくずらして重なる点をできるだけ増やすことになる。 $Y=1$ 全部と $X=N$ 全部と左下の3x3正方形、を提出したらWAになった。もうちょっと重ねられるということなのでいろいろ構築方法を考えていたが、頭が爆発しそうになったので方針を変えた。

$(x,y)\mapsto(3x+y,x+3y)$ と変換する。変換後の $x'=3x+y$ 、 $y'=x+3y$ は互いに一致してはならないので、とりあえずそれぞれありうる値を列挙する。 $(x',y')$ から $(x,y)$ を復元することができるので、 $(x',y')$ のペアを数えればよい。復元した $(x,y)$ は整数で、かつ値の範囲の制限がある。整数であるという条件は $x'\bmod 8$ と $y'\bmod 8$ を固定することで達成できる。値の範囲の制限については、 $x'$ と $y'$ を昇順に並べておいて、値が範囲から外れていたらその外れ方に従ってどちらかを1段階大きくするという方法で探索し、ペアを作ることにした。これで出したら通った。残り時間は5分だった。

3完101位。人生終了。

コードゴルフはA問題のみ。Aは最初に書いたdcがTLEしたのでとりあえずPerlで通しておいたが、朝方書き方を変えたdcコードを投げてみると通った。偶奇に従って値をずらす部分でmodつきpowを使うのは遅いらしい。単に2で割った余りを使うとコード長据え置きでかなりの高速化になった。オーダーレベルの改善なのでそれはそうか。

ARC-Dを通した。Cを通した後に少し考えていて、削除しなかった場合の数列を作って小さいほうから $X,\dots,X+K-1$ 番目を削除すると考えればよいだろうと思ったのだが、これはどう頑張っても計算量が $O(MK^2)$ になる。どうしようもなくなったので解説を見た。数列の値を2値にするのは頭が良すぎる。これで、これまでdpの遷移として $0\le i\le j\le K$ なる $i\rightarrow j$ を全部試さなければならなかったところを、 $0\rightarrow i\rightarrow K$ だけにできるようになる。必要な係数については依然として $i\rightarrow j$ を全部試す必要があるものの、多項式の掛け算と見なして前計算することで $O(MK\log K)$ で求まる。十分間に合うようだ。

Submission #31251400 - AtCoder Regular Contest 139

多項式の掛け算というか、 $f(x)^k\bmod x^{K+1}$ を $0\le k\le M$ で求めることになる。 $f(x)$ のフーリエ変換後を保持して、値だけ $k$ 乗した後戻してもよいという話を聞いた覚えがあって、定数倍速そうに見えた。しかし合わない。いろいろ試してみて、そのようなテクを使うには最初から長さ ${\rm deg}\;(f(x))\times M+1$ の列をフーリエ変換しておく必要があると分かった。冷静に考えると当たり前で、フーリエ変換後の値たちは $f(x)^k\bmod x^{K+1}$ ではなく $f(x)^k$ そのものを表現しているのだから、長さが足りないまま復元すると高次の部分だけずれてしまう。変換後の値をべき乗することで変換前の式のべき乗が求まる話は、思い出してみればbit演算系の畳み込みで聞いたはずで、そちらは列の長さが変化しないためそもそも高次の部分が出現し得ないという理屈だったと知った。