週記（2021/07/05-2021/07/11）

07/05(月)

先週の週記の続き。月曜日の典型90問084は余事象を考えるやつだった。先頭から順に見て、今何文字目かを答えに足し、現在同じ文字が何文字連続しているかを引く、というアルゴリズムを考え、Perlで書いて45Bになった。

さらにしばらく土曜日の典型90問083と格闘していた。まっとうな解法で縮めるのはあきらめ、例えば辺を適当に向き付けたら間に合わないかだとか、隣接リストの先頭500要素だけ見たら通らないかだとか、そういうことばかりやっていた。本当は隣接リストからランダムに選ぶのをsampleメソッドで行いたかったのだが、TLEしてしまった。実装を見たところ、n\ge 2個の要素を抜き出すときは「リストの先頭からn個取り、残りと入れ替えたり入れ替えなかったりする」というアルゴリズムで動くようで、常にリストの長さに対して線形時間かかるらしい。それもそうか。重複チェックするのも重いだろうし、重複を気にしないなら1つ抜き出すのをn回行えばよい。

crystal/array.cr at 3c48f311f98e95964d425abe23d2b353b7da07d1 · crystal-lang/crystal · GitHub

結局縮まなかった。布団に入って人の日記を読んでいたら寝落ちした。午前10時半くらいだった。

その後午後4時から午後5時まで目覚めていた形跡がある。ほかにYouTubeアプリで動画を視聴していた時間があった気もするが、よく覚えていない。

07/06(火)

午前0時半くらいに目を覚まし、昨日の典型90問が縮められていることを知った。42B。即座にスマホでコードを縮めにかかった。新しいアイディアとして「自分と異なる文字が最後に出現したインデックスを答えに足す」というのが思い浮かぶ。今回の問題だとこれが特に有用で、'o'（文字コード111）と'x'（文字コード120）のxorが23なので、$_に対して自分と異なる文字は$_^v23で得られる。

ここでv23はPerlにおけるバージョン文字列で、文字コード23の文字1文字からなる文字列である。実際のところクオーテーションで直接埋め込んでも長さは変わらないが……。このバージョン文字列のテクニックは、特に古い問題で$/を書き換えた後に改行を得るため使われていた。v10だ。

version - バージョンオブジェクトのための Perl エクステンション - perldoc.jp

$$_=${$_}と${$_^v23}を使うことで変数$oと$xを自在に使い分けられるので、あとは片方に現在のインデックスを代入し、もう片方を答えに足せばよい。しかしピッタリ42Bだった。

寝たままずっと動画を見ていたが、午前4時に布団を出る。人の日記を読んだ後、ABC208-Eをoptさんのユーザ解説をもとに縮めたが、縮め切れておらずさらに短縮されてしまった。

ラノベを読んでいたら今日の典型90問の公開に微妙に遅れてしまった。今日の典型も星は少なめ。しかしどう解いたものか結構迷って、最終的に1012以下の高度合成数を求めて（プログラムはQiitaから拾ってきた）約数の個数が十分小さいことを確かめ、約数全列挙で通した。

コードゴルフについては、この方針でRubyコードが通るようだったが、やはり長い。約数全列挙しない方針はないものかと考え、1\le a\le \sqrt[3]Kとa\le b\le\sqrt{\frac K a}を全探索することにした。a\mid Kという条件で枝刈りしてもRubyでは通らなかったが、Crystalでは素のまま余裕をもって間に合う。70B。計算回数はK=10^{12}でおよそ1.5\times10^8ステップくらいとなる。

昨日の典型90問をさらに縮めることに成功した。わざわざ${$_^v23}で自分と異なる文字の変数を持ってこなくても、$o+$xから引けばよい。これで41B、さらに出力部を改善して40Bになった。出力部の改善についてはほかにもいくつか適用できる問題があったため、探して縮めておいた。

atcoder.jp

$\に答えを保存しておくことで、ただprint関数を呼び出すだけで答えが出力されるというやつ。これまでは最後に;printとしていたのだが、このセミコロンは消せる場合がある。具体的には、直前の式を弄って無意味な比較などをし、得た偽の値=空文字列をprint関数に渡す。

昼までに橙diffを4問通した。先週の週記では問題リンクを貼っていたが、今日からは自分の提出へのリンクを貼ることにしよう。

Submission #24018337 - AISing Programming Contest 2019

かなり昔から、解法が2乗の木DPであることは知っていたはずだが、何度か挑戦して解けずにいた問題。しかし今見てみれば面倒なだけでかなり明らかだ。この問題が600点で最後に残った問題、のはずだったが、今調べてみると「Two Snuke」も解けていなかった。

Submission #24020011 - Code Formula 2014 本選

面白い。最大・最小の円盤の位置で分割することばかり考えていたが、それだと全然よくない。計算量評価をしようとすると、クイックソートの最悪計算量というのが思い出されて、そのつながりでマージソートにたどり着いた。そこからも微妙に面倒で、僕の実装ではiの杭にある円盤をソートされた状態で「iの杭に重ねる」関数と「j\ne iの杭に重ねる」関数の2種類を実装する必要があった。

