08/29(月)

午後3時起床。11時間くらい寝たらしいが体感としてまだ疲れは残っている。TLを眺めていたら二度寝するタイミングを逃し、ノソノソ起き上がって午後4時半からインターン先定例会。

先週の進捗はまあまあ。金曜日の1on1で話したことがすべてで、日記でも至る所が崩壊したと書いたように完成に近づいているわけではないが、いくつか方法を試してダメだということが分かったのは結構重要だと思っている。なぜダメだったのかの考察も少し加えつつ、1on1で提案された別のアプローチを試すのを今週やりますと言っておいた。

勉強会は線形空間とか線形写像についての話。序盤は知っていることだらけなのでよい、と気を抜いていたら、終盤難易度が急激に上昇し、知らないものがよくわからないまま終わってしまった。極限から位相を定められるということを知ったのが収穫といえば収穫だろうか。

定例会を終え、今日も先週の週記を書く。オンサイト参加記の下書きとして土日の行動記録をつけていたので、それの日曜日の分を完成させた後、週記のほうに手を付けた。こちらは金曜日の分から残っていた。土日の日記はつけておいた行動記録の内容を参加記とで振り分けるつもりなので、同時並行で書き進める必要がある。

とりあえず土曜日のコンテスト、ABCとECRの部分を書いた段階で日付が変わりそうになったので、投稿した。これまで未完成の状態で投稿したことは何度もあるが、今回は特にボロボロ。日曜日の部分を全く書けていない。

どういう形であれ何とか月曜日中に投稿できたので、気が抜けてしばらくYouTubeを見ていた。

午前2時にMHC2022 qualが終わった。全完14位。順位にあまり意味がない形式のコンテストだが、それでも順位表の最上位層に位置できたのは素直にうれしい。

Meta Hacker Cup - 2022 - Qualification Round

Aは難読気味に感じられた。読めればやるだけ。B1は全部木で埋める、B2は木を置いてはいけないマスをBFSのように列挙して、そうでないマスを木で埋めればよい。Cは先頭文字を与えられた文字列と異なるものにして、以降の幅を固定しインデックスの2進数表現を埋め込んだ。C2の制約も満たせる解法。むしろC1だけ満たす構築は不自然ではないだろうか。

Dは少し面白い。クエリ $(X,Y)$ に対しては、 $X\rightarrow u\rightarrow Y$ と飛べるフライトのペアを列挙し $C$ の小さいほうを答えに足せばだいたいOK。 $X\rightarrow Y$ というフライトは朝夕2回使えるが、これは別に処理してもよいし、任意の頂点 $u$ について定員 $10^9$ 人の $u\rightarrow u$ というフライトを足せば、最初に計算したフライトのペアと同様に扱える。後者の方法で実装した。

フライトを重み付きグラフとして、クエリ $(X,Y)$ について $X$ の次数が $Y$ の次数以上であるようにswapしておく。 $X$ が同じクエリを集め、まず $X\rightarrow u$ という辺すべてを見て、 $u$ に乗客数を保存する。次に、 $X$ とペアになった $Y$ に対し $u\rightarrow Y$ という辺をすべて見て答えを求める。このとき $(X,Y)$ が全く同じクエリが以前にあったならその答えを使う。

計算量を解析する。まず $X$ に接続する辺を見るのが全体で $M$ 回。 $Y$ については次数が自分以上であるような点が何個あるかが問題になって、最悪ケースはクエリに出現する全頂点の次数が等しくなる場合のはず。その次数を $c$ とすると、 $X$ または $Y$ として出現するのが $M/c$ 頂点なので、ペア $(X,Y)$ は $(M/c)^2$ 種類。またこの値はクエリ $Q$ 個でも押さえられるため、都合 $c\times\min((M/c)^2,Q)$ 回くらい見ることになる。この値は $M^2/c=Qc$ つまり $c=M/\sqrt Q$ のとき最大値 $M\sqrt Q$ を取る。よって間に合う、だろう。

手元で確か50sec弱かかったはず。うっかりただのリダイレクトで実行してしまったため出力が見えず、いつ終わるのか気が気ではなかった。実行時間が長いと予想される場合、ちゃんとteeコマンドを使って途中経過を眺めるようにしたい。

Dの計算量についてより正確な証明をへのkのツイートで知った。

証明
簡単のためaを単調増加としておく。
(a_i,a_j)が大きい順にQ個あるときにmin(a_i,a_j)の総和が最大になる。
このとき出てくるi,jはO(sqrt(Q))種類しかないので、総和はO(Σ(a_i*sqrt(Q)))で抑えられて、これはO(Msqrt(Q))
— heno (@heno_code) 2022年8月29日

先週の週記について、金曜日の分まで校閲を済ませた。問題の解説として書いていた文章が盛大に間違っていてびっくりした。Codechef 8月LunchtimeのMEXPERMDIFについてで、順列の転倒数と $K$ が一致すると書いていたが全くそんなことはない。特殊な形をした順列、つまり「転倒数が $K$ になるような順列を構築せよ」と言われて先頭の項から調整した、辞書順最大っぽい順列だった場合はこれが成り立ちそう。正確に書くとまた長くなるので言葉を濁しておいた。

PN=0PN=0 のときPPの転倒数を減らしていくような感じでB=KB=Kを11ずつデクリメントしていける
週記（2022/08/22-2022/08/28） - kotatsugameの日記

ハーメルンの更新を読んだ。1か月に1回ペースでしか更新されないのにしばらく主人公が暗躍するばかりで登場しなかったので、最新話で久しぶりに出番があって非常に嬉しかった。焦らしただけある格好いい登場シーン。

syosetu.org

布団に入ってハーメルンを1作読み始めた。午前8時半就寝。

08/30(火)

午後6時過ぎ起床。