Submission #24020511 - AtCoder Regular Contest 034

各a_iの寄与にばらして求める。これは、a_iが引かれてからゲームが終了するまでに何枚bのカードを引いたかを全探索し、bの積は事前にDPで求めておくことで計算できる。値が非常に大きくなりそうでびっくりしたが、古い問題にありがちなdoubleで計算するやつだった。

Submission #24021063 - Yahoo Programming Contest 2019

結構難しい。行aとbには4通りの選び方があるが、これはaとa\oplus bの選び方と等しい。同じことが列にも言えるので、結局入力の行列を標準形（これはWikipediaにあった用語で、単位行列が尻切れトンボみたいになっているやつ）に直すことができる。あとは簡単で、普通に線形時間かけて計算してもよかったのだが、2項定理を正負足し合わせて打ち消すようなことをすれば閉じた式で表せることに気づき、それに時間をかけた。しかもmodミスで1WA。

最後の問題のコードゴルフもした。行列のランクが求まればいいので、いつものnoshi基底を使う。\mathbb{F}_2行列の掃き出し法をするといえばARC054C-鯛焼きが思い出されたので、そのコードを参考にゴルフしていたら、ARC054Cのほうのコードも縮んだ。

atcoder.jp

昼過ぎ、学食に行く。ご飯の特大サイズの提供が再開されたらしいので注文した。

平常時はご飯（特大）を注文していたが、今日は提供されないらしかったので、迷った挙句ご飯（大）とご飯（中）を購入した。ちょっと多かったので、次回は中サイズを2つ注文することにしよう。

週記（2021/05/10-2021/05/16） - kotatsugameの日記

帰ってきてラノベを読んでいた。メールが来たのに気づいて確認すると、急に明日午後1時までのレポート課題が生えていた。実はこれは全然急ではない。数学基礎論の講義3回ごとに出されるレポートの1つなので、同様のものを今セメスターすでに2回提出している。今回は課題の提出場所を作っていなかったので今日になって課題が生えたように見えたというわけで、講義が3回ぶん溜まっていることを知りながらClassroomで資料を確認しなかった僕が全面的に悪い。

しかし、あと24時間で講義3回分の資料を読んでレポートを作るというのは……ヤバい。あまりにヤバいので現実を放棄して、読んでいたラノベをまず読了した。

「居候先の三姉妹がえっちなトレーニングを求めてくる」。タイトルから伺えるようにお色気路線のラノベで、実際巻頭のカラーイラストも設定・文章でもそういうシーンが多々挟み込まれるが、ストーリーとしては普通にスポーツを頑張っていて、純粋に面白かった。特に終盤出てきた悪役っぽい人がそんな悪い奴ではなく、主人公も悪印象を抱いていないようだったのがグッときた。初登場のシーンから受ける印象で悪役と書いたが、どちらかというとライバルだったのだろう。

満を持してレポート作成に取り掛かる。これまで講義の担当の教員が作成した資料を使用してきたが、今回のレポート範囲については、別のテキストの一部を著者の厚意により配布し、それに沿って進めるらしい。そちらのテキストのほうが丁寧でわかりやすいように感じた。

こうなることが明らかだったので、これまでの2回のレポートから一転今回はTeXを使用している。特に2重になっている角かっこllbracket、rrbracketなどは1回打つだけでも頭がおかしくなっちゃうので、初めて自分でコマンドを定義したりしてみた。TeXのプログラミング言語らしさを感じて楽しくなった。TeXはチューリング完全！

しかしこの調子で命題を3つ証明するのはさすがに面倒が過ぎた。終わったところで力尽き、午後9時くらいに布団に入る。そこからしばらくなろうを読んで、午後10時半就寝。

07/07(水)

午前5時起床。二度寝しようと思っていたがうっかりなろうに手を出してしまい、眠気が消えうせる。午前7時半くらいになって、今から寝るのはさすがにまずいということで布団から出た。

今日の典型90問を解く。解法は一瞬だが実装方針でちょっと迷い、コードを書いたり消したりしていた。しかし何とか書き上げて通す。どうやら今日こそはFAが取れたらしい。コードゴルフは素直なRubyコードで131B、ちょっと捻って128B。

昨日のレポートの続きをする。以前と同じく10問の問題から5問以上選んで解く形式。昨日で3問の問題が解き終わっていて、残り2つ。期限まで6時間くらいあるし簡単だろうと思っていたが、選んだ問題の1つが非常に難しく、かなり長い間考えていた。

ゲーム意味論におけるモデル検査ゲームに関する問題で、モデルMのグラフが2種類のラベルa,bを持つとき、始点から出発して「無限回aの辺を含むようなパスがあり、かつ無限回bの辺を含むようなパスはない」という意味の様相\mu論理式を作れ、という問題。無限回bの辺を含むようなパスを確実に検出するために、最初に\forallが駒を動かせるようにしたいが、すると今度は\existsが無限回aの辺を含むようなパスに行けなくなったりして、大変難儀した。