今朝読み始めたハーメルンを放棄した。「役満で上がると惚れられる」。咲のR18二次創作。主人公は、少なくとも序盤においては特に麻雀で強いというわけでもなさそうだったので、読む気力が続かなかった。

ハーメルン - SS･小説投稿サイト-

起きて参加記の続きを書こうとしたが、どうにも内容が思いつかない。そもそも参加記という形式のブログを書くことが久しぶりすぎて、詳細に残しておいた行動記録のどれを参加記に、どれを日記に書くべきか決めきれない。集中が切れてかなり長い時間をYouTubeに費やしてしまった。

午後11時50分からCF #817 div.4。15分こどふぉってこの時間になった。

Dashboard - Codeforces Round #817 (Div. 4) - Codeforces

Aはソートして判定。BはGをBに変えて一致判定。Cはmapで文字列の出現回数を数えた。それぞれの人は同じ文字列を書かないので実装はかなり簡単。 $O(nt)$ 回のmapアクセスも、文字列長が $3$ なので速度的に問題ない。Dは変更することによる増分を列挙して大きな方から使う。

Eはちょっと時間がかかった。二次元累積和を使うと計算ステップ数が $10^8$ くらいになるが、TLが6secということもあって十分間に合いそうではある。ただこのことを信じ切れず、BITを使って $O( (n+q)(\log(n+q)+\log\max w))$ で解いた。まず、二次元累積和と同様にしてクエリを四つに分解する。それぞれの形式は、 $(h,w)$ に対して、 $h_i\lt h\land w_i\lt w$ なる $i$ について $\sum_i h_i\cdot w_i$ を求めるものである。あとは $(h_i,w_i)$ とまとめて $h$ の昇順にソートし、 $w$ をBITのインデックスにして管理すればよい。

Fは面倒なだけ。Gは全要素のXORが $0$ であればよくて、 $n\bmod 4$ の値で場合分けした。ちゃんと $4k+0,\dots,4k+3$ の四つ組を作らないとXORを $0$ にできないのに、連続する四つの数であればよいと早とちりしたまま提出。サンプル1で落ちたためペナルティがつかなかったのは幸い。

36分全完で17位。EFGでそれぞれ時間をかけてしまったのが痛い。Eを改めて二次元累積和で書いてみたところ500msもかからず通ってしまった。そうか……。

TCO Finalsのフライトがまた提案されていた。羽田空港発着となるようお願いしていて、とりあえず行きは問題なく見つかったらしい。ただ帰りの飛行機が希望する時間帯に見当たらず、どうしても羽田空港に帰って来たいならボストン出発が朝になり、そうでないなら正午出発で成田空港着となるとのこと。

成田着のフライトの日程が添付されていたので見てみると、ボストンを土曜正午に発ってそのまま成田までの直行便、到着が日曜午後4時過ぎだった。両方現地時間である。実はこれは非常にありがたい。ボストンは日本より13時間遅れているため、出発が日本時間で日曜午前1時になる。すると、土日どちらも日本時間午後9時から数時間は陸地にいることになって、AtCoderのコンテストに問題なく参加できるのだ。これほどピッタリな便はそうそうないだろう。成田空港着でも構わないからこれを予約してくれ、と伝えた。

そういえば9月からSlackの過去ログを見られる範囲が変わるらしいので、今のうちにサークルで使っているワークスペースのデータをエクスポートしてみた。publicなチャンネルだけなので、例えばICPCチームで使ってきたprivateチャンネルの内容はこのままデータの藻屑と消えてしまう。残念。12000件ほどあるのに一瞬で完了してびっくりした。Windows機でデータを解凍するとフォルダ名が文字化けしてしまったので、Ubuntu機で解凍して、サークルで使っているGoogleドライブに投げておいた。

改めて参加記を書いていたが相変わらず筆が乗らない。そのうちラノベに逃げて、1冊読了した。「異世界でチート能力を手にした俺は、現実世界をも無双する」11巻。

やはり現代パートが好みで、文化祭だったり生配信に映り込んでバズったりとニヤニヤできる展開が盛りだくさんだった。これが前半の内容。後半は異世界パートで、前の巻の内容をあまり覚えていなかったからよくわからなかったがとにかく無双している。主人公の過去にまつわる設定が少し明らかにされた。これまで伏線が張られてきたわけではないように記憶しているので、どちらかというと「設定が追加された」と言うほうが近かったりするのだろうか。後書きから推測するにこの巻もまた行き当たりばったりで書いているらしい。それで物語的に破綻しないのは凄まじい。

インターン先が巨額の資金調達を実施したとのことで、Slackで通知が回ってきた。すごい話だ。僕がインターンを開始してからちょうど1年経ち、その間だけ見ていてもこの会社は加速度的に成長しているように思う。それは業績云々という難しい観点ではなくもっと単純なところで、毎月社員がどんどん増えているのだ。正直適当に決めたインターン先だったが、今は愛着みたいなものもある。

26億の資金調達を実施しました！
これもひとえに、お客様、THIRDの仲間たち、投資家の皆様のおかげだと思っています。
これから会社をもう1段階を大きくするための成長フェーズを作っていくことになります！仲間を絶賛募集中です！興味ある方DMください！https://t.co/m5GbxBmmud
— 井上惇 | 管理ロイド | THIRD代表 (@inoue_third) 2022年8月31日

午前11時就寝。

08/31(水)

午後7時起床。寝足りない気持ちを抱えながら布団から這い出た。今日は午後8時という変な時間からSRM836がある。レジって参加した。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19394

Easyはカス。ふんふん言いながら書いてサンプルを試したところで $A=0$ のケースに気づきキレそうになった。あまりにも嫌らしすぎる。そのうえ領域一杯にしか長方形がない場合など不必要なコーナーケースが盛りだくさん。