一度は不可能なのではないかと思って、不可能なことを極端なグラフをいくつか取り上げて論証しようとしたが、それを考えているうちに進展があった。つまり、\forallはゲームに負けないのが目的であって、誤った結果に誘導するのが目的ではない。これをもとに、最初に\forallが「今後駒を動かすのが\forallか\existsか」を選ぶことで、うまく求める論理式を構築できた。(\mu x.\nu y.(\Box_b x\land\Box y))\land(\nu z.\Diamond z)である。

何とか解けて、5問完成。興が乗ったのでもう1問解いておいて提出した。期限の30分前だったので、まあまあ余裕があった。

今日も学食に行こうとしたが、外は雨が降っていたしなんとなく眠気もあるので断念。七夕なので特別メニューが提供されるという話があった気もするが、あまり興味はない。

なろうを読んだり週記を書いたりしていたら、昨日と今日の典型90問が縮められていた。昨日の問題はどこが縮んだのかわからないので諦めて、今日の問題について考える。冷静になると、Rubyの数値に配列のようにアクセスすることでその位置のbitを取得する機能を使っていないことに気づいた。それを使って124B。調べてみると、これも配列と同様に連続したbitを一気に取得するような機能が追加されていたらしい。なかなか面白いが微妙に使いにくく、今のところこれで縮むコードは思いついていない。

Integer#[] (Ruby 3.0.0 リファレンスマニュアル)

昨日解いた問題から1問コードゴルフをした後、橙diffをさらに3問解いた。

Submission #24046495 - Dwango Programming Contest 6th

前のほうを貪欲に取って最後全探索して無理やり帳尻を合わせる、ということを考えたが、この場合他の要素の後ろに来れないものがあった場合に破滅する。この破滅する条件を発展させると、前をいくつか決めたところで「必ず残りの列の先頭にいなければならない要素」が出現したときにそれを置くようにすればよいことがわかる。最後3要素はうまくやらないとこれまた破滅するが、そこの条件を間違えて1WA。

Submission #24048310 - AtCoder Grand Contest 019

ずらしつつ1を0にした後、最後に一気に0を1にする、という順の操作と固定してよいことがわかる。ここで最終的にずらす幅を全探索すると、ずらす途中に0にできる1とできない1が存在する。できないものについてはもう少し余計にずらしてつじつまを合わせる必要があるが、この時必要な幅を左右で計算しておいて、「全部左でつじつまを合わせる」状態から「全部右でつじつまを合わせる」状態に1個ずつ変換していく過程で左右で必要な幅の合計を毎回計算し、最小値を求めればよい。

Submission #24048744 - Dwango Programming Contest 6th

解法を覚えていた。あまりに衝撃的な数え上げ。しかもここで知っておきながら、すぐ後に出た似たような問題も落とした覚えがある。もう忘れないようにしたい。

今日の典型90問がさらに縮められていた。123B。僕のコードも、初期値が何でもよい変数を宣言するのに、配列の先頭要素を取得するn,=の空いていたコンマの横に押し込んで-1Bできた。これは悔しい。そもそも初期値がなんでもよいことを自覚していなかったようだ。

さらに橙diffを1問解いた。

Submission #24050436 - AtCoder Regular Contest 075

大きな桁は打ち消しあわないとダメだろと思っていたら、残りの桁全部が打ち消すことでもOKらしく、数ケースWAが出てしまった。最終的に大きな桁は極端な値しか調べないようにしたら通った。解説はもっと考察していて頭が良い。大きな桁じゃなくてもできるだけ打ち消しあっておく必要があって、少しでも残ってしまったら以降の桁はすべてその解消に専念する必要があるらしい。

RecommendationのEasyを下から解いてきたが、今一番下にはハシポンがいる。嫌なので見ないふりをしている。それ以外で次に解く問題を頭に入れ、午前1時半就寝。

07/08(木)

午前7時半、目覚ましにより起床。今日の典型90問の公開を待つ。二分探索+ワーシャルフロイドのはずが、焦って辺ごとに二分探索しようとしてしまった。さらに二分探索の初期値を間違えて1WA。散々な結果だ。

通してから布団に戻って二度寝した。午前8時から正午まで寝ていた。

起きたらABC208Cが縮んでいた。インデックスを含めてソートしていたが、そんな必要はなく、小さいほうからK%N番目の要素を持ってそれ未満か以上かを確認すればよい。これは僕の前最短コードのアルゴリズムがアホすぎたから縮んでいただけで、言語を変えればさらに縮めるのは容易。Rubyで通して取り返した。

午後1時からゼミに出席。発表を聞きながら橙diff3問にチャレンジし、2問通した。

F - Distribute Numbers

チャレンジ失敗。

Submission #24055458 - AtCoder Regular Contest 095

昨日の夜頭に入れておいた問題。右から見た累積minの更新点に注目すると、グラフでも1本のパスになる。残りの頂点はどうなるかなと思って考えてみたところ、全部葉になってしまうらしくてびっくりした。あとはパスをどちらから埋め込むかで2通り求めて、辞書順で小さいほうを出力すればよい。

Submission #24055865 - AtCoder Regular Contest 079