Medもカス。見るからに嫌な形式をしている。こういう問題をサンプルだけで解かせるのはもう本当に時代遅れだから一刻も早く考え直してほしい。SRMらしさなど求めていない。頼むからまともなコンテストを運営することだけに専念してくれ。

どの文字をどのように変えるか先に決め打っておき、貪欲に操作した。変えるべき位置が1か所しかない場合はそのままだと操作列が作れないので、追加で一か所無駄な変更をする必要がある。変えなくてよい位置のみを見て、a以外の文字があったらそのうち最初の出現をaに変えて戻すのがよい。なければ最後のaをbに変えて戻す。

貪欲に操作するとき、残りの操作回数がちょうど2になる瞬間だけ気を付ける必要がある。同じ位置の操作が2回残っていると操作列が作れなくなってしまうので、二か所で1回ずつ残すようにする。それ以外は特に気にしなくてよい。なぜなら同じ位置で操作する回数は高々2回だから。

コンテスト後に文字列間の距離を返す関数を作っておく方法を聞き、感動した。自分の解法もシンプルに書けるようにしばらく考えて編み出したものだが、こちらのほうがかなり簡単になりそう。

Hardはまともか。まず $R\times C$ の盤面に辺同士が接しないようにキューブを置く。市松模様を考えると $N\le\lceil RC/2\rceil$ の場合はこれだけで達成できて、最適。そうでない場合、置いた $\lceil RC/2\rceil$ 個のキューブの上に余ったキューブを積み重ねるべきで、これはただの重複組み合わせ。

盤面に直接置く部分はbitDPで計算した。本当は1個ずつ置くことで計算量が削減できるらしいが、1行ずつ状態を決めても間に合った。そもそもキューブが隣り合わないような置き方が $C=14$ で $1000$ 通りもなく、その2乗に $R$ とばらまいた個数 $\lceil RC/2\rceil$ をかけて、計算ステップ数は $1.4\times 10^9$ くらいになる。テストすると1sec強だった。

15分ほど余らせて全問提出した。チャレンジフェーズではEasyを見ていて、成功1失敗1。 $A=0$ のケースで共通部分を持たないように長方形を置くところが間違っているコードを落としたはず。もう一つ、自分が読んだ限り同様のケースで落ちると思ったコードがあったのに、なぜか落ちなくて失敗。コードを書き写すか迷っているうちに別の人に落とされた。

そのうち自分のEasyも落とされた。 $A=0$ のケースに気づいて場合分けを付け加えたのだが、その前に与えられた長方形が共通部分を持たない場合空のvectorを返すif文を書いていたのがダメ。先に $A=0$ の場合分けを書いておく必要があった。改めてRoomの提出を見ると、EasyとMedがどちらもボロボロで、そんな中たった+25ptしかできていないのは残念。

システスでHardも落ちた。1完19位で2977→2887(-90)。ゴミコンテスト。出る価値なし。Hardのミスは盤面に直接置く部分で、 $R\times C$ の盤面に $\lceil RC/2\rceil$ 個敷き詰める方法は市松模様とそれを反転した高々2通りしかないと思っていたら、例えば $(R,C)=(1,4)$ などで落ちてしまった。これは間に2マス開ける方法を含めて3通りある。ちゃんとbitDPで求めた値を参照するべきだったらしい。

絶望してしばらくぼんやりとYouTubeを眺めていた。日付が変わってから明日のセミナー発表の準備を始めた。いつものように教科書を読んで内容を紙にメモ。以前準備した分が微妙に残っていたので量的にはそれほどでもないはずなのに、集中が切れまくってスマホを触ったりTLを見たり、なかなか進みはよくなかった。あとは内容も難しい。証明が回っていることはわかるが、なぜこのような方法を思いついたのか全くわからず苦労した。少しでも「お気持ち」が汲み取れていることを願う。

ひとまずの完成を見て午前8時くらいに布団に入る。ハーメルンの更新を少し読むのと、あとはチュウニズムのアップデートで15が2譜面追加されたので、その確認動画を見ていた。

どちらの譜面も一部が以下のように事前に公開されていた。この紫色のノーツの下には別のノーツが隠れていて、視認性が悪すぎるだろと思っていたのだが、その前に紫色のノーツなしで同様の配置があり、ちゃんと誘導になっていたので感心した。

pic.twitter.com/OP8avLMHRQ
— （凍結中）【穴山大輔 VS 光吉猛修】【水野健治 VS 大国奏音】@SEGA (@anayama_daisuke) 2022年8月30日

午前9時就寝。

09/01(木)

正午起床。起きるに起きられず布団に突っ伏してTLを見ていたら、atgolferの更新が流れてきた。AWKで新手が出たらしい。一気に覚醒し跳ね起きて、適用できるコードを探し、10個以上縮めた。

atcoder.jp

RS=FSとして空白区切りでレコードを読み込むテクニックがある。この状態で入力の終端を検出しようとするとき、ENDブロックを使ったりNRを見たりするよりも短い方法があって、それが/\n/だった。今、空白をレコードの区切りとしているため、逆に普段のレコード区切りである改行文字が$0に残ったままになっており、それをチェックすることで行の末尾であることを検出できる。

ここで特殊変数RTを使うと短くなるようだ。そもそもそのような変数があることすら知らなかった。RTには今見ているレコードを実際に区切った文字列が入っている。後ろに入力が続いている場合、この文字列は空白、つまり真となる。一方今見ているレコードが入力の最後だった場合、そもそもレコードは区切られておらず、RTは空文字列つまり偽となる。これで判定できる。/\n/と比べて-1B。

副次的な効果でさらに縮んでいる。/\n/で判定する場合、$0を書き換えると壊れてしまうため、/\n/が真であることを確認してから$0に代入する必要があった。今RTを使う場合そのあたりのことは気にしないでいいので、とりあえず答えとなりうる値を$0に放り込んでおいてRTが偽のときのみ出力する、という方法が取れて、追加で大体-2Bくらいされる。

そんなことをしていたら午後1時になってしまった。なんと今日のセミナーは午後1時開始の予定である。先生に遅れるとのメールを送ってから急いで家を出た。途中購買で食べるものをサッと買い、何とか15分くらいで山の上の教室にたどり着いた。

今日のセミナーは、まず博士課程の人の報告を聞いてから、自分の発表。報告のほうは相変わらず知らないことだらけでよくわからない。自分の発表については、自分では別に難しい内容を喋っているつもりもないし至って普段通りに進められたと思ったのに、あまり伝わらなかったし、先生から「内容がまとまっていないように感じる」と言われてしまった。何が悪かったのかあまりよくわからないため改善が難しい。一か所、言い忘れていたことを後から口頭で補足した場面があって、それはピンポイントで不親切だと指摘されたので、とりあえずここを直すべきか。

午後4時過ぎに解散。帰宅して、まず8月の読書記録をツイートした。先月も全然ダメ。リアル読書に限らず全体的にやりたいことができていないように感じられて、理由も明確。YouTubeに時間を吸い取られすぎている。かなりどうしようもない。Vtuberの波は自分の中でもう過ぎ去った感じがして、今はQuizKnock、チュウニズム譜面保管所、デュエプレ実況のさとらさん、GOD EATERのプレイ動画を見ている。

8月の集計
買った：20冊
読んだ：5冊
積読：+15冊
積読（累積）：+91冊
— こたつがめ (@kotatsugame_t) 2022年9月1日

疲れ果ててTLを眺めていたら先生からメールが来ているのに気付いた。今日の発表内容について、関連するものが教科書の後ろのほうにあるのでちょっと読んでみてください、という感じ。該当部分を探してみると、もう知らないことだらけで全然読めずびっくりした。文章とにらめっこしているうちにPCの前で意識を飛ばしてしまったので、メールの返信もせず即座に布団にダイブして就寝。午後7時半だった。

午前1時起床。性懲りもなくYouTubeを開いたら「科学の力使いまくって隠居生活」が投稿されていたので視聴した。

www.youtube.com

布団から出て、オンサイトの参加記を必死に書いていた。朝方にとりあえず土曜日の分が書けた。まだ校閲はしていない。日記のほうはその状態で更新しておき、参加記はまた日曜日の部分が完成してから公開するつもりである。

1時間ちょっとインターン関連のコードを書き進めた後布団に入り、少しハーメルンを読んで就寝。正午を少し回ったくらいだった。

09/02(金)

午後2時半に目覚ましで起床。執念で布団から這い出た。フラフラする頭をたたき起こして午後3時から1on1。

昨日寝る前に書いていた部分を進捗として報告。月曜日の日記で言及した、別のアプローチというやつを実装した。実はこれもダメだったので、また次のアプローチを試すことになる。今度は少し実装が難しくなりそう。かなり最初のほうから候補としては上がっていたものの、とりあえず簡単に書けるものから試してみようとこれまで放置してきたのだった。今日は1時間ほどで終了。

午後4時40分から今週もサークルバチャに参加した。一応全問解いたことがあるのに、特に後ろ4問はどれも全く覚えていなかった。何とかその場で解け、1時間ちょっとで全完。4問目はエスパーした後解説を読んで感動。6問目はただ速そうだからという理由で書いたコードが実は2乗の木dpになっていたらしくびっくり。深く考えずに提出していた。7問目はしばらく有向グラフだと思い込んで苦しんだ。向きがあると解けなさそう。

https://kenkoooo.com/atcoder/?user=kotatsugame&rivals=&kind=category#/contest/show/59afc896-e37b-457a-99df-8fb92c8082aa

余った時間で解説を確認した後、1時間ほど通話を繋いで解説会に参加した。上に書いたようなことを喋っていた。

あまりの眠さにいったん仮眠をとろうと布団に横たわり、なぜか1時間ほどハーメルンを読んだ。午後8時を回っていい感じに眠気が来たので身を任せたところ、目覚ましで起きることができず、yukicoderに参加し損ねた。ハッと目を覚ましたら午後11時15分で絶望。

コンテスト終了を待ってAとBを通し、午後11時半からCF #818 div.2。

Dashboard - Codeforces Round #818 (Div. 2) - Codeforces

Aは $(a/\gcd(a,b),b/\gcd(a,b))=(1,1),(1,2),(1,3),(2,1),(3,1)$ に限ることがわかり、それぞれ $\gcd(a,b)$ としてあり得る数が単純な割り算で求まるので足し合わせた。Bは $k\times k$ のマス目の $((r+i)\bmod k,(c+i)\bmod k)$ にXを置いてコピー。

Cはまず $a_i\le b_i$ が必要。その上でとりあえず全要素を $\min b$ まで上げることができる。 $\min b$ を達成するインデックスはOKなので、そこから一つずつ遡って作っていくことを考え、条件を求めた。各 $i$ について $b_i=a_i$ または $b_i\le b_{i+1}+1$ ならよい。前者を見落としていたがサンプルの最初のケースが優しかった。

Dは題意を掴むのに手間取った。 $2^n$ 人が参加するトーナメント表と、各試合で左右どちらが勝ちあがるかが決まっているとする。高々 $k$ 個の試合について左右の勝敗を入れ替えて優勝者の番号を最大化されるので、最初の状態をうまく決めてそれを最小化せよという問題らしい。最初の状態は $1$ 番の選手が優勝するとして、そのノードからトーナメント表、つまり二分木を根まで登る途中のどこかで勝敗が入れ替えられる。これは特にたった一か所であることがわかる。なぜなら二か所以上入れ替える場合、最も浅いところで入れ替えたノードが優勝するから。すると、高々 $k$ 回の入れ替えでどこのノードが優勝できるかがわかってくる。