簡単。ループ部が問題だが、適当な頂点の現在のMEXを求めると、それがその頂点の値になるか、それともループで1つ先の頂点の値になるかの2通りしかない。

ゼミの最終版、今後の予定を教授が話している最中、急にパソコンが落ちてしまった。慌てて再度起動してZoomに入ったところ、すでに解散しており、教授に呼びかけられてちょうどよいからと面談が始まった。院試についてお話を聞けたりしてかなりありがたかった。教授だけカメラonなのはよくないかなと思い、僕もカメラをonにしたが、パジャマだし背景にはシャツが干してあるしでちょっと恥ずかしかった。

上でチャレンジ失敗と書いた問題をずっと考えていたが、全然解けそうにない。そうこうしているうちにコンテストの時間が近づいてきたので、別の橙diffを通してunique AC 4問にしておくことにした。昨日の最後に通した問題も、日付が変わった後なのでカウントに入っている。

Submission #24060381 - AtCoder Regular Contest 018

最小全域木の辺を交換して同じ重みの全域木を作ろうとしたら、同じ重みの辺と入れ替えるしかない。なので重みごとに辺を見て、辺の使い方の通り数を求める。これは行列木定理を知っていればやるだけ……に見えるが、全域木ではなく全域森を求める必要があることに注意。関係する頂点だけ抜き出して、森を仮想的な辺でつなぐ作業が必要になり、かなり面倒だった。

午後8時からTCO21 R3に出た。2完58位、レート2567→2538(-29)。R4通過らしく、まあ通行料かな……。

Easyは3種の文字の残りをキーに持つdp。僕の実装だと0文字の文字列で壊れて、サンプルにあって本当に良かったという感じ。

Medはより偏りが大きくなるように値をまとめた後、聞かれた回数が多いほうのバッグを判別するだけ。怖かったから慎重にやっていたが、通してみるとすでに黄色が無限人通した後でびっくりした。

Hardに挑戦したがシステス落ち。mapで平面を持ってひっくりかえせるだけひっくり返しまくるようなコードを書き、入力がランダムだからそう酷いことにはならないだろうと提出したが、落ちてしまった。正解は2-SAT。関係するマスが1マス飛んでいるのに惑わされたが、確かに2-SATだなあという気持ちになる。ただ読んでみたコードがどれも異常場合分けで辺を張っていて、かなりつらそう。

システス前はMedを通して80位ちょいだったのでヤバいなあと思っていたが、蓋を開けてみるとMedが焼け野原で、なんとか助かった。

yukicoder 303に出た。5完。

yukicoder contest 303 - yukicoder

A、Bはよい。Cは下のような感じ。Dは適当に深さ優先探索。Fのsolvedが多かったのでEを飛ばす。Fは寄与分を足し合わせる。ある数について考えるとき、それ以外の数は今注目している数より大きいか小さいかにまとめてよい、というのは最近のCF #729 div.2 Dで見た。

000001
000011
000111
112222
122222
222222

その後Eに1時間半ほど費やしたが解けず。僕が考えていた方針は、要素をK個選んでANDを取ることを繰り返し、その答え全部のORを求めるもの。取り出す要素の組み合わせはテストケースを見て選ぶので、場合によっては答え全部のXORを求めても合うようにできる。値を保存するためのレジスタがもう1つ必要で、どうしようもなかった。コンテスト後に解説を読んだところソートと書いてあり、椅子から転げ落ちた。テストケースが入力されるというのは完全なミスリードだったらしい。

ソートは簡単。a bをa&b a|bにすればよくて、(a|b)==(a&b)^(a^b)であることを考えれば、まずXORを番地Nに保存して、in-placeにa&bを作り、最後にその2つからa|bを作ればよい。

コードゴルフ。まず、ACLのデータ構造の宣言について、コンストラクタ呼び出しがあたかもint型かのように代入で行えることを知った。

Submission #24067317 - AtCoder Library Practice Contest

また、下の問題の更新が流れてきて、見ると僕が以前提出していたC言語のものより短い式で計算していたので、それを参考にしてdcで書き直しておいた。多分テストケースハックだと思うが、1か所minを取らなくてもACできてしまい、これがかなり効いた。

Submission #24069050 - 第4回 ドワンゴからの挑戦状 本選(オープン)

布団に入ってすぐ就寝。午前4時だった。

07/09(金)

午前7時半、今日も目覚ましにより起床。今日の典型90問を通す。よくわからなかったが再帰関数で探索してよさそうだったので書いたら通った。枝刈りをしていることになって、それが効いているようだ。適当にRubyで縮めて184B。

布団に戻ってなろうを読んでいたが、正午くらいに就寝。午後6時起床。

サークル解説会の準備をする。今日はABC208で、C問題とF問題の解説をすることにした。と言っても、F問題の解説と書いておきながら実際は多項式補間のやり方しか書いていない。しかも書きあがってみるとほとんどWikipediaの記述そのままになってしまい、悲しい。

2021/07/09 定例会 | puzzleknot 公式サイト

yukicoderのコンテストに出る。8完。