例えば1回戦で勝敗を入れ替える場合、選手一人が新たに優勝する可能性が出てくる。2回戦で勝敗を入れ替える場合、 $k\ge 2$ なら1回戦も入れ替えられるので選手二人が新たに優勝する可能性が出てくる。以下同様にして、 $i\le n$ 回戦で勝敗を入れ替える場合、 $0\le j\le\min(i-1,k-1)$ について新たに $\binom{i-1}{j}$ 人優勝する可能性のある人が登場する。すべて足して答えればよい。 $i$ における和から $i+1$ における和を求めて解いた。

日記を書いているときに、もっと見通しの良い方法を発見した。優勝者は二分木の根から勝敗に応じて左右の子に降りて行った先のノードである。常に左に降りるのを最初の状態としておいて、そこから $k$ 個まで深さを指定し、その深さでは右に降りることにした場合の行き先を考える。これは指定の方法 $2^n$ 通りに対しすべて異なるから、 $1\dots n$ から高々 $k$ 個選ぶ方法と優勝者は一対一対応する。つまり $\sum_{i=0}^{\min(n,k)}\binom{n}{i}$ が答え。

Eは典型的か。 $g=\gcd(a,b)$ とし、 $a=ga'$ 、 $b=gb'$ と書く。 $c$ と $g\mid n-c$ を固定すると、 $(n-c)/g$ を $a'$ と $b'$ に振り分ける方法であって $\gcd(a',b')=1$ となるようなものを数える問題になる。これは最初に $1\le(n-c)/g\le n$ すべてに対し求めておくことができる。つまり、 $1\le i\le n$ に対し $\gcd(a',b')$ の条件を無視すると $i-1$ 通りあって、そこから $j\mid i$ かつ $j\lt i$ なる $j$ についての答えを引けばよい。いわゆる除原理である。

$(c,g)$ を探索する際は、まず $g$ を決めて、次に $n-c$ を $g$ の倍数で全探索すればよい。ここも除原理と同様調和級数になる。

Fはよくわからない。次数の偶奇が合っている必要があって、また辺であって結ぶ頂点の片方の値に興味がないものは、もう片方の頂点を調整するためだけに使ってよい。よってそういう辺を最初に取り除いた後、残った辺をまずいったん向き付けて、その後調整できる範囲に収まるまで有向パスを見つけてひっくり返すということを繰り返してみた。グラフの隣接リストをsetで持って実装。いかにもヤバそうだが、制約が微妙に小さいので何とか……と思いつつ投げたら爆速で通った。

全完14位。Fは両方の頂点から $1$ 引いておけば $+2$ する頂点を選ぶ問題だと思えてフローで解ける、ということを知った。なんともしてやられた感じのする問題だった。Aは謎の式で解けるらしい。

09/05追記： $n\bmod 2$ と $n\bmod 3$ で場合分けしているだけらしい。確かに。

lcm(a,b) / gcd(a,b) <= 3 なる (a,b) の組を数えよって問題なんだけど、これ爆笑してる pic.twitter.com/QbQ8RYM027
— 物理好き (@butsurizuki) 2022年9月2日

yukicoderのCを解いた。DはTesterした問題なのでAC済で、EFはわからないのでまだ通していない。とりあえずここまででコメントを書いておこう。

DMを確認するとyukicoderのTester依頼が届いていて、考えているうちに微妙にやる気が出てきたので気合いを入れて起き上がった。
週記（2022/08/01-2022/08/07） - kotatsugameの日記

yukicoder contest 359 - yukicoder

Aはpopcountがちょうど $2$ か、 $2$ 以上で $1$ が連続しているか。Bは適当にやるとダメだし、文字列を持ちながらdpできる制約でもない。少し考えて、辞書順最小の文字列とそれを達成できる位置の集合を管理すればよいことに気づいた。Cは $A$ と $X$ を混ぜて昇順にソートすれば $X$ 以下の値がどこで出現するかをBITで管理できる。2本用意して個数と和を持った。

DはTesterした時にあった公式解説が大胆に削除され、僕が書き添えたTester解がトップに来ていた。つまり新たにここに書くようなことは何もない。今は余談に名残を残すのみだが、元は図表などあってかなり丁寧だったので、別に消す必要はなかったのではないかと思う。まあ今の解説に比べて複雑だったのは確かか。覚えていないのでここに再現もできない。

イナズマゼロニンという音MADが削除されたことを知った。色変記事で好きな音MADとして挙げていたのを覚えている。ひとまずタイトルがわかるように、記事に書き足しておいた。まだYouTubeに転載された動画が残っているらしい。

イナズマゼロニンが削除されました。
最終再生数: 735,195 以上https://t.co/xmg5xv0bQF #sm34036224
— ニコニコ動画削除・非公開監視bot (@niconicodeleted) 2022年9月2日

イナズマゼロニン https://www.nicovideo.jp/watch/sm34036224
AtCoder 赤色になりました - kotatsugameの日記

2時間ちょっと「異世界クイズ王　～妖精世界と七王の宴～」を読み返していた。昨日の日記でも少し触れたように最近QuizKnockを見ており、そういえばクイズを題材にしたなろうがあったなと思ってチラ見して、抜け出せなくなった。

https://ncode.syosetu.com/n1867fd/

やはり面白い。ただ競技クイズの話として読んでも、面白い蘊蓄なりテクニックがいろいろ登場して唸らせられる。ただここまで気に入るのにはもっと一般的な理由があって、競技クイズに人生をかけた主人公の、常軌を逸した執念の描かれ方が非常に好み。ひたすら真剣にクイズと向き合う様が格好良くて、自分も競技プログラミングにここまで情熱を傾けられたらなあと憧れる。