競プロ典型 90 問 期末試験 - yukicoder

AからWAを出した。正規表現で/../としたが、これは2文字以上であることしか判別できない。正しくは/^..$/。Bはよい。Cもよいはずだったが、平方根を求めるのに洒落っ気を出して二分探索したらオーバーフローしてしまい2WA。WAの原因に気づいたのがコンテスト最終盤だったのもつらいところ。Dは全探索。Eは10x10x10のテーブルを項番号で埋めていって、同じマスを参照したら差でKを割った余りを取る。Fは無料になる移動それぞれについて、それを使う場合の数を求めて全体から引けばよい。GはそのままとPを足した値の2つに対して二分探索でカウント。ARC092-D Two Sequencesで見た。

Hは非常に面白かった。典型90問で以前出題された、マスを左上から1つずつ埋めていく解法かと思ったが、できない。正解は、未決定の場所と決定済みの場所に分けて、スコアへの寄与を毎回足していくというもの。ABC025-D 25個の整数で見たことのある考察だったから、何とか思いつくことができた。

残り時間でIを考えていた。交差点の間で連続して2回以上受け渡しが行われる場合どうしていいかわからず、そのようなケースはないのでは？と思って実装してみたらサンプルが合わなくて終了。

深夜、昨日から引き続き考えていた問題に取り組んで、4時間くらいかけて通した。

Submission #24087155 - CODE FESTIVAL 2017 Final

前に見たアダマール行列だ！と思ってチャレンジしたが、とんでもない目に遭った。

手で実験すると(N,K)=(3,2),(7,3)が見つかる。N固定、K全探索で深さ優先探索をするコードを書いて回してみたところ、さらに(N,K)=(13,4)が見つかった。どうやら[tex:N=K2-K+1]らしい。実際、13より大きなNに対してはまともにプログラムが終了しなかったため試すのを諦めていたが、(N,K)=(21,5)のケースも深さ優先探索で見つけることができた。これ以上はさすがに無理なようだ。

以下、紙にある数字が書かれているか否かをビットで持つN\times N行列を解と同一視する。K=5の解の一例を下に示した。深さ優先探索で解を見つけているので、行列はそこそこ特徴的な形をしている。ここから攻めていこう。

000000000000000011111
000000000000111100001
000000001111000000001
000011110000000000001
111100000000000000001
000100010001000100010
001000100010001000010
010001000100010000010
100010001000100000010
100001000010000100100
010010000001001000100
001000011000010000100
000100100100100000100
001010000100000101000
000101001000001001000
100000100001010001000
010000010010100001000
010000101000000110000
100000010100001010000
000110000010010010000
001001000001100010000

まず、上端のK行と右端のK行はこの形で固定してよい。ビットをソートしたと考えれば納得できる。K'=K-1と置くと、残り注目したいのはK'^2\times K'^2の領域になるが、よく見るとK'\times K'のマスにK'個のビットが立っているような小行列を組み合わせた形となっている。小行列自体も4種類しかないようだ。

小さいケースで構築したものを用い、K'を1増やしたり倍にしたりすることでより大きなケースを構築するのがよいと考えたが、どうにもならず。ただ、K'を倍にすることを続ければ、K'=32のとき元のK=33となり、N=1057でピッタリ（？）解として提出可能なサイズになる。これが筋がよさそう。

ここまでが昨日考えたことだった。あとは小行列をいろいろ取り出して眺めていたが、進展はなし。

今日になって、小行列4種類というのが次のように分類できることに気づいた。

小／小＼
大／0001
0010
0100
1000		0010
0001
1000
0100
大＼0100
1000
0001
0010		1000
0100
0010
0001

これに0から3の番号をつける。番号はどれでもいいはずだ。番号で上で示した行列を解釈すると、次のようになる。

0000
3210
1320
2130

一番上の行以外は順列になっていて、さらに2つの行を取ってきてxorを取ると、それもまた順列となる。ちょっと考えると、これが成り立っていればよいようだ。順列とならなかった場合はxorが等しい列のペアが出現するが、そこで「2つの列で同じ位置に立っているbitがちょうど1つ」が満たされなくなる。

これはK'が大きくなっても扱いやすい。K'としては2べきのみを考えればよいから、K'=2^kとしておく。まず番号から小行列への変換については、小行列2^k種類は上の表をk次元にした感じで再帰的に見ていくことでできる。あとは番号だけ考えていればよい。問題は「0\dots 2^k-1の順列2^k-1個の組であって、どの2つの順列も要素ごとにxorをとるとまた順列になるような組」を構築することに換言された。

が、これもまあしんどかった。bitごとに見ればアダマール行列っぽくなるが、それをどのように重ねるかがわからない。順列をひたすらシャッフルして頑張るプログラムで2^3、2^4の解は見つかったが、2^5は無理そう。そこで2^3の解をひたすら睨む。

00000000
01234567
05142736
04376251
06715324
07521643
03657412
02463175

アダマール行列（の-1を0に置き換えたもの）の各行を次のように番号付けよう。

0：00000000
1：01010101
2：00110011
3：01100110
4：00001111
5：01011010
6：00111100
7：01101001