朝方から昼前までは日記を書いていた。オンサイトの参加記を作っていたせいで今週分をまだ1文字も書けていなかった。とりあえず大まかな行動をChromeの閲覧履歴から復元し、火曜日の分まで文章を作ったところで切り上げて布団に移動。少しハーメルンを読んで正午就寝。

09/03(土)

午後3時過ぎに冷凍弁当を受け取った記憶がある。日記に登場するのは7月以来らしく久しぶりだが、8月の間も配達がある週は毎回注文していた。ただそのころは土曜日の午後1時から5hに参加していたので、特に睡眠を中断されることなく受け取れていたし、また弁当に言及するタイミングもなかったのだ。

またすぐ寝て、今度は午後7時半起床。ハーメルンの更新を確認したり食事して午後9時からABC267。

NEC Programming Contest 2022 (AtCoder Beginner Contest 267) - AtCoder

Aは面倒。sedで場合分けをした。先頭の大文字で三つは簡単に区別がつき、それらを取り除けば残り二つの区別も簡単。適当に目についたhを使った。Bはもっと面倒だった。言われたことを頑張って実装。

Cは差分更新が簡単に書ける。問題を開くときにDと問題名が似ていることに気づいていて、Cの内容を把握した今、Dでは連続部分列ではなくただの部分列になるんだろうなあと予想がついた。しかしCと同じ制約とするとどう解くのかわからない。 $O(NM)$ なら簡単だが……と思いつつDを開いてみると、それが通る制約になっていた。ホッとしつつ実装。

Eは二分探索を考えるとBFSで判定できる。Fは、決め打った頂点に向かって $K$ ステップ進むのをダブリングで行うことを考えていたら、最も遠い子孫に向けて進むためのダブリングテーブルを全方位木dpで管理できることに気づいた。実装はかなり頑張った。

Gを少し見て、わからなかったので順位表を開いたら、Exのほうが通されているようだったので先にそちらに進んだ。見た目と通され具合から畳み込みで何かする問題に見えて、そういうつもりで考えたらすぐ解けた。要素が奇数個という条件がなければ $[x^M]\prod_i(1+x^{A_i})$ で書けて、 $\sum_i\binom{n}{2i}$ を二項定理から求めるのと同じ発想で $[x^M]\prod_i(1-x^{A_i})$ を使う方法を思いついた。積をマージテクで計算して1sec強。

Gに戻る。 $A$ 自体を並べ替える挿入dpの方向で考えることにした。同じ値をまとめ、小さい値から列に挿入するのを遷移にしてみる。 $A_i\lt A_{i+1}$ を満たしている位置の個数を持つと解けそうに見えたが、係数がよくわからなくなってしまったし、決めることが多すぎて間に合うように見えない。実は同じ値をまとめなくてもいいんじゃないかと思って考えると、解けた。

遷移の際は $A_i\lt A_{i+1}$ なる $i$ の個数、 $k$ とおく、がどのように変化するかだけに興味がある。新しい値 $a$ を $i$ と $i+1$ の間に挿入する（ただし先頭への挿入を $i=0$ で表す）とき、 $i=0$ である・ $A_i=a$ である・もともと $A_i\lt A_{i+1}$ 、のどれかが満たされている場合、 $k$ は変化せず、そうでない場合 $k\leftarrow k+1$ となる。

ここで $A_i=a$ ならば $A_i\ge A_{i+1}$ だし、逆に $A_i\lt A_{i+1}$ なら $A_i\lt a$ も成り立つため、この三つの条件は実は排反である。 $A_i=a$ なる $i$ の個数は挿入の方法に依存しないので、 $k$ だけdpで管理すれば遷移が正しく書け、これで $O(NK)$ となり解けた。

全完11位。上に5人以上8人以下の学生がおり、賞金は得られなかった。AがFAで嬉しい。Fはどの頂点からも直径の端点が最も遠い頂点の一つになることをすっかり忘れていた。ここでの実装によるタイムロスが順位的に痛い。

コードゴルフ。Aは入力を数値に変換し、余りを取ったりしてうまく答えを作る方法。odコマンドとdcを使う方法より、Rubyで文字列のsumメソッドを使ったほうが短くなった。BはRaku。配列の添え字をJunctionにしてからBoolにキャストすることで、ORを判定するための配列アクセスを最大限に減らせる。そうして作ったBool配列を暗黙的に文字列化しつつ、正規表現で/T.*F.*T/を探した。そのままだと/./が空白にマッチせず困っていたが、m/./とするとうまくいった。よくわからない。

CはRubyで書いて短くならないなあと唸っていたらPerlで大幅に縮んでいた。隙をついて現在の最短コードを取得。最初の答えを求めるのと差分更新をほぼ同じ式でできるのは、言われてみればという感じで巧妙。DはdpをAWKで書いた。木曜日に出たRTのテクニックを使っている。Eは解説のpriority_queueを使う方法をPythonで実装。以降は手付かず。

午前3時から3時間でDMOJのコンテストに出た。2600未満rated。終了が火曜日なので、感想は来週の週記に書く。

An Animal Contest 7 - DMOJ: Modern Online Judge

正午まで日記を書いていた。金曜日の終わり際まで書き上げたところで布団に入り、しばらくハーメルンを読んで午後2時前に就寝。

09/04(日)

午後8時起床。ゆっくり準備して午後9時からARC147。

AtCoder Regular Contest 147 - AtCoder

Aは操作の度に $A_i$ が半分未満になるので、愚直にシミュレートしてよい。その値は $0$ でなければ新しい最小値になるから、最初にソートした後はpop_back、push_frontだけで各操作を定数時間で実行できる。

Bは考察に見覚えがある。操作 $B$ によって1個飛ばしに見た数列をソートできるので、すべての要素について最初にあったインデックスと全体をまとめてソートしたときのインデックスの偶奇が等しければよい。特に今回は順列なので、同じ値の処遇に困ることもなく、単純に $P_i\bmod 2$ と $i\bmod 2$ を比較すればよい。ダメなインデックスは偶奇で同じ個数ずつ存在するから、それらをペアにして、操作 $B$ で隣接させた後操作 $A$ を1回行うことで一つずつ解消する。これが最適。

ところがWA。操作回数の見積もりに失敗していたらしい。操作 $A$ のために一度先頭まで要素を持ってきた後、元の場所に戻すというコードを書いていたが、全要素に対してそのようなことを行う場合、操作回数は $1\dots N/2$ の和を行き帰りで倍、偶奇で倍とおおむね $N^2/2$ くらいになる。最後の操作 $B$ によるソートが $1\dots N/2$ の和を偶奇で倍にして $N^2/4$ であることを考えれば、最大で $1.2\times 10^5$ 回くらいの操作をすることになっていた。戻さないようにすると単純に行き帰りの倍が取れて、条件を満たせる。

Cはよくわからないまま解けた。まず $r=\min R$ と $l=\max L$ を取る。 $r\lt l$ のときはその二つが違う人に対応するので、地点 $l$ と $r$ に一人ずつ並ばせて最初に戻る。 $l\le r$ のときは残る全員が $[l,r]$ に並べるが、特にこれまでの決め方から区間内に左右に同じ人数ずついるような地点が必ず存在するため、全員をそこに並ばせるのが最適。本当にこれで解けているのか半信半疑で出したらWAで、やっぱり考察が違ったかと思いつつサンプルを試していたら、実装ミスを見つけた。 $r\lt l$ のとき二人ずつ並ばせているのを忘れており、最後、全員を一気に並ばせるときの人数が間違っていた。

Dは面白かった。スコアが積なので、各 $1\le x\le M$ について $x\in S_j$ なる $1\le j\le N$ を選ぶ方法と読み替えておく。集合の列の前にこの選び方を固定し、列が何通りあるか考えるところまで典型。今、条件から対称差集合 $S_i\bigtriangleup S_{i+1}$ の要素はちょうど一つなので、それが $x$ であるような $i$ の集合と $x\in S_j$ を固定してみた。そのような状態が実現されるには他にどんな条件が必要か考えてみると、実は何も必要ないということに気づいた。

各集合に $x$ が含まれるかどうかだけ考える。その状態は $S_i\bigtriangleup S_{i+1}=\{x\}$ なる $i$ のたびに切り替わるため、 $x\in S_j$ という状態から左右にどんどん $x$ が含まれるかどうか決まっていく。当然矛盾が起こるはずもなく、 $x\in S_j$ を満たす列が常に、ただ一通りだけ、存在することになる。これに気付いた瞬間は本当にアハ体験だった。

つまり、 $j$ の選び方を決め打った時、どのような選び方をしてもさらに各 $i$ について $S_i\bigtriangleup S_{i+1}$ を決めるだけの自由度がある。それぞれ $N^M$ 通りと $M^{N-1}$ 通りなので、掛け合わせて答えとなる。通ったのを確認してすぐさまdcで縮めておいた。

Eに進む。二部グラフの完全マッチングだと思えるので、Hallの結婚定理を考えてみた。点数を入れ替える人の集合を $S$ として、すべての $T\subseteq S$ について $\#T\le\#\{i\in S\mid\exists j\in T\;s.t.\;B_i\le A_j\}$ が成り立つかチェックしたい。条件をよく見ると $\max_{j\in T}A_j$ だけに依存しているから、その値を $A_T$ と決め打った時、 $T$ としては $\{j\in S\mid A_j\le A_T\}$ を考えるのが一番 $\#T$ が大きくなって不等式がタイトになる。つまり、これだけ見ればよい。

最初に $S$ を $\{i\mid A_i\lt B_i\}$ とし、 $i\in S$ についての $A_i$ の昇順に $A_T=A_i$ としてチェックしていく。 $B$ を座圧してBITのインデックスとすることで不等式の右辺が求まり、これを満たすまで新しく $S$ に要素を追加する。どういう要素を追加するべきかというと、 $i\not\in S$ かつ $B_i\le A_T$ はまず必要。ここで $A_i\le A_T$ だと $\#T$ も同時に増えて何も嬉しくないため、 $A_i\gt A_T$ も必要。これらの条件を満たす $i$ なら、以降常に不等式の右辺の集合に含まれてくれるので $B_i$ の詳しい値に興味はない。よって $A_i$ が最大となるものを取って追加した。これはセグ木でできる。 $\#T$ を求めるのに失敗して1WAしつつAC。

Fはあきらめてコードゴルフしていた。最終順位は5完で67位。DからEに進むときに少し別のことをやっていたら、Eが思ったより通されたので、順位が低くなってしまった。ペナも多い。

少し解説や最短コードをチェックした後、すぐCF。ICPCルールの5hだが強気に30分遅れのソロ参加。

Dashboard - COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred) - Codeforces

ABGMHCLFKJEIをこの順で解き、12完で15位。当時のsolved順に数問開いて順に解くということを繰り返した。やはりペナルティが響いて、解いた問題数が同じ中では最下位だった。全完できなかったのは残念。

Aは $M=1$ のケースがサンプルにあって優しい。Bは $P$ が大きな人一人に小さな人を複数人くっつける。Gは $b^2-a^2$ という形で表せる正整数のうち $N$ 番目に小さいものを求めればよい。 $(a,b)$ に対する表を作ってみると、 $3,5,7,\dots$ と $8,12,16,\dots$ という斜めの列が見え、重複がないこと、二つの列で尽くされることは明らか。よって二分探索で解ける。