これを用いて見つかった解を表すと、1bit目が上の行から順に01326754、2bit目が02463175、3bit目が04157362であったようだ。1bit目が昇順に並ぶようにソートすると01234567、02645731、04512673。これもまた3bitと見て桁ごとに分解すると、それぞれ124、436、243。2bit目と3bit目を入れ替えると124、243、436。ここにきてようやくパターンが見えてきた。つまり、{1,2,4}から隣接する項のxorを取って{1,2,4,1^2,2^4}、この隣接する3要素を抜き出す感じ。

これを実装して試してみると、K'=2^4とK'=2^6ではうまくいったが、K'=2^5ではダメだった。かなり絶望しかけたが、ふと隣接する項のxorではなく1つ飛ばしに取ってみたところ、構築に成功した。

喜びのツイートをしたらmaspyさんに射影平面の直線を利用した構築があることを教えてもらった。スゲー。

Distribute Numbers（CODE FESTIVAL 2017 [F]） | maspyのHP

これは性質が適切すぎるが、より一般に、対称性があるものを構築するときは数学の言葉で説明するのが簡潔になりがちだと感じる。また上で用いたアダマール行列というのを筆頭に数学の経験から得られる構築の手順もある。こういったものに慣れていないならば、数をこなすことで身に着けていくしかない。アダマール行列はちょうど半年くらい前にコンテストで出たので、知っていた。

現在のD問題の最短コードはアダマール行列を利用した解法になっている。

週記（2021/01/11-2021/01/17） - kotatsugameの日記

日記を書いていたら朝になった。土曜日の典型90問を解く。セグ木のノードにvectorを持ってもいいのでは！？と思って書いたが、手元で適当に生成した最大ケースでは当然のようにTLE。ACLのセグ木は参照渡しできないからダメだ、と思って書き直していたが、これも全然通らなかった。多分セグ木上の二分探索が重すぎるのだろう。

全然ダメだったので改めて考え直すと、尺取り法で解けることが分かった。転倒数は数列の先頭・末尾を弄っている限りは簡単に差分更新できる、というのはABC190Fで見た覚えがある。

午前10時半就寝。

07/10(土)

午後4時過ぎに弁当を受け取るため起床。その後布団に戻って二度寝しようと思ったが、うっかりYouTubeアプリで動画を見始めてしまい、眠れなくなった。午後6時くらいに諦めて布団から出た。

昼過ぎにyukicoderでコンテストがあったようだ。2問構成で、1問目は普通の拡張ダイクストラ、2問目は星5で論文などが参考資料として掲出されている。1問目だけ通しておいた。

No.1601 With Animals into Institute - yukicoder

ABCが始まるまでの時間で橙diffを1問通した。

Submission #24099997 - NOMURA Programming Contest 2021(AtCoder Regular Contest 121)

つい最近の問題。その日の日記を見たところ、解説で1行目だけ読んだということが書かれていた。なんとなく記憶が蘇ってくる。解説では「頂点iにはiの子孫であるような頂点の番号を書き込むことはできない」と書かれているが、問題文をただ解釈しただけでは子孫ではなく親となるべきはずで、意味が通らない。これについてTLに質問を投げると、逆順列についての言及が返ってきたのだった。つまり、問題文では「頂点a_iから頂点iに到達できない」となっているが、このiにa^{-1}_iを当てはめて「頂点iからa^{-1}_iに到達できない」と読み替えるということ。

逆順列を考えると自分の子についての条件になって扱いやすくなるらしい。

週記（2021/05/24-2021/05/30） - kotatsugameの日記

今日の挑戦で最初に選んだ方針は、コンテスト中と同じで「自分の子でまだ値が決まっていない頂点数」をdpのキーに持つものだった。愚直に書いてもサンプルが合わずに絶望していたもの。この方針だとあまり逆順列を意識しなくても書けるな、と思いながらとりあえず愚直な遷移を書いたら、今日はサンプルが合った。これは来た！と思ったが、そこから高速化できなかった。係数をうまく分離して畳み込みなりするのだと思っていたが、この分離が全然できない。lとrからの遷移先は0\le x\le l、0\le y\le rのそれぞれに対して存在し、係数には4つの変数が入り混じって存在する。

結局方針を転換し、包除原理で解いた。当時のTLで見聞きしたことを覚えていたのかもしれない。この方針だと逆順列を意識するのがかなり効く。

もうすでに眠くなってきているが、ABC209に出た。全完24位。

AtCoder Beginner Contest 209 - AtCoder

Aはよい。式の値が負になる場合のケアもすぐ気づけた。Bは割引額が\left\lfloor \frac N 2\right\rfloorだとわかる、と思って書いたがWA。入力を1行目しか受け取っていなかった。アホ。

Cは難しい。しばらく考えると、A_1\le A_2の場合の先頭2要素について場合の数がA_1(A_2-1)となるとわかる。これを一般化して、Aを昇順ソートして引きつつ掛けていけば求まる。Dは最近作ったLCAライブラリを使いたくなって、あまり考察せずに貼り付けて通した。