Mは右手を動かすパスを反転することで頂点 $1$ からしばらく辺を辿り、続けて逆辺を使い頂点 $p$ に辿り着くまでの時間を求めればよいとわかる。Hは $A_i\bmod 3$ と $A_j\bmod 3$ だけ見ればよいので、 $3\times 3$ 通り書き出してどういう分け方をすればよいか考えた。そもそもの式の形を間違えていて1WA。

Cは直径となる2点の色が同じ場合その色はもう使えないことにだけ注意する。ある点が2本以上の直径に乗ることはないので、直径の2点をペアにして、いくつのペアが同じ色になるか全探索した。あとは組み合わせ。Lはいろいろ試した末先頭から累積和をとると隣接swapになってびっくりした。先頭の項が非負かつ広義単調増加にしたいので、最小値をチェックした後転倒数を求めればよい。最後の項を移動させられないことに気づかず1WA。

Fは $W$ を達成すること自体は $+W$ して $-W$ すれば簡単。なのであとは微調整で区間を重ねる問題になって、LSBにのみ依存することがわかる。 $W=2^0,2^1,\dots,2^{29}$ に対し、各区間が $\bmod W$ でどの値を覆えるか求めて最も重なる位置を探すのは、イベントソートによりソート以外線形でできるから、軽めの $O(N\log N)$ を30回行うことで前計算しておけばよい。TL 1secのところ800ms強で通った。

Kは気合い。ビルの高さに対しビルのインデックスの集合を対応させるmapを持つことは簡単に思いつく。マージテクでクエリ3には対応できそう。しかしクエリ1と2が難しい。マージテクがどちらの集合からどちらの集合に値を移すかわからないため、各インデックスがどの集合にいるかはわかっても、高さがいくらかはわからないのだ。そこで、集合と高さをペアにして持つことにした。このペアをvectorに並べ、vector上の位置を高さから求めるmap、ビルのインデックスから求める配列を持ち、丁寧に管理する。1730msで一発で通って最高。

Jは2本のパスで頂点を覆う問題になる。端点四つを適当な頂点に設定したとき、各辺についてどちらかの部分木にある端点を数え、奇数個なら $+W$ 、偶数なら $+2W$ を足し合わせたものがパスの重みの和になる。ただし端点を2個と2個に分けるような辺について一つだけ一回も通らない、つまり $+0$ とすることができる。すでに置いた端点の数と $+0$ を使ったかのフラグを持って木dp。マージが盛大に間違っていて2WA。デバッグのとき、どの頂点を根にしても答えが変わらないかチェックするのが強くて、小さいランダムケースですぐ間違いを見つけることができた。

Eは素数を全探索しても見るべき頂点数が合計 $O(N\log\max A)$ 個にしかならない。dfs順で並べ、隣接する頂点のLCAを追加した木の上で答えを求めると、辺の数も同じオーダーで押さえられる。何度もグラフを作り直してdfsするのは怖かったので、dfs順に並べた後LCAが深いところを順にマージしつつ辺の寄与を数えることで解いた。マージをミスして1WA。

Iは問題文がいかついが解法は簡単。2番目と4番目の条件から、key treeの辺を順に見て二つの連結成分をマージするとき、同じタイミングでそれぞれの連結成分から1点ずつ取ったものに共通する閉路を作る必要がある。そのために辺を2本使うので確かに全体で $2N-2$ 本となっている。辺は区別できるので、繋ぎ方は連結成分のサイズを $x$ と $y$ としたとき $(xy)^2$ 。次に辺の重みについて、長さ $2N-2$ の順列 $P$ であって $P_{2i-1}\lt P_{2i}$ かつ $P_{2i}\lt P_{2i+2}$ なるものが対応する。 $P_{2i-1}$ と $P_{2i}$ が一度に使う辺の重みである。一つ目の不等式は先に2本の辺を区別したからで、二つ目の不等式は4番目の条件のため。これは実験すると $(2N-3)!!$ 通りあった。掛け合わせて答えになる。

Dに50分残したものの解けなかった。 $1,2,3,3,4,4,\dots$ という数列になると思ったのだが、わざわざTLが2secになっていることだしこんな簡単ではないのだろう。そうやって最後1時間は不完全燃焼気味。しかし逆に、それ以外の3時間30分はコンスタントにAC数を伸ばせて非常に気持ちよかった。このくらいの難易度の5hならソロ参加がかなり楽しいと感じている。

ARCのコードゴルフ。AはPerlで、for文でループしているリストを中で伸ばすと非常にシンプルに書ける。ただしmapを使ったり、リストへの代入をループと一緒に書くと、伸ばした分までループが回らないのでうまくいかない。Dはコンテスト中のdcが提出時間の差で勝っていた。残りC以外は手付かず。

CはOctave。答えがdouble型だと精度が足りないくらい大きくなるせいで、せっかく二つのベクトルの内積で書けるのに行列積を使えない。要素ごとに積をとってsum関数に投げてもダメだったが、これはsumがデフォルトでは内部でdouble型を使うからで、第2引数に"native"を指定することで元のデータ型を保ってくれるらしい。引数をint64にキャストしてそれを使ったら通った。元のコードからはかなり長くなってしまったが、別の言語で書くよりはまだ短そう。Octaveは大きなケースでのWAに苦しめられがちなので、他の問題でも使いどころがあったはず……と思いつつ、見つけられてはいない。WAだったコードを調べる必要があって難しい。

朝からはまた日記を書いていた。日曜日のARC途中まで書いて切り上げ、布団に移動。少しハーメルンを読んで午後1時就寝。結局今週中に参加記を完成させられなかった。情けないぜ。