Eはかなり難しい。文字列を有向辺と思うと523頂点のグラフになる。出次数が0の頂点は当然負けで、そこからトポロジカルソートの要領で決めていけ、ループ上の頂点は引き分けになるのだろうと思ったが、WA。ほとんどのケースで答えが間違っているらしい。しょうがないのでループを検出するメモ化再帰を書いたが、これもWA。実はトポロジカルソートから微妙に変える必要があって、ある頂点から出る辺の先にある頂点が全部決定する前であっても、負けの頂点に遷移できると分かった時点で勝ちだと決定させてしまう必要があった。これはメモ化再帰でも実現できていたのだが、そちらはループ検出のために途中に置いたフラグを毎回クリアしなければ正しく検出できず、逆にそれをすると計算量が増えてしまう。

Fは簡単。隣り合う項との順番にしか興味がないので挿入dpができる。遷移は一見O(N^2)に見えるが、ある値以上・以下の要素を全部足しているだけなので上から・下から累積和を取ればよい。

コードゴルフをする。A問題は開始16秒で提出した8Bだろうと思っていたが、7Bがあった。?r-1+ではなく1?--のほうが短い。これは何度も見たことがあるはずだった。以下のツイートはABC180の時のもの。

Bはdc。\left\lfloor \frac N 2\right\rfloorではなく\frac N 2でも通るようだった。他に、N=1の場合の対応をしなくても通ったことを利用して微妙に縮めている。CはPerl。

Dは、LCAなど持ち出さずとも深さの偶奇が異なることさえチェックすればよかったらしい。頂点間の距離の偶奇にしか興味がないので、LCAを求めても関係する項は\bmod 2で消えるというわけ。とりあえずRubyで通したがPerlで書いたほうが格段に短い。Perlでグラフの入力受け取り・dfsを行うコードは、典型90問のコードゴルフでいくらか新手が出て整備された結果、シンプルになりすぎて取っつきようがない。

Eは適当にRubyで書いておいた。ゴルフしていない。Fは2方向から累積和を取る関係でOctaveが強いはず。

今日のdifficultyもなかなか崖が大きかった。Cまで灰色、Dが茶色、EFが黄色。Cは難しいと思ったが、AtCoderで数え上げが出すぎた結果この程度なら普通に解けるように訓練されているらしい。

CF #731 div.3に出た。pretest全完10位。

Dashboard - Codeforces Round #731 (Div. 3) - Codeforces

Aは面倒。x座標とy座標のどちらかが全ての点で等しく、かつ障害物が2点の間にある場合だけ関係する。Bは'a'を探して、左右から貪欲に取る。Cも貪欲。Dは、どこかのbitを打ち消すくらいならそれ以降常にそのbitを立てるほうが辞書順で小さくなるので、xorではなくorだと考えてよい。Eは線形時間でやってほしそうな雰囲気を出していたが、思いついた方針がだいたい0-N BFSと同じだったので、面倒になってdijkstraした。Fは素因数ごとに見るのを考えたが、素因数が多すぎて間に合わなさそう。列を倍にしたセグメント木上で二分探索した。GはSCCして、内部に辺を含むような強連結成分を通ったら-1になる。

終わってみると順位表の1ページ目に日本人が10人いてかなり面白かった。Eは左右から累積minすると線形時間になるようだ。頭がよい。

典型90問089がRubyで通されていたので、自分もやってみる。そこそこ普通に通るようだった。しばらく格闘して現在報告されていた最短を更新したが、実は報告し忘れでもっと短いコードになっていたらしい。悲しい。嘘です、報告してくれるだけで嬉しいです。

眠気に耐えかね布団に移動。ちょっとだけなろうを読んで午前3時半に就寝。

07/11(日)

午前8時くらいに目を覚ます。典型90問の投稿までもうちょっと寝ようと思ったが、結局なろうを読んでいた。

今日の典型90問を解く。今日は10点満点。最初、頭が働いていないのか全く何も思い浮かばず絶望していたが、小課題をどんどん進めていく方針で無理やりにでも考察を生み出す。といってもK=1の場合は隣接2項がどちらも1にならなければよくて、N=K=6は何やっても解けて、それ以降は途端に難しくなる。

とりあえず、数列の値としてはKを割ったあまりでまとめて考えることで\sqrt K種類しか考慮しなくてよいことに気づいた（実はこれはなくても解ける）。次いで、l=\left\lfloor \frac K a\right\rfloorとなるようなaたちの置き方について考えるときは、l-1の場合をいくつか並べて間にaとしてありうるどれかを置く、というdpで求まることに気づく。これは、l-1の場合とa1つを組にして一度に遷移し、最後に1つずつずらすことで求まる。l=Kの場合まで求まったら、あとは同様のdpを長さNで行うことで答えがわかる。これをナイーブに実装したら大きめのサンプルが合った。

このdpは遷移がインデックスによらないということで、多項式で表現できそうな見た目をしている。遷移をfと置くと、(1+f)^\inftyを適切な範囲で求めればよいのかと思ったが、これは遷移を選ぶ順番も考慮してしまい合わない。正解は1+f+f^2+\dots=\frac 1{1-f}で、多項式の除算はライブラリを持っていないのでどこかから窃盗してくることが確定した。とりあえず拾ってきたライブラリを貼ると、ちゃんとサンプルは合ったまま、計算量だけが落ちている。

最後のdpだけはx^Nの項を求める必要がある。高速きたまさ法が使えるので、それまで実装されているライブラリを新たに探してくることにした。それを参考に今貼り付けてあるライブラリから新たに実装しようと思ったが、やはり中身を理解していないアルゴリズムをその場で書くのは難しく、結局見つけたライブラリに置き換えてしまうことにした。verifyコードを見つつ書き換えてサンプルを試すと答えが一致し、最大ケースでも十分高速に求まる。提出するとAC、261msだった。Nyaanさんのライブラリを使用したのだが、いろいろ闇の魔術を使っていて、熱意に唸らされる。

線形漸化式の高速計算 | Nyaan’s Library

解法50分ライブラリ窃盗50分みたいな感じで、都合100分弱でAC。かなり手ごたえがあった。コード長は40000Bを超えている。

提出する直前に宅配が来た。

布団に戻って4時間ほどなろうを読み、午後3時に就寝。午後6時半ごろに起床。

昨日のCF div.3のシステスが終了し、ちゃんと全部通っていた。

午後7時に典型90問のコンテストが終了。統計情報を聞くと、全体の提出のうち1%が僕によるものだったらしい。

直ちに提出がすべて公開されると思っていたのだが、まだ凍結が解除されない。どうやらYouTubeで行われる閉会式の後、午後10時くらいまで待つ必要があったらしい。その間に日記を書いていた。

www.youtube.com

3位だった。これまで89問すべて解いた人の中で最終問題を解いたのが3番目だったということで、最終問題だけで見れば5番手以降となる。

午後10時半くらいにすべての提出が公開されたので、001から順に最短コードだったり自分のコードとのdiffを確認していった。複数人のコードがほとんど一致しているものがいくつかあり、例えば001なんかは変数名と改行位置の違いを除いて4人が同じコードを提出していて面白い。以下のリプライツリーに、特筆すべきであると感じたコードについての言及を連ねておいた。

といっても、典型002は正規表現の改善で-1Bされてしまったのだが……。公式ドキュメントの\gの使用例が「正しい括弧列にマッチする正規表現」そのもので、等価な書き換えをするだけで縮む。

それ以外にもいくつか覚えておきたいコードがあったので、ここに書き残しておく。

典型013：Submission #22965470 - 競プロ典型 90 問

eval(dir()[N])（ただしNは適切な定数）で長い関数名を省略するテクは使っていたが、dir(G)とすることでGに関連付けられた関数名が得られることは知らなかった。公式ドキュメントを見ると「有効な属性のリスト」とある。

組み込み関数 — Python 3.9.4 ドキュメント

典型016：Submission #24168759 - 競プロ典型 90 問

min_ofというメソッドがあるらしい。min_byはargminを返すが、このメソッドはminの値そのものを変えす。RubyにはないCrystal独自のメソッドで、こんな便利なものがあったのかと魂消た。

Enumerable(T) - github.com/crystal-lang/crystal

典型055：Submission #24171449 - 競プロ典型 90 問

each_combinationsには第二引数があって、そこに真と解釈される値を入れると速くなるらしい。

each_combinationsを使用してイテレータを用いるとよいのではないか、とも考えたが、こちらも結局TLEしてしまった。

週記（2021/05/31-2021/06/06） - kotatsugameの日記

実装を読んだ。第二引数はreuseという変数である。これが真である場合、reuseには新しく取り出す個数分の長さの配列が確保されて代入される。

crystal/array.cr at 4401e90f001c975838b6708cc70868f18824d1e5 · crystal-lang/crystal · GitHub

イテレート中にpool_sliceという内部メソッドが呼び出される。ここでreuseが使われ、reuseに配列が代入されているならそこに値を詰め込むが、そうでないなら毎回配列を確保する、という実装らしい。この再確保のオーバーヘッドがなくなることで、TLEが解消されるということのようだ。

crystal/array.cr at 4401e90f001c975838b6708cc70868f18824d1e5 · crystal-lang/crystal · GitHub

典型089：Submission #24169798 - 競プロ典型 90 問

昨日格闘していた問題。どうやって縮めたのか気になっていた。配列ではなくHashを使うことで、座圧をせずにBITを実現している。必要なところだけ作るセグ木、あるいはBinaryTrie木と理解できる。これで間に合うというのも驚きだ。

典型90問の問題がAtCoder Problemsに追加されて、最短コードが1600を超えた。

そのほか、Longest Streakが48日になったりしていて面白い。日曜日以外は典型90問で新規ACがあって、日曜日はコンテストがある、ということがかなり長く続いていたようだ。

朝方、数理統計学の講義資料を3回分読んで、1つだけ設定されていた課題を提出した。残り2回分あるが、こちらは課題がないようだ。実質後は期末レポートのみ。