週記（2021/05/17-2021/05/23）

05/17 (MON)

睡眠時間が短すぎて、9:00 には起きていたが半寝状態で 10:00 ぐらいまで何もしなかった。起き上がれたため、大学に向かう。 そんなんで眠すぎる故、行きの電車は何かをチェックしたり考えたりすることなくひたすら寝ていた。

大学に着くと、昨日の分の週記を書き上げて初めての週記を投稿する。妙な達成感がある。 それはそうと昼飯は月曜日のキッチンカーであるところのケイジャンビーフステーキチーズ＆ライスを食べた。寝不足には重かったが美味しかった。来週こそは写真を撮ってここに貼ろうと思う。

ゼミが始まる。この時期の月曜は B4 の輪講（例年同じやつ）なので聴きながら裏で作業したりすることが多い。 作業をしようと思ったが、今日の典型を確認していないことに気づいたので先にそちらをチェックする。

https://atcoder.jp/contests/typical90/tasks/typical90_ap

正整数 $ K $ が与えられて、10 進数での桁和が $ K $ かつ、その数そのものが $ 9 $ の倍数であり、さらに $ 0 $ を桁に含まないような整数を数え上げろ、という問題。

$ 9 $ の倍数である事と桁和が $ 9 $ の倍数である事は同値である事はあまりにも有名。というかまあ式を書けば一瞬で確認できる。 $ N $ 進数における $ N-1 $ の性質だと思う。 つまり、$ K $ が $ 9 $ の倍数でないなら答えは $ 0 $ であり、$ 9 $ の倍数ならば二つの条件は自然に満たされる。あとは $ 0 $ を含まないように整数を構成するだけだ。 これは $ 1 $ 回で $ [1,9] $ マス先に進める時の $ 0 $ マス目から $ K $ マス目までの経路数に等しい。普通に DP をするといい。更新の時に区間加算をするので高速になるが今回は遷移が多くないので愚直でも問題ない（というか $ 9 $ ならキャッシュとか考えて絶対に愚直の方が速いだろう）。理論上は線形探索は悪だが、実際はシーケンシャルな処理なので相当キャッシュとかが効いてある程度まではむしろ高速だよねという話題、あまり競技プログラミング界隈では聞かないな。

ゼミも終わり、一頻り喋ったりしたあと作業に戻る。作業の途中で典型のジャッジが来ていそうなので提出する。$ K \bmod 9 \neq 0 $ の場合に $ 0 $ を出力するのを忘れていて WA をもらう。書き直す。AC。 先週の金曜と土曜の典型をまだ書いていない。なぜなら最大流ライブラリをまだ書いていないためである。いやその理論だと土曜のは書けるな。 アルゴリズムもわかっているしなんなら空で書くことができると思うんだけど、どうせ書くなら綺麗にしたいため中々面倒くさい。

そういえば今日も途中で大学に入っているセブンへプリンを買いに行った。なんか毎週同じことをしている気がする。 大学に入ってからというもの一週間スパンでループをしているような気がする。社会にでたらもっとこれになるのかと考えたら尚更社会に出たくなくなってきた。日常に刺激がないと死んでしまうため。

ところで今作業がほぼほぼ調べ物フェーズなんだけど、全然出てこない。競プロの知見とかって死ぬほどよくヒットするけど、研究に必要な知見はゲボほど出てこなくて発狂しそうになる。 調べ物といえば先週ローカルに落とすかと言っていたチートシートはまだ落としてなくて $ \bmod $ を出すためにまたググってしまった。

なんか取れたデータが壊れていそうな気がしたが、もう燃料切れなので帰宅する。 帰宅して晩飯を食べて、もこうの最新動画を見て、ジャンプを読んだら日付変更まで 30 分を切っていた。 もこうが全然使われないポケモンを使って興奮している動画を見るのが好きなんだよな。 ジャンプは Dr. STONE でようやく千空が復活した。一言でコメントできるのが Dr. STONE ぐらいしかない。

伝説の害悪戦法「レベル1ココドラ」を完全再現してみたｗｗｗｗ【ポケモン剣盾】 - YouTube

例によって例のごとくこの時間に競プロをやろうとする。いい加減もう少しマシな時間にやる人間になりたい。 とりあえず最大流ライブラリが必要ない典型 41 の実装をすることにした。

凸包を求めるアルゴリズムを完全に忘れている。まあライブラリがあるからいいと言えばいいが、ソートして凸になるように上半分と下半分に分けて構築するだった気がする。多角形は反時計回りの順序の点の列にするため、最後の $ 2 $ 点と次に追加する点の関係がちゃんと反時計回りになっているかチェックして、なっていなかったら最後の点を削除、という操作を繰り返すと下半分が構築できる。上半分はソート逆順にやることで構築できる。最も左下と最も右上の点は絶対に凸包に入るので簡単に証明はできたはず(はず)。久々に書くと意外と面倒。自分の幾何ライブラリを見ると汚くてびっくりする。

典型 41 の解法自体は先週の週記に書いたので割愛する。今日は完全に寝不足なのでここで活動終了。

05/18 (TUE)

12:00 起床。かなり身体のダルさが取れた。今日は普通に活動ができそうだ。 正午まで寝ていたことがバレて親父がヒリついていたことを除けばかなり良い滑り出し（10 : 0 で僕が悪いのでかなりつらい）。 今日の典型を確認する。

https://atcoder.jp/contests/typical90/tasks/typical90_aq

二次元グリッドが与えられる。マスの種類は '#' と '.' であり、それぞれが壁と空間。壁を通ることはできない。スタート地点とゴール地点が与えられるので、スタートからゴールまで行くとき方向転換の回数の最小値を求めよ、と言う問題。

この問題は過去に何度か見たことがある気がする。普通のグリッド上の位置の状態をさらに $ 4 $ つの向きによって分割する。これで向きが変わる遷移について $ 1 $ 、そうでない遷移について $ 0 $ に設定した最短経路問題になる。この制約ならグラフを陽に持たなければ dijkstra 法で耐えるかもしれないが、まあ 01BFS をすればいいだろう。解説のキーワードは「追加の情報が必要な場合は頂点を倍加する」みたいなのだろうか。 ケアするポイントとしては最初の移動による方向転換だろうか。自分は始点に上下左右すべてぶち込んでやった。

ここでとんでもないことに気づく。自分の 01BFS が壊れていた。具体的に実装を見ると一回到達した頂点への距離更新が行われない実装になっていた。え、これを使って問題を通したことある気がするんだけど…と思ったけど、$ 0 $ の辺を先に全て隣接リストに入れれば壊れないためだな。かなりタチが悪いバグの残り方だな。直して push や。

時系列が前後するが、実装をする前に昼食をとっていた。昨日の残り物を食した。あと食べかけのコンビーフを処理した。 実装が終わったあとは、ジャッジ来てるかなと思って確認をしたが来ていない。とりあえず週末普通に競プロに力を入れすぎたため少しピアノを弾くことにした。

3~4 時間格闘をしていた気がするが、下手くそすぎてブチ切れそうになった。才能がまるでないように感じられるデーだった。競プロや音ゲーにもたまに訪れる日が今日だったようだ。脳血管が切れそうになったので切り上げて部屋に帰ってクーラーで涼んだ。 弾くときに楽譜が暗くて見づらくならないようになどの理由から白熱灯のライトをつけるのだが、これを弾きながら浴びるとクソ暑い。その部屋のクーラーがまだ使える状態でないためうっかり溶けてバブルスライムになりそうになっていた。

ジャッジが来ているか確認した。流石に来ていた。186ms だった。dijkstra 法でやると落ちる可能性が十分ありそうだ。グラフのサイズは最大で $ 1.6 \times 10^{7} $ ぐらいあるのでまあそれはそうか。

夕食の時間になったので、夕食をとる。チーズ入りチキンカツが美味しかった。というか気づいちゃったんだけどチー牛野郎なのでチーズが好きなんだよね。

夕食の後の一時間ぐらいは Twitter を見たり、ネットサーフィンをしたりしていた。 今日の典型をグラフを陽に持って 01BFS をやるとどのぐらいなんだろうと思って試してみた。1 sec 以上かかっていた。これは dijkstra はかなり厳しいんじゃないか？

明日の 10:45 提出の小レポートがある。今週は週末を自由に過ごしすぎたため、まずはシステムに上がっている講義音声を DL して聞く必要がある。今週はすべての音声ファイルが壊れていなくて安心した。この講義は大学院の講義の癖に全然専門じゃないし、専門的なこともしないため完全に学部生時代の一般教養科目を受けるのと同じテンションで参加している。社会勉強になりますみたいな。 講義音声を聞き終わり、レポートを書いて提出する。週ごとに 400 字前後の目算がうまくなる。

CLIST を確認する。二日後にコドフォの Div.2 があるらしい。いい加減、薄橙にもどらないと恥ずかしいように思ってきた。 そのためにも精進や。とりあえず、最大流のライブラリを作って verify して典型 40 を通すことにした。もういい加減盗人をやめたい。 その理論で行くと beats もそろそろ自分で実装した方が良いかもしれない。まあそれはまた今度…

05/19 (WED)

なんか知らないうちに寝落ちをしていた。11:00 起床。朝飯代わりの何かを口に突っ込む。 少し作業らしき何かをしていたが、間もなく昼食をとることになる。親子丼を食べた。かなりおいしい。

ピアノの日なので、手ならしをするために食後は出かけるまで弾いた。今日も下手くそだ、助けてくれ。 というかそろそろ気づいちゃったけど、これ俺が下手くそなのもあるけど単純にラ・カンパネラが難しい。 完全に暇な週とかがあったらみっちり練習したいが、大学に行く日は練習ができなかったりしてかなり困難だ。

レッスンから帰ってきた。そういえば今日はバタバタしてまだ典型を見ていないことを思い出す。最大流を Ford-Fulkerson と Dinic の両方で書いてリポジトリに push する前に、今日の典型から片づけてしまおう。

https://atcoder.jp/contests/typical90/tasks/typical90_ar

今日の典型は、長さ $ N $ の整数列 $ A $ と以下のようなクエリが $ Q $ 個与えられて、それを処理しろというもの。

• $ x $ と $ y $ が与えられて、配列 $ A $ の $ x $ 番目の数と、$ y $ 番目の数をスワップする。
• 配列全体を一つ右シフトする。一番右の要素は一番左に来る。
• $ x $ が与えられて、配列 $ A $ の $ x $ 番目の数を出力する。

最近の ABC でよく見るやつだ。実際に愚直にシフトすると間に合わない (平衡二分木を貼るのもまた一興だが…)。現在のシフト幅を持ってさえいれば $ x $ 番目の要素を見つけるのは簡単である。これを管理しながらクエリを一個当たり $ O(1) $ で処理できて OK。 雑に実装すると、剰余の演算が多くなる。割り算は（ある意味で当然なのだが）他の四則演算と比べて滅茶苦茶遅い。案の定 400ms とか返ってきてワロタ。掛け算をおこな三項演算子で書きなおす。71ms になる。

このタイミングで兄が部屋に入ってきて星野源と新垣結衣の結婚ニュースを見せてきた。ワロタ。これは絶対に Twitter の人々は大騒ぎだろうと思ってみたら大分楽しい感じになっていた。星野源は前川みくP なんですよね。現場からは以上です。

最大流のライブラリの作成に戻るが、インターフェースをどうしようか迷っている。構築問題で最大流を使うときに流量とかを知らなきゃいけないと思うんだけど、そこら辺のケアが一番面倒くさい。付加的な情報を辺に載せたいことがあるため、struct Edge みたいなものをユーザ定義にする（最もベーシックなやつは用意しておく）みたいなことをするのが良いかもと思ったが、逆辺を張るのをユーザ負担にするのは結構つらそう。インターフェースのことを考えていたら頭痛くなってきた。脳死で常に復元が出来るような辺を持つことにした…。

結果的な実装としては、辺のインデックスを任意に入力することを諦めて張った順番にインデックスを振る。辺インデックスに対応する始点と隣接リスト中の位置を覚えておいた。これをすることで辺インデックスの管理はユーザ負担となるが、代わりに辺の容量と流量を変更したり取得したりするのが簡単に $ O(1) $ で実装できるのでこれを採用。よく考えると ac-library と似たようなインターフェースになっている気がする。 メモリを余計に食うような気も一瞬したが、結局インデックスを辺に載せると辺を張る際に、逆辺と併せて int $ 2 $ 個分のメモリを消費することになるが、視点と隣接リスト中の位置を覚えるのも同じ量のメモリ消費なので変わらない。 復元に使わなそうな辺にインデックスを振らないようにできるように add_edge 関数をしようかとも思ったが、わざわざそんなことを気にする方が大変そうだと思った。

間に夕食を食べたりしながら納得のいく最大流ライブラリが完成した。実は Dinic を書くのが初めてだったのだが、この実装を見て DFS 途中で抜けて途中から再開するみたいな書き方があることを知った。これからの実装方針の糧にしたい。 最小費用流のライブラリも作ろうと思ったがなぜか一般グラフの最大マッチングアルゴリズムに関するスライドを読み始めてしまう。

https://www.dropbox.com/sh/7uhazzp6wvx9mi7/AACpEgmn--Grp9nVD3NOD9Hia?dl=0&preview=%E8%AC%9B%E7%BE%A9%E8%B3%87%E6%96%99.pdf

ふむふむなるほどと言いながら書いていたら夜中になっている。完成はしなかった。あともっと速いやつもあるらしい。いずれにしても一般グラフの最大マッチングについてまた今度にした。

05/20 (THU)

6:30 起床。起床時間の波がえぐすぎる。諸々支度をしてジャムサンドみたいなものを食して大学へ向かう。 家を出た時は全然眠くなかったのに、電車に乗っているうちにクソ眠くなってくる。最終的に典型を確認するのが億劫になるぐらい眠かった。

9:00 からのオンライン講義を受ける。眠いが、そんなに難しい内容ではないため耐えている。というか大学院の講義は意外と適当だ。 多分だけど大学院生の活動のほとんどが研究だからだろう。そんな感じで講義をそつなくこなす。 眠気もマシになってきたので、今日の典型を確認する。

https://atcoder.jp/contests/typical90/tasks/typical90_as

二次元平面上の点が $ N $ 個与えられて、$ K $ 個のグループに分ける。分けた時にグループ内の最大の $ 2 $ 点間距離を最小化せよ。距離は二乗で答えろ、という問題。

うーん、とりあえず $ N \leq 15 $ のため、全ての任意の点集合について最大の $ 2 $ 点間距離を時間内に求めることができる。 そこで bit DP をすれば $ O(K 3^{N}) $ でできそうである。具体的には、点集合ごとに取っていくことを考えて $ K $ グループ以下選んでその最遠距離の最大を求めればよく、被りのない点集合のみを選んで遷移すればこの計算量でいける。これ、間に合うのか？わからない。間に合って欲しいので考えるのをやめた。

競技プログラミングばかりやるわけにはいかないので作業をやる。全然身に入らない、眠すぎる。おかしいぐらい眠い。胃も今年度最悪のコンディションになっている。本日は営業不可能ということらしい。マジでメンタルも終了しそうになるが、人と会話して元気にはなった。ところで今日の昼はタンドリーチキン丼だった。写真を撮ることを毎度忘れる。胃が最悪なこともあって重いがうまい。

そんなこんなで何も捗らないまま家に帰って夕飯を食べる。食後も普通にボケーっとしていた。今日は 2 時間どころが 1 時間すら集中できないことが明らかなので、コドフォ Div. 2 をやらないことにした。「やらない」って宣言してからずっと「やっぱやろうかな・・・」みたいな気持ちになるの本当に勘弁してほしい。

活動が厳しい日で、書くことがあまりないため現在読んでいるマンガの話でも記録しておこうと思う。今「ハリガネサービス」と言うマンガを読んでる。バレーボールの漫画なんだけど、結構好み。作者がキャラクターを大事にする作品に弱い。構成は一般的なスポーツ漫画とそう違わないように思う。もしこの週記をを読んでいる人がいて、興味があったら是非どうぞ。

05/21 (FRI)

12:00 起床。頭はかなりスッキリした。今日は十分に活動ができそうだ。朝食を食う時間がもう残されていないのが残念だが。 昼食をとる。カレーだ。うまい。結局今週も一回も食事の写真を撮らなかった。 古畑任三郎の話などをしていた。田村正和が亡くなったのでまた再放送をやるらしいので見ようかな。

昨日の典型を通さないまま寝たため、昨日の考察の通りに $ O(K 3^{N}) $ の実装をする。怖がりなので生配列を使ったり、in-place にしてメモリ消費もできるだけ少なくしたりした。部分集合を列挙する bit のテク久々に書いた気がする。提出。AC。271ms だった。余裕じゃん。自分は結構厳しめに計算量を常々見積もってしまっている節がある。気を付けていきたい。

きよしくんのツイートを確認したら、彩色数に落ちるらしくてこれによって底が $ 2 $ になるらしいな。まあ（そもそも彩色数自体が）難しいので今はパスや。なぜならこういう問題で底の $ 2 $ と $ 3 $ の区別をつけるのは極めて難しいと思うため。

今日の典型を確認する。☆3 だ。

https://atcoder.jp/contests/typical90/tasks/typical90_at

$ 3 $ つの長さ $ N $ の非負整数列 $ A,B,C $ が与えられて、$ A_i + B_j + C_k $ が $ 46 $ の倍数になる $ (i,j,k) $ の組を数え上げろ、と言う問題。流石に見た瞬間かな。 $ 3 $ つの数列の各要素を $ 46 $ で割った余りを考えてそれぞれ分布を作る。あとはできた三つの分布を畳み込めばいい。普通に三重ループでも間に合うので今回はそれで実装した。普通に FFT を二回とかでもいいはず。早めにジャッジが来ていたので提出。AC。どうせ入力がボトルネックになって高速化を実感できないため速くはしなかった。

そういえば結局典型 40 を通していないことを思い出した。最小カットを意識する辺張りが簡単になるなぁを実感。Dinic と FordFulkerson 両方試す。それぞれ 9ms と 73ms 。Ford Fulkerson はワンチャン間に合わないかなと思ったが杞憂だった。

時計を見てゼミの直前だった。あぶね～と思ったがアウトだった。時々自分の部屋の時計は本当の時刻を示さなくなるのだが、それだった。二個時計があるのに全てが壊れるってなんや。稼働率の期待値計算壊れてないか？反省したのでちゃんとリマインダーを使うことにする。

ゼミが終わる。一般グラフの最大マッチングはとりあえず置いておき、最小費用流のライブラリを作ることにした。そもそもようやく自分のライブラリを作ろうと決心をした理由が GCJ で最小費用流が出題されたからである。自分は単純なので借り物のライブラリだと余りモチベーションが湧かないし、アルゴリズムが分かっていても具体的な実装を自分でしていないと弄れないし気持ち悪くて無理なのだ。どうしても使わなきゃいけない時のみこっそり人様のものを借りていたが、そんなんでは演習ができないため自分のものを作成することにした。あと結構大きい理由は、人のフローのライブラリって復元のためのメンバが用意されていなかったり、用意されていても自分に合わないインターフェースだったりする。ここが自分の納得のいくものにできるのは大きい。

とりあえず書き上げた。verify してない。

05/22 (SAT)

12:00 起床。最近睡眠習慣が崩壊している。体調は悪くない。朝食を軽くたべる（すぐ昼食のため）。 しかし、今日は一ミリも何をやる気も起きなかった。

ほどなくして昼食を食べる。マックを食べた。マックではいつもダブルチーズバーガーとチーズバーガーを両方たべる。トリプルチーズバーガーが常設されればこんな妖怪みたいなことしなくて済むのになあと思ったりもする。

本気でやる気が起きないのでしょうがなく蟻本でも読みなおすかと言う気持ちで、蟻本を読んで演習問題を解いたりしていた。POJ の C++ が旧石器時代なのがかなりストレスフルなことを久々に思い出した。アレ C++ じゃなくて C+ ぐらいだろ。

不機嫌な気持ちになったりしながら演習をしていて、油断して一瞬横になったのが仇となり夕飯の時間まで帰らぬ人となった。 夕飯を食べた。寝起きで食べたせいで胃が爆発しそうだ。

完全に自業自得なのだが胃にばくだんいわを抱えた状態で AISing Programming Contest 2021（AtCoder Beginner Contest 202） - AtCoder に出ることになった。脳みそ自体はそれなりに正常に動いているはずなので大丈夫だろう。

A 問題。$ 21-a-b-c $ python で送れば FA も狙えそうな問題だった。

B 問題。たまにある数字の $ 180 $ 度反転だ。幸いにもひっくり返すと Invalid になるような文字がなくリバースして $ 6 $ と $ 9 $ を入れ替えるだけ。

C 問題。ここにきて胃のばくだんいわのせいで冷静さを書いてしまう。$ i $ か $ j $ を固定すればいいのだが、脳を使わずにヒストグラムとっていじいじしてなんか合ったで提出した。$ 5 $ 分ぐらいかけた気がする。

D 問題。ばくだんいわがメガンテを唱えてしまった。マジでわからないと思い唸っていた。仕方なく a を $ 0 $、 b を $ 1 $ とみなすことで整数として扱うことができて、辞書順は普通に昇順になる。よって二分探索で桁 DP をすればよかった。実際は二項係数を使って手前から貪欲に埋めていくことができる。 ヤバすぎる。

E 問題。木のクエリと聞いて HLD を貼る準備をした。思ったより不思議な条件だなぁと思っていたが、根への最短パス上に $ U_i $ が存在するって先祖に $ U_i $ がいる、つまり $ U_i $ の部分木内ということをややこしく言っているだけだな。根への最短パスの長さが $ D_i $ と言うのも単純に深さが $ D_i $ ということである。まとめると $ U_i $ の部分木内に深さ $ D_i $ の頂点はいくつ存在するかと言う問題になり、Euler Tour と Wavelet Matrix の rank 関数で問題なく解ける。Wavelet Matrix を貼るのをやめて、vector を $ N $ 本持とうか悩んでいた時間が世界で一番無駄だった。後で Euler Tour + vector $ N $ 本をライブラリなしで書きなおしたところ普通にテキパキ書けたので、アホくさとなった。

F問題。最悪。凸包を構築しながら DP をして三角形の符号付面積の和のパリティが $ 0 $ のやつ数え上げていくのだと思った。脳が混乱して時間内に合わせることは不可能となった。こういう問題を時間内に合わせられるようになりたいな。

E までを早く解いていれば黄色になることができただろうが出来なかったため 1975 になった。ジワリジワリと近づいているが、こういうときの一回の事故はメンタルを崩壊させるためつらい。ARC 頼む。

コンテスト後 F 問題を書き続けているがサンプルすら合わない。人生が終了した。そうこうしているうちに TCO Round 2A の時間となった。

Easy。問題文が脅威的に長いし、明らかに不必要な部分が多い。open then rated でコレをやるの悪質な嫌がらせではないだろうか。最悪な気分になりながらも仕組み自体はそこそこ面白かった。証明されているけど一般に非自明に感じてしまうマジックって結構あるし、問題にできそう。

Med。大嘘を展開しており、記録するのも憚られるためノーコメントで。

うーん正直このコンテストでなくてよかったな。寝る。

05/23 (SUN)

12:00 起床。マジで起きられない病気になってしまっている。今日は活動をする。 人々がいてピアノができる雰囲気ではなかったのでパソコンでやるべきことを処理しようと思う。 始めたぐらいの時間に昼食の時間になってしまう。

昼食は確か昨日の残り物+α だったと思う。実家ぐらしなので出てくるのが有難い。喜んで残飯処理係になりまつ。 作業に戻る。しばらく作業をして、まあ日曜だしこのぐらいでいいかと言う気分になる。

競技プログラミングをすることにした。昨日の F を書いてみる。やはりサンプルすら合わない。一体どうしてだろう…これ故に赤 Diff なのだろうということを再確認しつつ、日を改めることにした。 そういえば昨日はボーっとしていて典型を見ていないことに気が付く。

https://atcoder.jp/contests/typical90/tasks/typical90_au

RGB からなる長さ $ N $ の文字列 $ S,T $ が与えられる。$ N \times N $ の表に $ S_i = T_j $ なら $ S_i $ を、そうでないなら $ S_i $ でも $ T_i $ でもない色でマス $ (i,j) $ を埋める。$ i-j = k $ のとなるような $ (i,j) $ が全て同じ色で塗られているような $ k $ を数え上げろ、と言う問題。

こういうのはとりあえず $ 0,1,2 $ に置き換えるところから始める。が、そんなにいい性質が見えてこない。$ S $ に対する $ T $ の位置が $ k $ に対応して、重なっている部分を見て色を塗るように考えられる。色 $ c $ で塗られるには $ c $ 同士か $ c $ 以外の二つの組しかないな～う～ん、なんとなく文字列アルゴリズムぽいなでもわからん～。みたいなことを一時間ぐらい考えてしまった。久々にわからない問題が来たのでワクワクしながら解説を読むことにした。

色 $ c $ に塗るためには $ c $ 以外の色が $ S $ に出現した際には、さらにもう一つ $ c $ でない色である必要がある。重なっている部分の文字の対応関係を 色→色 の写像として考えたときに全単射なので、$ S $ か $ T $ において $ c $ でない色同士を入れ替えてやれば、普通の文字列のマッチング問題として解ける。ちなみに全単射は必要条件ではなく、対応関係を二部グラフで考えたときに出次数が高々 $ 1 $ になっている方の文字列を書き換えることでマッチング問題に落ちると思う。

$ 3 $ 種類に文字列 $ T $ を変換することで文字列マッチング問題に落ちた。しかし、まだ問題は解決していなくて単純にマッチングすることを考えると効率のいいアルゴリズムでもマッチング文字列の長さの合計ぐらいの計算量がかかり今回は $ O(|T|^{2}) $ で明らかに間に合わない。よく考えるとマッチング文字列は $ S $ と $ T $ の prefix と suffix（逆も）が対応しているため、Z-Algorithm を使えば効率よくマッチングできる。解説にはローリングハッシュが書いてあったが怖いのでこちらかな？

この問題からは結構知見が得られて満足した。 色々しているうちに ARC の時間になる。

AtCoder Regular Contest 120 - AtCoder

A 問題。普通に難しい。困るも、最大値を足したら確実に最大値になるやつだということに気づいたら prefix max の寄与が $ k $ 回、それぞれの要素の寄与が等差数列になっているため累積和の累積和を前計算することで AC。

B 問題。これも難しい。作るグリッドは対称であることは間違いないな～と思って眺めていたら、$ i+j $ が等しいマスを全て同じ色にしなければならないことに気が付く。あとはちょっと場合分けして AC。

C 問題。難しい。位置と数字が大事だと気づく。目標の数字を目標の位置に入れるには 数字+位置 が同じでなければならないと気づきを得る。数字+位置 のヒストグラムが等しければあとは転倒数でできるが、重複ありで座圧と数字の変換が必要な転倒数の実装に不慣れで $ 30 $ 分近くかけた。反省。

D 問題。大きい数字から $ N $ 個をプラスに寄与させることができそうなことに気づく。しかし、何を思ったか偶奇で分けて昇順降順で対応させれば構築できると思ってしまった。これは意図通りに対応しない可能性があるだろ…コンテスト後に過ちに気づき、プラスに寄与させる数字に mark を付けて stack を用いて mark を付けているのとつけていないのを対応づけて AC。

EF は読んでいない。

明らかに本番の動きをしくじって 1955(-20) になってしまった。来週こそ黄色になる… 睡眠習慣が頭おかしいことになっているので今日こそぐっすり寝ることにした。レベルの高い睡眠をとるんだ…。

そんなで今週はうまく活動と競技プログラミングができなかった週だったように思える。 来週はもうちょっと睡眠をうまくなって活動をしようと思う。 あと来週はちゃんと昼食の写真を撮る。

P.S. ここまで書いて、金曜に書いた最小費用流の verify をしていないことに気が付いた。すみません…

週記（2021/05/10-2021/05/16）

05/10 (MON)

9:00 前後に起床。月曜は研究室に行って on demand な講義を再生したり作業をしたりする日にしているが、今日は大学に提出書類などを作成するなどしていてゆっくりめに家を出た。この時間の電車は空いていて最高だと思う。 行きの電車の中で今日の典型 90 問を見た。

https://atcoder.jp/contests/typical90/tasks/typical90_aj

二次元平面上の点が $ N $ 個与えられて、指定された $ Q $ 個の点について、$ N $ 点の中で最遠のマンハッタン距離を答えろというもの。これどうせキーワードは「マンハッタン距離は 45 度回転」だろ。

まあ「45 度回転」なんて思わなくても $ |X|=\max(X,-X) $ であることを思い出せば、すぐに $ 4 $ 通りの式の $ \max $ であることに気づき、変数分離をすることでそのうち本質的なものは $ 2 $ つであり、マンハッタン距離は $ (x+y, x-y) $ のチェビシェフ距離と等しい結果が得られる。比が違ったり次元多かったりしたときにも使えるテクニックの方で頭に入れておきたいと思って再確認した。 この時点では眠くてスマホコーディングする元気はないので帰宅したら書こうと思った。

このタイミングで毎日の生活にメリハリがなさすぎるため、週記を付けることを決意。

昼前に大学に到着する。昼前なのであまり作業もしないまま大学に来ているキッチンカーへ先輩方と向かう。曜日によって来るキッチンカーが決まっているが、月曜はケイジャンビーフチーズ＆ライスを毎週食べている。牛肉とチーズが好きなチー牛野郎なのでこれしか食えない体にされつつある。 飯のあと、ゼミがある。後輩の輪講 ONLY の回だ。去年僕も読んだコードなのだがあまり詳しく思い出せないな、などと思っているうちに終了。昼からは作業をしていた。具体的には書かないが、C++ のコードを C で書きなおす必要があり本当に助けてほしかった。

20:30 頃に大学を出た。さすがにこの時間から飯も食わずにゲーセン行くのは戦士すぎるため直帰。帰りの電車では普通に寝まくっていた。デレステの営業だけ設定したかも。

帰宅。実家住みに感謝しながら晩御飯を食べる。おいしい。 今日の典型をコーディングする。脳が解けていてなぜか 2WA 貰いながら AC。 学部生の課題の採点、仕事、ピアノの譜読みなど色々なことに思いを馳せながら全て投げて ARC 118D - Hamiltonian Cycle の続きを考えていたが、解けない。 競プロすら投げて、今日は今朝買ったジャンプを読む。2:00 頃までじっくり読んでいた。 Dr. STONE の続きが最近とても気になる。まだスイカ以外のキャラクターは石化したままだ。 矢吹健太朗の絵が結構好きなのであやかしトライアングル読んでいるのだが、読んでる最中に親が入ってきたら嫌だな。今週もエッチだったし。 というかジャンプに掲載されている殆ど全ての作品は読んでいる。少年なので。 気が付いたら寝ていた。

05/11 (TUE)

13:30 に起床。最悪。驚くべきことにこの時間で二度寝はしていない。一度寝でここまで寝られる日はなかなかない。スマホで時間の確認と今日の典型の確認をする。

https://atcoder.jp/contests/typical90/tasks/typical90_ak

$ N $ 個の料理が与えられて、それぞれが $ L_i $ 以上 $ R_i $ 以下のコストをかけて $ v_i $ のスコアを得る。コスト合計がちょうど $ W $ になるような料理の作り方があれば価値の最大値を答えよ、という問題だった。制約を見て O(NW) とか O(NW log W) が間に合うのでナップザック DP である。連続部分列に対して同じ更新を行う DP は遷移をセグ木を使って高速化できる。この場合は in-place DP でセグ木高速化をするのが一番楽そう。一回の更新の中で幅が一定なので、スライド最大値を使って余計な $ log $ を付けずに済んだりする。ABC200E - Patisserie ABC 2 もこれだった（こちらは更新が加算なのでより簡単に $ log $ が取れるが）。さすがに典型☆5は見た瞬間だな。

朝食が消滅したので、親に申し訳なく思いながら昼食をとる。本当にカスなので申し訳なさがすごい。今日は講義を受ける予定もなければ、コンテストもないし大学へ行く予定もない。明日の昼までのショートレポートがあるぐらいだと思う。このショートレポートは講義内容の要旨と軽い意見を 400 字以内にまとめるというもので、講義を受けてさえいれば一瞬で終わる。などと思いながら午後の過ごし方（すでに午後だが）に思いを馳せていた。

飯を食べ終わったので、採点、仕事、ピアノの譜読み、作業の 4 つの内どれをやろうか悩んだ。正直どれもクソ大事なタスクである。ピアノのレッスンが明日なので、とりあえず譜読みを優先することにした。Twitter で競技と音ゲー以外のことを全く話さないため自分がピアノを弾かなければならないことを時々忘れる。実家住みでピアノがあることはすごく有難いが、家族の都合に合わせて練習をしなければならないのは、このコ某ナ禍の苦しみポイントの一つだと思う。

16:00 ぐらいからウォーミングアップから譜読みを開始。ラ・カンパネラと言う曲なのだが、譜読み自体は簡単で手の運動が鬼のように遠い。アマゾンで第三の腕を購入したいレベルで遠い。体感 5 キロぐらいある。四苦八苦しながら 3 時間ほど練習した。早くある程度弾けるようにならなければ…

夕食をとった後、今日の典型を実装する。in-place DP をセグ木で高速化やっぱり実装が楽だ。in-place だとキャッシュに載りやすくなり思っているより早くなるからあまり $ log $ を落とす気にならないんだよな。とはいえいざと言うときに落とせないのはまずいと思ったのでスライド最大値でも通しておいた。deque に添え字を入れる実装をしているのに添え字と比較していたりして無駄な時間を要した。 スライド最大値（最小値）はほぼ自動で書けるようにしておきたいな。

この時点でもう今日は休むフェーズに入ろうと思ったのだが、ここで昼食時に思いを馳せていたところの 400 字レポートを書くことにした。講義音声が配られるタイプの講義なのだが、3 つある内の 3 つ目の音声が壊れていることを思い出した。報告しようとしていて完全に忘れていたのだが、課題に関係ある部分でなかったため 400 字のレポートを書く。せっかくこの時間に身体を縦にしていた記念として、ついでに on demand の講義を一つ消化しておいた。大体知っている内容で涙がちょちょ切れてしまったが消化したという精神的優位が得られたため良しとした。

提出を終えた後は、競技プログラミングを少しやった。虚無を 2~3 問と青 diff を 2~3 問解いた。 経験的に二分探索をしたくなるような設定でなぜ二分探索が効くのかについてちょっと整理したくなってきた。いろんなパターンがあるため、これから見つけたらメモしておこう…

布団に入ってもこうの動画をみているうちに寝落ちした。

05/12 (WED)

11:00 に起床。二日連続で寝坊したが、このぐらいならまだ許容範囲かな。トーストとコンビーフの朝食をとる。例によって今日の典型を見る。今日は☆3 か。

https://atcoder.jp/contests/typical90/tasks/typical90_al

$ 2 $つの整数 $ A,\,B $ が与えられてその最小公倍数を求めよ。ただし $ 10^{18} $ を超える場合はそれを報告せよ。と言う問題だった。 最小公倍数は $ \frac{A \times B}{\gcd(A,B)} $ なので $ \frac{A}{\gcd(A,B)} $ と $ B $ の掛け算が $ 10^{18} $ を超えるか確認すれば良い。単純にやるとオーバーフローして壊れるので $ \frac{A}{\gcd(A,B)} > \left \lfloor \frac{10^{18}}{B} \right \rfloor $ で判別すればいい。多倍長や 128 ビット整数を使えばそのままいけそう。

余談だがこの記事を書いている最中にまた床関数とかの括弧の大きさを自動で調整するやつの書き方を調べた。全く覚える気がないので本当に毎度調べてしまう。よくまとまっているチートシートをローカルに落としてしまおうか…

そうこうしているうちに正午を回ってしまう。譜読みの優先度が MAX なので昨日の続きをすることに。 昼飯には、買ってきてもらった弁当を食す。そぼろと卵の弁当なんだけどシンプルでおいしかった。食した後また譜読みに戻る。 右手が言うことを聞かないため叱咤していたら時間になってしまっていた。急いで家を出てピアノ教室に向かう。下手すぎて泣きそうになるも、終えて帰ってくる。

ピアノから帰ると 15:30 ぐらいで典型のジャッジが来ているかなと思って確認したら、追加されていたので提出。AC。 今日は作業をしなきゃいけないんですよね～って心のクソデカ声で叫びながらちょっと疲れたのでデレステを起動した。

馬鹿なので 3 時間ぐらいデレステをしていた。理性の敗北。でもデレステの感覚を思い出してきた。そうだこのゲームをスマートフォンでやるにはそれなりにコツがいるんだった。具体的には複数指運指の使いどころが難しい。

Radio Happy [MAS+] をとりあえず FC 。AP でないので不満。

段々解ってきた Gossip Club [MAS+]。近日中に AP したい。

夕食を食べたらさらにやる気を失ってしまった。2 時間ぐらいマンガアプリでマンガを読んでいた。5 時間連続で生産性のない活動をしていたことになるのでまずいと思い、せめて競プロをすることにした。とくにやりたい問題もなかったので Problems の Recommend 機能を使うことにした。D - Double Landscape があったので適当に選ぶ。Diff 1670 だと思って舐めていたら酷い目に遭った。普通に 40 分以上かかったので割と助けてほしいな。

問題概要は、$ N \times M $ の表に対して $ [1,N \times M] $ の数字を重複なく書き込むことを考える。$ A_1, A_2, \cdots, A_N $ と $ B_1, B_2, \cdots, B_M $ が与えられて、$ i $ 行目の最大値が $ A_i $ 、$ j $ 列目の最大値が $ B_j $ となるような書き込み方の通り数を求めよ、というもの。重複がないから $ A $ や $ B $ の内部で数字の重複があったらその時点で $ 0 $ なことがわかる。また、$ A $ にも $ B $ にも含まれる数字がある場合、その行と列が交わるマスは必ずその数字を書き込まなければならない。また、とりあえずマス $ (i,j) $ は $ \min(A_i, B_j) $ 以下の数字を書き込まなければならなそうだということがわかる。大きい数字の方が明らかに書き込みづらいので、制約を守るようなまだ書き込まれていない $ X $ の書き込み方を $ X $ の大きい方から求めて掛け算をしていくといいと思った。最後のサンプルが合わない。参った。よく考えたら、$ A $ や $ B $ に数字があるってことは、その行や列にその数字がなければならないことに気が付いた。行や列に書き込みのある数字の場合はより強い制約で置くように書きなおしたらサンプルが合う。提出。AC。 こういう問題を速く解くにはどうすればいいか途方に暮れていた。と思ったけど自分で最初に書いていた条件を忘れていただけなので競技痴呆をやめることによって改善されそう。自分で書いた考察メモはちゃんと見よう！

C - 掛け算 も Recommend されていたためやる。$ a_1, a_2, \cdots, a_N $ と正整数 $ A, B $ が与えられるから、数列で最小の数に $ A $ を掛けるという操作を $ B $ 回行った結果をソートした上で、$ mod 10^{9}+7 $ で答えろという問題。冷静に考えると、 $ a $ 内の数字は実行する演算に比べて差が小さいなと思う。全部が $ 1 $ 回以上掛けられたらすべての数を $ A $ で割ることで過去の状態と同一視することができる。全部が $ 1 $ 回以上掛けられるのにかかる操作回数は $ A \geq 2 $ なら $ O(N log A) $ ぐらいな気がする。これぐらいなら愚直に計算が余裕にできる。結構実装が嫌で、疲れていることもありいやいや言っている時間が長かったので反省。結局 $ A=1 $ のパターンを忘却して $ TLE $ を一回食らってしまった。

この時点で 1:00 になっている。木曜は早起きしなくてはならないため寝る。

05/13 (THU)

7:00 起床。眠いし寒い。適当にパンを食して家を出る。家を出て少し歩くと雨が降っていることに気が付く。最悪だが予定した時刻の電車に乗れないのはもっと不愉快なので我慢してそのまま行く。 いつもの通り電車内で今日の典型を確認する。

https://atcoder.jp/contests/typical90/tasks/typical90_am

問題概要は、$ N $ 頂点の木が与えられてすべての頂点の組に対してその距離の和を求めよ、というもの。脳がうまく起動していないのか最初に全方位木 DP をして最後に $ 2 $ で割る解法を思いつく。もちろんこれでも $ O(N) $ なので問題はないが、こういう問題は寄与を考える方が筋が良いだろう。実際にそれぞれの辺の寄与を考えると、その辺を切ったときに出来る $ 2 $ つの木のサイズの積になる。これを足し合わせればいいので部分木のサイズを持つ簡単な木 DP で良い。

大学に着く。木曜日はオンラインの 1 限があるのだが、これを受けてから登校すると微妙な時間なのでいつも大学で聴いている。今週の課題はものすごく簡単そうということがわかった。今日は朝から胃が重くダルかったのであまり作業に身が入らない。だめそうなので研究室に置いてあるルービックキューブで遊ぶことにした。過去のしょっぱいタイムを塗り替えるために普段使っているのとは別の揃え方を調べて覚えた。作業に戻ったり、周りの人と喋ったりしているうちに昼の時間となった。

木曜はキッチンカーのタンドリーチキン丼をたべることが決まっている。いい加減別のメニューを試したいが冒険して口に合わなかった時のことを考えるとできない。胃が重いためタンドリーチキン丼が想像よりつらかったけどいつも通り美味しかった。

色々やってちょっと早めに大学を出た気がする。大学を出る前に典型を通す。作業はできたと思ってから何度もデバッグをしていたし、体調も微妙だったので今日の進捗はあまりよくなかった。気分転換にゲーセンに行くことにした。身体が不調なのか指が思い通りに動かなくて困った。一応それなりに満足して帰宅。

帰って夕食を食べる。帰ったら夕食があるって本当にありがたいことですね…。今日は何をやってもダメそうなのでベッドで横になった。 週記の今日の分を書いていないことを思い出したので急いで書く。日付も回っているので今日はもう寝ようかなと思うが典型以外一問も通していないのはマズそうなので少しだけ競プロをやることにした。

B - Boxes を解くことにした。 問題概要は、円環上に数字が並べてあって $ 1 $ 回の操作で任意の位置から時計回りに $ -1, -2, \cdots, -N $ を数字に実行できる。この操作を任意回行って全ての数字をピッタリ $ 0 $ にすることができるか判定せよ、というもの。問題がシンプルでかなり好み。問題文のみからでは自明な解法は浮かばない。引いていくこと考えるのは面倒なので、逆の操作で最初の数列を $ 0 $ から構成できるかを考えた。自明な性質として、$ 1 $ 回の操作で総和は $ \frac{N(N+1)}{2} $ 増える。よって与えられた数列の総和がこの倍数でなければ NO が判明する。ちょっと詰まるも $ 1 $ 回の操作の右隣との寄与の差は大体 $ +1 $ で端と端の部分だけ $ -(N-1) $ である。差に注目すればもっと扱いやすい制約として考えられそうだ。操作回数は 総和÷$ \frac{N(N+1)}{2} $ で決定するため、それぞれの位置について連立方程式から操作の開始位置として選んだ回数を求められる。あとは非負整数条件や操作回数の条件を確かめて問題がなければ YES。AC。考察 $ 15 $ 分の実装 $ 5 $ 分。難しい実装でもないのに遅い気もする。

うーん、操作が厄介なため操作が単純になるような量に着目するのは典型な気がする。あとは未知数が $ 2 $ つの式が一つしかないからもう一つを探すというのもアプローチの一つかもしれない。

あと気分でCoding Gameを登録した。やり方は明日にでも見ようか。

05/14 (FRI)

9:00 に起床するも、昨日のダルさが全然抜けてなかったので二度寝して正午過ぎに起床。朝食は食べないことにした。 レトルトのハヤシを温めている間に今日の典型問題を確認する。今日の問題は☆7なので見てすぐとはいかない。ハヤシを食べながら典型問題を考える。食べながらだと余り集中できないが、問題をグッと睨むと $ O(N³) $ で解けた。と思ったが嘘だった。わざわざ嘘のためにスペースを使うのはもったいないので割愛。改めて考えると依存関係にサイクルがないため、最小カットで最適化できるタイプの問題であることがわかる。世間では「燃やす埋める」と言われるやつだろう。実はまだ最大流ライブラリを作っていないため、WSL 環境でこの問題を通すのが面倒なので、実装を後回しにする。ライブラリをちゃんと作って早く人間になりたい。

典型を考えたり Twitter を見たりしている内に TA の時間がきた。TA の時間、最近本当に暇なため手元でずっと作業をしている。三週連続ぐらいで一回も質問が来ない。学部生の間で使えない TA の烙印を押されている可能性があるな。最後にされた質問も Eclipse の使い方だし、本音ではそんなの俺に聞かないで欲しい。TA の時間が終わると、ゼミの時間となる。自分の発表回ではないため聞く。色々あったが終わる。やんわりゼミの後に教授と相談する予定になっていたのだが、それを zoom で言い忘れる。これ確か前もやった、人はなぜ同じ過ちを犯すのか。急いで slack で連絡したら相談に漕ぎつけた。懸案事項も解決してハッピー。

夕食を食べる。夕食後はダラダラしていた。具体的には YouTube を閲覧していた。もこうがマナー講師にバチボコに怒られている動画面白すぎて呼吸困難になる。

例によってこのまま日付が変わるのはよくないと思い AtCoder Problems を開く。

D - Classified を解くことにした。こういう問題結構すき。問題概要は、$ N $ 頂点の完全グラフがある。全ての辺を正整数で色分けして、同じ色の辺を使って移動して元の頂点に戻った時に通る辺の本数が偶数になるような色分けで辺に割り当てた最大の整数を最小化せよ、というもの。

一番最初に出来るだけ少ない二部グラフに分解する問題だなぁということを理解した。最初の $ 10 $ 分ぐらいは $ N=4,5 $ の図を書いて唸っていた。とりあえず、頂点数 $ N $ の二部グラフを考えてみたところ、よく見たら補グラフは完全グラフ 2 つになっていることに気づいた。完全グラフのサイズが小さい程最適なのは自明なので、できるだけ半分に分割すればいいわけだ。分割統治的に再帰的に解けるなと気づいたので実装に入る。実装が下手でビビった。あと偶奇で分割していたが余計混乱する原因になったので反省。$ 15 $ 分ぐらいかけながら AC。 思ったけどこういう問題、大体再帰的に解けるよな。メタ読み下手くそなのであまり意識しないようにしてはいるけど。

C - 収集王 も解いた。グリッドに $ N $ 個のコインがあってあるマスに降り立つと同じ行/列のコインを収集できて、ちょうど $ K $ 枚収集できるような降り立ち方は何通りかと言う問題。これは流石に自分にとってはやるだけにしないとまずそう。グリッドがデカく $ N $ もデカいので二次元累積和とかはできない。同じ行/列の個数系の問題は交差する地点に置いてあるかどうかだけが本質がち。行/列についてそれぞれ何個コインが存在するか求めておいて、和が $ K $ になるものを基本的に考えればいい。降り立つ地点（＝交差する地点）にコインがあって和が $ K $ の数を引き、$ K+1 $ の数を足すことで問題ない。AC。$ 10 $ 分以内に AC できなかったので反省。

05/15 (SAT)

11:11 起床。朝飯を食しながら今日の典型を確認する。

https://atcoder.jp/contests/typical90/tasks/typical90_ao

$ N $ 個の座標が与えられて、それらを全て含むような最小の周を持つ多角形で覆う。この多角形の中にある (周も含む) 格子点の数を数えよ。 多角形は明らかに凸包。なので $ O(N \log N) $ で凸包を作る。最初に思いついた解法はそこから三角形に分割して Floor Sum を使って内部の格子点の数を重複を気にしながら数え上げるというものだったため、いやだなぁという旨のツイートをした。 しかし冷静になると、ピックの定理 - Wikipediaとかいうのがあったなあと思い出す。多角形の面積は原点中心の三角形の符号付面積の総和で求められる。辺上の格子点の数はまあ頑張って数えれば、あとは定理の式を整理すれば答えが出そう。

典型を考えていたり、ちょっとだけ作業をしていたりしたりしたら昼食の時間になってしまう。

昼飯を食いに出かける。ファーストキッチンを食べた。ここのポテトの質めちゃくちゃ高くないですか？すいてる昼飯どころ目的で来たけどポテトがうまいのを思い出せて満足。そのあとはゲーセンに向かう。身体の調子は悪くなさそうなのだが、あと一歩みたいなのが多かった。もうそういう日だということにした。最後の悪あがきをしたら SOUND VOLTEX で初の 19PUC が出た。一応めでたい。欲を言えばもっとかっこいい曲で決めたくはあったけど。

音楽 -resolve- [VVD] PUC

帰宅。鬼のように音ゲーをしていたせいで帰ると 19:00 前とかそんなん。 晩飯を食べる。音ゲーで完全に疲れているけど今日の ABC 大丈夫かななどと思う。とりあえず指のウォーミングアップも兼ねて既 AC の問題を解きなおしたりして時間を待つ。ABC が始まる直前に口にガムを放り込み集中力を高めようとしてみる。 A-E が「実家」みたいな問題だったため、ガムの集中力もあってか自分にしてはそう悪くないタイムで駆け抜けられる。 F がクリティカルっぽい考察までいくも詰め切れずタイムアップ。132 位で perf 2400 なのでヨシ！レートが 1964 になった。東京五輪だ。 しかし明日は ARC だ…流石にここまできて 1900 付近に戻されたら萎えるので体調によっては不参加を決めさせていただくかもしれない。

さて、 Google Code Jam Round 2 がある。ABC が終わって間もなく始まるのでバタバタしたが、特に問題はないように思える。特別眠くもなかった。

A 問題を開く。いきなり interactive である。interactive は詰まると絶望しかないので、戦々恐々としながら問題文を見る。見えない数列があって、区間を与えると最小値のインデックスが返る query をコスト $ \frac{10^{8}}{r-l+1} $ で実行できる。 $ 6 \times 10^{8} $ までコストを消費できて、こいつらをスワップすることで昇順にしろ、と言う問題。見た瞬間調和級数かな？と思ったが、そんな簡単なわけが…と謎読みをしてしまい時間を浪費する。全人類が一瞬で通しているため投げると通る。

B 問題を開く。問題については長くなりそうなので割愛。コイツに自分の今回の GCJ は破壊されてしまった。コーナーケースを見落としたり、コーナーの処理をミスったりして 4~5 ペナと無限時間を費やして AC。

C 問題を開く。こちらも問題については割愛。個人的にそんな得意そうな問題ではないし、small を通そうと思ったが順位表を見るにこれは large も通さないと結構やばそうな雰囲気があり、しばらく考えた後一旦 D 問題に行くことを選択。

D 問題を開く。難しそう。問題文は割愛するが、small は二部マッチングを解けばよく、Dinic を貼って通す。が、実装がへたくそすぎて、かなりの時間を費やしてしまっていた。

C に戻る。しばらくサンプルを使って色々試したり、唸ったりした結果 large まで解けた。が、この時点で残り 2 分だった。もう small すら間に合わないなと思ったので日本人の順位表を眺めたりしていた。

最終順位は 1514 位、c を投げていたら順位はもう少し上がっていただろうが読み通り ABcd は落ちていたらしいのでやはり C を通さなければならなかったな。A の迷いの時間、 B と d に使った時間みたいなのを何とかすれば来年は Round 3 に進めそうだな…

完全にふてくされてしまったので、明日は何もしないことにした。寝る。

05/16 (SUN)

12:00 起床。よく寝た。朝ごはんは食べないことにした。最近朝食を抜きすぎているのでそろそろ反省の方をさせていただきたいと思います。兄と一緒に KFC を食べに行くことにした。食べた。おいしかった。KFC のオリジナルチキンっておいしすぎないか？ウマ娘の話とか聞きながらダラダラして、ちょっとゲーセンで遊ぶことになった。

VALKYRIE ASSAULT は PUC を狙えるかもしれない

うっかり DDR にクレジットを入れてしまったため全身疲れているが、17:00 からえでゅほがあるため帰宅。

https://codeforces.com/contest/1525

A 問題。$ 1 $ リットルずつ入れて行って $ k : 100-k $ を作る問題。最大公約数でしょう。

B 問題。全体以外の区間を自由に並び替えられる操作を何回で与えられた数列を昇順にできるでしょうという問題。 昇順なら $ 0 $。端が正しい数字なら $ 1 $。それ以外なら $ 2 $。とやってしまいがちだが、よく考えると左端に $ N $ 右端に $ 1 $ がある場合は $ 3 $ になる。 結構ペナをもらっている人が多かった印象。

C 問題難しくて、D 問題を先にやる。一列に並んだ空き席と座られている席（半分以下）があって、人を移動して元々座っていない席にのみ人を座らせたい。移動量の最小値を求めよという問題。 これは移動先の空き席の集合が決まれば左から順番に人を割り当てれば良い。移動がクロスしなければ損しないよくある奴だ。この前のえびまさんのお誕生日コンテストでも見たな。E - Min Cost Sort ←これだ。 よってあとは空白を使う使わないを選択していく二次元 DP でいける。

C 問題。難しい。左右どちらかの向きを向いているロボットが一次元上に配置されていて、$ 1 $ 秒に $ 1 $ 向いている向きに移動する。左右に壁があり、壁にぶつかると向きを変える。ロボットどうしが整数座標でぶつかると爆発する。それぞれのロボットが爆発する時刻を報告せよ、という問題。 パリティが一致するロボットしかぶつかって爆発しないので分ける。あとは set をそれぞれ $ 2 $ つずつ使って時系列に沿ってシミュレーションする。こういう set いじいじ系が本当に苦手。

E 問題。制約で罠を仕掛けに来ている。$ N $ 個の直接支配する都市と、支配したい $ M $ 個の地点が与えられる。それぞれの都市から $ M $ 地点に対する距離が与えられて、支配されたターン数で支配領域が $ 1 $ ずつ増えていくので、ランダムな順番で $ N $ 都市を支配した時の支配できる地点の個数の期待値を求めよ、という問題。 最初はゴニョゴニョ bit DP とか考えていたが、期待値なので主客転倒を考えると、余事象が簡単に求められるため答えが出る。C より簡単じゃないか？

残念ながら E のバグとりが間に合わず 4 完。まあ耐え。

夕ご飯をたべる。肉がうまかった、助かります。 お腹いっぱいで ARC を辞退しようかかなり迷ったが、まあなんとかなるの精神で出場。

AtCoder Regular Contest 119 - AtCoder

A 問題。こういうのは一番影響のでかい文字から決め打っていく。今回は $ b $ を決め打てばあとは $ a $ を最大化するだけ。

B 問題。クロスせずに $ 0 $ を移動するだけ。さっきの問題の残像で解けるな。

C 問題。むずい。足してから引けばいいので実質マイナスは気にしなくて良い。区間に着目した時に端から消していって全部消せたら OK なのだが、その手続きを式に落とすと引き算の連結になり偶数和と奇数和が一致することと等価であることに千年かけて気付く。遅すぎる。偶奇の寄与を +- として累積和テーブルを作っていつもの等しい組みを数えるやつ。

D 問題。むずすぎ。依存関係をグラフにして SCC をするという嘘を生やす。これを一時間以上かけて実装して丁寧に WA をもらう。これで最大化できるのは操作列の最長だ・・・

E 問題。リバースというが、評価値が影響を受ける範囲はスワップより少ない。隣接二項を方向つき区間としてやると、これをつなぎ変えることになる。よく考えると逆向きの区間どうしをつなぎ変えても意味がないことに気がつき、最終的に区間の共通部分の長さの倍だけ改善することがわかり、あとはイベントソートなりなんなりで解ける。この問題を先にやってればなあ・・・

C が遅かった割には 耐えていた。ナイス耐え。黄色入りは来週以降に持ち越し。

なんかすごい夜更かしをした気がするが、何時に寝たか覚えていない。

週の後半はなんか自由人みたいな生活を行なっていたが、週記を始めたことで横になっている時間は減ったのでこの調子で来週も活動をしたい。

Educational Codeforces Round #107 E - Colorings and Dominoes

コンテスト中全然わからなかった． かなり多くの人が通していてショックを受けたので記事にしました．

冷静になって翌日に考察しなおしたら解けたけど，このぐらいはサラっと考察したいところ．

問題概要

$ N $ 行 $ M $ 列のボードが与えられる．ボードの各マスは黒か白で塗られている． 白いマスを赤か青に塗ることを考える． ここで，以下のようにドミノ（ $ 1 \times 2 $ のパーツ）を置くことを考える．

• 横に連続した $ 2 $ マスが両方とも赤なら，その $ 2 $ マスにまたがってドミノを置ける．
• 縦に連続した $ 2 $ マスが両方とも青なら，その $ 2 $ マスにまたがってドミノを置ける．
• $ 1 $ つのマスに $ 2 $ つ以上のドミノを重ねて置くことはできない．

塗った後の盤面の価値を，その盤面に置けるドミノの数の最大値とする． 全ての塗り方に対して，盤面の価値の総和を求めよ．

ただし答えが大きくなる可能性があるので， $ 998244353 $ で割った余りを答えよ．

制約

• $ 1 \leq N,M \leq 3 \times 10^{5} $
• $ NM \leq 3 \times 10^{5} $

考察

当然ながら白のマスの塗り方を全て試すのは最悪 $ O(2^{NM}) $ の時間計算量がかかるので無理である．

こういう問題は塗り分けた盤面単位で値を足していくという方針は難しく，筋が悪い． ドミノ $ 1 $ つの価値の総和に対する寄与を考える．

まず重複など何も考えずにドミノの寄与を考える． ドミノを置く隣接 $ 2 $ マスを全探索する．両方とも白いマスでなくてはならない． 下の図の左のように隣接 $ 2 $ マスに着目してやると，その $ 2 $ マスは所定の色で塗られることが確定する． その他の白いマスはそれぞれ $ 2 $ 通りの塗り方が存在するため，図の例なら $ 2^{5} $ 通りの塗り分けの時にその位置にドミノを置けることがわかる．

これを足し上げることで求められるのはすべての白マスの塗り分け方に対してすべてのドミノの置き方を考えたときに置いたドミノの総和である． この値はほぼほぼ求める価値の総和と一致しない．というのも，$ 1 $ つの塗り分けに対して $ 2 $ 通り以上のドミノの置き方がある時に重複して数えてしまうためである．

左の 2 つのドミノの寄与を単純に考えると，右の盤面に対して 2 通り数えることになる

重複，すなわち $ 1 $ つの塗り分けに対して複数のドミノの置き方がある場合について考える． ある塗り分けられた盤面に対して，横向きにドミノを置いていたとする． 同じ領域を使って縦向きのドミノに置き換えるということは当然不可能である． これは，赤に塗られた領域には縦向きのドミノを置くことができないためである． したがって，横向きのドミノの置き方を考える時はそのドミノが置かれている行のみについて考えれば良い． さらに言えば間に黒マスが挟まっても，その前後は配置について影響を及ぼさないため連続する白マスの列について考えれば良い． これは縦のドミノと列についても同じことが言える．

以上のことから $ 1 $ 次元の問題について考えれば良いことがわかる． 重複なく数え上げるテクニックの $ 1 $ つとして条件を付けて数え上げることで重複を防ぐというものがある． これはどうやら競技プログラミングの数え上げ典型らしく，しばしば問われる． よくあるのは（というか殆どこれな気がするが），最左のもののみを数え上げるというものだ．

今回の問題では，左から（上から）貪欲にドミノを配置する置き方をするときのドミノの寄与のみを考えることにする． 例えば，下の図の例では赤く塗ったマスが $ 5 $ つ並んでいるためドミノの配置は複数存在するが，太線のようなドミノの置き方しかしないものと考える．

横向きのドミノ 2 個の置き方は 3 通りあるが左から貪欲に詰めたときのドミノの寄与だけを考える

連続する白いマスの列について左から $ 1, 2, \cdots $ のように番号を振って考える． $ i-1 $ と $ i $ 番目のマスにまたがって置かれるドミノに着目したときに，そのドミノの寄与について考える． 貪欲に左から詰めたときの寄与のみを考えるため，ドミノのすぐ左側には偶数個（$ 0 $ 個も可能）連続している赤いマスがなくてはならない．それ以外はどちらの色で塗っても構わない． このような塗り方を愚直に計算すると，各ドミノに対して左側の赤の個数を全探索するため，全体で $ O(M^{2}) $ （縦の場合は $ O(N^{2}) $ ）かかってしまい今回の制約では間に合わない．

着目するドミノと数え上げるパターン

しかしよく考えると，すぐ左の赤の個数が $ 2 $ 個以上の場合については，$ i-3 $ と $ i-2 $ にまたがるドミノの寄与を計算する際に求めている． 具体的には，左の赤の個数が $ k $ 個の場合は $ i-3 $ と $ i-2 $ にまたがるドミノにおける左の赤の個数が $ k-2 $ 個の時に対応する．

よって遷移が $ O(1) $ の DP で求めることができ，すべての寄与を最悪 $ O(N) $ や $ O(M) $ で計算することができる． 注意点としては，他の行や列の白マスも自由に塗っていいことを考慮しながら $ 1 $ つ $ 1 $ つのドミノの寄与を足し上げていくことにより，プログラム全体で $ O(NM) $ で価値の総和を計算することができた．

個人的ポイント

• この手の盤面を決めて盤面のスコアを足し上げる問題はそのままでは筋が悪い．
  • スコアに寄与する単位（今回はドミノ）について，その寄与を考えると良い．
• 問題文を冷静に読むと同じ行/列，さらに連続する白マスの列についてのみ考えれば良い．
• 重複を防ぐテクニックとして，条件付きのものを数え上げるというものがある．
  • 最左の要素，最左のマッチング…などなどを考えることが多い．
  • ABC171 F - Strivore とか ARC114 C - Sequence Scores などよく出題されている．
• $ 2 $ 個ずつ伸びていくような数え上げは，DP で次元が落ちる．
  • 別に偶数個ずつではなく一般の自然数 $ N $ にしても同じ（だと思う）．

ソースコード

提出URL

▶ソースコードを展開

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert

#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}

using namespace std;

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//-------------------------------------------------
//--ModInt
//-------------------------------------------------
const uint_fast64_t MOD = 998244353;

class mint
{
private:
    using Value = uint_fast64_t;
    Value n;
public:
    mint():n(0){}
    mint(int_fast64_t _n):n(_n<0 ? MOD-(-_n)%MOD : _n%MOD){}
    mint(const mint &m):n(m.n){}

    friend ostream& operator<<(ostream &os, const mint &a){
        return os << a.n;
    }
    friend istream& operator>>(istream &is, mint &a){
        Value temp; is>>temp;
        a = mint(temp);
        return is;
    }

    mint& operator+=(const mint &m){n+=m.n; n=(n<MOD)?n:n-MOD; return *this;}
    mint& operator-=(const mint &m){n+=MOD-m.n; n=(n<MOD)?n:n-MOD; return *this;}
    mint& operator*=(const mint &m){n=n*m.n%MOD; return *this;}
    mint& operator/=(const mint &m){return *this*=m.inv();}
    mint& operator++(){return *this+=1;}
    mint& operator--(){return *this-=1;}

    mint operator+(const mint &m) const {return mint(*this)+=m;}
    mint operator-(const mint &m) const {return mint(*this)-=m;}
    mint operator*(const mint &m) const {return mint(*this)*=m;}
    mint operator/(const mint &m) const {return mint(*this)/=m;}
    mint operator++(int){mint t(*this); *this+=1; return t;}
    mint operator--(int){mint t(*this); *this-=1; return t;}

    bool operator==(const mint &m) const {return n==m.n;}
    bool operator!=(const mint &m) const {return n!=m.n;}
    mint operator-() const {return mint(MOD-n);}

    mint pow(Value b) const {
        mint ret(1), m(*this);
        while(b){
            if (b & 1) ret*=m;
            m*=m;
            b>>=1;
        }
        return ret;
    }

    mint inv() const {return pow(MOD-2);}
};

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M; cin>>N>>M;
    vector<string> f(N);
    rep(i,N) cin>>f[i];

    int w=0;
    rep(i,N)rep(j,M){
        if (f[i][j]=='o') w++;
    }

    vector<mint> d2(N*M+1);
    d2[0]=1;
    rep(i,N*M) d2[i+1]=d2[i]*2;
    
    vector<mint> dp(max(N,M)+1);
    FOR(i,2,max(N,M)){
        dp[i] = dp[i-2]+d2[max(i-3,0)];
    }
    
    mint ans=0;
    rep(i,N){
        const auto &row = f[i];
        int cnt=0;
        rep(j,M){
            if (row[j]=='o') cnt++;
            else cnt=0;
            ans+=dp[cnt]*d2[w-cnt];
        }
    }
    rep(j,M){
        int cnt=0;
        rep(i,N){
            if (f[i][j]=='o') cnt++;
            else cnt=0;
            ans+=dp[cnt]*d2[w-cnt];
        }
    }
    cout<<ans<<"\n";
    return 0;
}

Educational Codeforces Round #107 (Div.2) D - Min Cost String

この問題かなり難しく感じました． よく観察すると典型に落とし込めるということで，記事にしました．

問題概要

文字列 $ S = S_1S_2 \cdots S_{|S|} $ のコストを次のように定義する．

• $ 1 \leq i < j \leq |S| $ のようなペア $ (i,j) $ であって， $ S_i = S_j $ かつ $ S _ {i+1}=S _ {j+1} $ であるようなものの数

英小文字の最初の $ K $ 文字のみで構成される長さ $ N $ の文字列でコストが最小のものを $ 1 $ つ出力せよ．

制約

• $ 1 \leq N \leq 2 \times 10^{5} $
• $ 1 \leq K \leq 26 $

考察

まず，長さ $ N $ 文字列には $ 2 $ 文字の連続する部分文字列が（重複を含めて） $ N-1 $ 個ある． 文字列のコストはこの $ N-1 $ 個の部分列の等しいものの組み合わせの総和と等しい． よってコストを $ cost $ ，連続する部分文字列 $ ij $ の数を $ cnt_{i,j} $ として，次の式が成り立つ．

\begin{align} cost &= \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} \frac {(cnt _ {i,j})(cnt _ {i,j}-1)}{2} \\ &= \frac{1}{2} \left\{ \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} (cnt _ {i,j})^{2} - \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} cnt _ {i,j} \right\} \\ &= \frac{1}{2} \left\{ \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} (cnt _ {i,j})^{2} - (N-1) \right\} \hspace{15pt} \left(\because \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} cnt _ {i,j} = N-1\right) \end{align}

上の式で変数は $ cnt_{i,j} $ のみであるから，$ cost $ を最小化するには $ \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} (cnt _ {i,j})^{2} $ を最小化すればよいことがわかる．

$ \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} cnt _ {i,j} = N-1 $ であるから，和が一定の数列の二乗和を最小化すればよいことが分かり，これは（できるだけ）等しくなるように分配すれば良い（証明略）．

※実数の場合はコーシー・シュワルツの不等式で簡単に証明できる．

したがって，なるべく $ 2 $ 文字の連続部分文字列が被らないように文字列を構築していくことを考えればよい．この連続部分文字列は $ K^{2} $ 種類存在する．そして実は $ K^{2} $ 種類の $ 2 $ 文字連続部分文字列を全て含む 長さ $ K^{2}+1 $ の文字列を構成することが可能である．

ここでアルファベットを頂点に対応させたグラフを考える． すると $ 2 $ 文字の連続部分文字列は辺に対応し，文字列はこのグラフ上の歩道に対応する．

K=4 の時のグラフ

任意の辺を 1 回ずつ通る歩道をグルグル回れば，連続部分文字列の分布を最もフラットにできる． このような歩道は，オイラー路（Eulerian trail）の定義そのものである．

オイラー路を持つためには，すべての頂点の入次数と出次数が等しくなければならない． このグラフは，すべての頂点間に 1 本ずつ有効辺が伸びているため明らかに条件を満たしている． オイラー路の構築はグラフのサイズを $ M $ として， DFS で $ O(M) $ で構築が可能である（隣接行列のためのメモリの確保は別に考えています）．

オイラー路に対応する文字列を構築したら，長さ $ N $ に達するまで連結することで答えが得られる． 全体で $ O(N+K^{2}) $ で答えを得ることができる．

別解（コンテスト中の解法）

コンテスト中には全然オイラー路が見えなかったが長さ $ 2 $ の連続部分文字列 $ K^{2} $ 種類が被らない文字列を規則的に構築するための観察をしていた．

• $ K=1 $ の時は自明に "aa"
• $ K \geq 2 $ の時は $ K - 1 $ の時の文字列に $ K $ 番目のアルファベットを含む $ 2 $ 文字の文字列を含むようにすれば良い．
  • $ K=2 $ の時 "bb"+"aa"+"b"
  • $ K=3 $ の時 "cc"+"bbaab"+"cac"

上記のように再帰的に構築可能である．

個人的ポイント

• 要素を頂点，ペアを辺に対応させてグラフの問題に落とすことは多々ある．
• オイラー路は $ O(M) $ で構成可能．
  • 厳密には隣接行列を連想配列でするなどにより log が付いたりしそう．
• $ 1 $ パラメータの構築は，$ 1 $ つ前のものから簡単な手続きで作れることが多い．
  • 再帰的な構築を考える．

参考資料

競プロにおけるオイラー路とその応用について - Learning Algorithms

• これを見てオイラー路を構成を勉強しました．

ソースコード

オイラー路解

再帰構築解

▶ソースコードを展開

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert

#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}

using namespace std;

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K; cin>>N>>K;
    string S="aa";
    rep(i,K-1){
        char ch=(char)(i+'a'+1);
        string pref=""; pref+=ch; pref+=ch;
        string suff="";
        rep(j,i*2+1){
            if (j&1){
                suff+=(char)('a'+j/2);
            }else{
                suff+=ch;
            }
        }
        S=pref+S+suff;
    }
    while(S.size()<N) S+=S.substr(1);
    cout<<S.substr(0,N)<<"\n";
    return 0;
}

AtCoder Regular Contest B - 高橋ノルム君

見た目や diff 以上に手間取ってしまったので記録．

問題概要

$ N $ 個の点の座標 $ (x_i, y_i) $ と $ N $ 個の正整数定数 $ c_i $ が与えられる． $ i $ 番目の点が座標 $ (X,Y) $ に移動するには $ c_i * \max({|x_i-X|, |y_i-Y|}) $ 秒を要する．

全ての点が同時に動き始めて $ 1 $ つの点に集まるのにかかる最小の時間を求めよ．

制約

• $ 2 \leq N \leq 1000 $
• $ -10^{5} \leq x_i, y_i \leq 10^{5} $
• $ 1 \leq c_i \leq 1000 $

考察

集まる先の点を最適化して最小の時間を求めることは難しい．

というのも，$ c_i $ という係数があり単純な最適化は難しく単峰性もないため三分探索もできない．

というわけで，こういう時の伝家の宝刀であるところの答え決め打ち二分探索をする． そもそも問題自体が max-min 問題なので二分探索を疑った，という方針の人も多そう．

$ t $ 秒で全ての点が $ 1 $ つの点に集まれるかどうかを判定する問題を考えることになる． $ i $ 番目の点が動ける $ x $ 座標の区間を考えると， $ [x_i-t/c, x_i+t/c] $ となる． $ y $ 座標に関しても同様である． すなわち，各点の $ t $ 秒の可動域は正方形の領域になっている．

したがって，判定問題は「 $ N $ 個の正方形領域の全てに含まれる点が存在するか」と言い換えられる． これは， $ x $ 座標と $ y $ 座標を独立に考えて動ける区間の共通部分を取っていけば良い． この実装は区間 $ [l,r] $ を「$ l $ 以上 かつ $ r $ 以下」という制約に置き換えると簡単な最大最小の更新でできる．

以上により判定問題を $ O(N) $ で解くことができた． 二分探索とあわせて $ O(N log \, t_{max}) $ でこの問題を解けた．

余談

制約が $ 2 \leq N \leq 1000 $ なので，判定が $ O(N^{2}) $ の解法が存在するのではないかと考えた． よく考えると，正方形領域 $ A $ と $ B $ ， $ B $ と $ C $ ， $ C $ と $ A $ が共通部分があるときに $ A, B, C $ の共通部分は必ず存在する． このことは正方形領域が $ x,y $ 座標軸に平行な辺しか持たないことからわかる．

したがって，全ての正方形領域の組に対して共通部分が存在するかチェックすれば良い． これで $ O(N^{2}) $ で判定問題を解くことができた．

個人的ポイント

• 係数が付いていたりすると距離っぽい max-min 問題を解くのは難しい．
  • 答えを決めうって二分探索をすることで大体うまくいく．
  • Yakiniku Optimization Problem もこれだった気がする．
• 区間の共通部分を求める実装は，最大最小の更新で行える．
  • 存在しない場合 最大 < 最小 になるので判定も楽．

ソースコード

提出URL

▶ソースコードを展開

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
using lf = long double;
using P = pair<lf,lf>;

int main()
{
    int N; scanf("%d",&N);
    vector<int> x(N),y(N),c(N);
    for(int i=0; i<N; i++)
        scanf("%d%d%d",&x[i],&y[i],&c[i]);
    
    lf lo=0, hi=1e9;
    for(int q=0; q<70; q++){
        lf mid = (lo+hi)/2;

        P xlim(-1e5,1e5);
        P ylim(-1e5,1e5);

        auto merge = [](P p, P q){
            lf r1 = max(p.first,q.first);
            lf r2 = min(p.second,q.second);
            return P(r1,r2);
        };

        for(int i=0; i<N; i++){
            P xr(x[i]-mid/c[i], x[i]+mid/c[i]);
            P yr(y[i]-mid/c[i], y[i]+mid/c[i]);
            xlim = merge(xlim,xr);
            ylim = merge(ylim,yr);
        }
        bool ok=true;
        if (xlim.first>xlim.second) ok=false;
        if (ylim.first>ylim.second) ok=false;
        (ok)?(hi=mid):(lo=mid);
    }
    printf("%.15Lf\n", hi);
    return 0;
}

AtCoder Beginner Contest 026 D - 高橋君ボール1号

簡単ですが，なぜか詰まった覚えがあるので記事にしておくことに．

問題概要

正の整数 $ A,\, B,\, C $ と，以下の関数 $ f(t) $ が与えられる．

• $ f(t) = At + B \sin{C \pi t} $

$ t \geq 0 $ かつ $ f(t) = 100 $ であるような $ t $ を $ 1 $ つ見つけよ．

制約

• $ 1 \leq A, B, C \leq 100 $

考察

この問題文は，求める $ t $ はあるものとして書かれているが念のため確認をする． 制約から $$ -100 \leq B \sin{C \pi t} \leq 100 $$ は明らかである．一方で $ At $ は $ t $ が大きくなれば無限に大きくなる． $ f(0) = 0 $ であり $ f(t) $ は明らかに連続関数であるから，中間値の定理より必ず $ 1 $ つは解が存在する．

具体的には制約から $ f(200) \geq 100 $ であることが保証されるので，区間 $ [0,200] $ に解が存在することが分かる． 中間値の定理で存在が保証される解を $ 1 $ つ見つけるアルゴリズムとして，二分法が知られる． 二分探索と同様の手法で，解の存在範囲を狭めていくアルゴリズム (https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%B3%95)．

$ f(t) $ の計算自体は高速に行うことが出来るので，十分収束する回数二分法を回すことで正解が得られる．

個人的ポイント

• 連続関数 $ f(x) $ に対して $ f(x) = const. $ みたいな方程式の解を $ 1 $ つ求めるときは二分法．
  • 最小のものとかになるとまた話は変わってくる．
• 今回は常に解が存在したが，しない場合があるような制約で出題されることもありそう．
  • しっかりと存在しない条件を確認する．

ソースコード

提出URL

▶ソースコードを展開

#include <iostream>
#include <cmath>

using namespace std;
using lf = long double;

constexpr lf PI = 3.14159265358979L;

int main()
{
    int A,B,C; scanf("%d%d%d",&A,&B,&C);
    auto f = [&](lf t){
        return A*t + B*sin(C*PI*t);
    };
    lf lo=0, hi=201;
    for(int i=0; i<80; i++){
        lf mid = (lo+hi)/2;
        (f(mid)<(lf)100)?(lo=mid):(hi=mid);
    }
    printf("%.15Lf\n", lo);
    return 0;
}

Educational Codeforces Round 104 (Div.2) - D. Pythagorean Triples

高校数学みたいな問題でした． 脳みそが働いていなかったこともあって，相当な時間詰まってしまいました…

脳みそが死んでいても手を動かすだけでこの手の問題を解けるように整理しておきます．

codeforces.com

問題概要

ピタゴラス数とは $$ a^{2}+b^{2}=c^{2} \tag{1} $$ を満たす正の整数 $ (a, b, c) $ の組である． 誤ったピタゴラス数の定義 $$ c=a^{2}-b \tag{2} $$ を考える．$ (3, 4, 5) $ はピタゴラス数正しい定義と誤った定義両方を満たす． このように，両方の定義を満たし $ 1 \leq a \leq b \leq c \leq n $ を満たすような $ (a, b, c) $ の組の数を求めよ． テストケースは $ t $ 個与えられる．

制約

• $ 1 \leq t \leq 10^{4} $
• $ 1 \leq N \leq 10^{9} $

考察

式 $ (1) $ と $ (2) $ を両方満たさなければならないため，連立させる． 共通する $ a^{2} $ を排除したいので辺々足し合わせて整理する．

\begin{align} a^{2}+b^{2}+c&=a^{2}+c^{2}-b \\ b^{2}+b&=c^{2}-c \\ b(b+1)&=c(c-1) \\ b&=c-1 \tag{3} \end{align}

上の式 $ (3) $ を $ (2) $ 代入して（別に $ (1) $ でも良い）

\begin{align} a^{2}-(c-1)=c \\ a^{2}=2c-1 \tag{4} \end{align}

$ a $ と $ c $ の関係式が得られた．組の数え上げの典型であるところの関係式が得られたら文字を固定するをやる． こういうのは次数が高い文字から決めうつのが好ましい．（ $ a $ と $ c $ の上限が同じなので次数が高い $ a $ の方が探索範囲が狭まる）

式 $ (4) $ と制約 $ c \leq n $ より $ a^{2} \leq 2n-1 $ を満たす $ a $ を考えればいいことが分かる． また 式 $ (4) $ から $ c $ が整数である条件は $ a $ が奇数であれば良いことがわかる． $ b=c-1 $ なので $ c $ が整数であれば $ b $ も整数なのでこちらも同時に条件を確認できる．

最後に $ 1 \leq a \leq b \leq c $ の条件を確認する．

• $ a $ を $ 1 $ からインクリメンタルに全探索するので $ 1 \leq a $ は満たされる．
• $ b = \frac{a^{2}-1}{2} $ と計算できるので $ a \leq b $ はそのまま条件確認すれば良い．
• $ b \leq c $ は常に満たされている．

$ a^{2} $ は $ a>0 $ で単調増加するので $ 1 $ つのテストケースを $ O( \sqrt{n} ) $ で計算ができる． $ O(T \sqrt{n} ) $ は正直厳しいケースがありそう． $ n $ の最大値を $ n _ {max} $ として $ a^{2} \leq 2 \cdot n _ {max} - 1 $ までについて前計算でテーブルをすれば，二分探索によって各テストケースに $ O( \log{n} ) $ で答えられる． こうすることで，時間計算量 $ O( \sqrt{n_{max}} + T \log{n}) $ で安心して Submit することができる．

別解

計算量はそう変わらないんですが，別の解法を一応示します． $ a^{2} $ が $ a>0 $ で単調増加で $ b=c-1 $ とおけば，$ a \leq b \leq c $ も $ a=3 $ 以上の時は満たされている（ $ f(a)=b-a=\frac{a^{2}-1}{2}-a $ のグラフを思い浮かべれば自明かと思います）．

つまり，$ 2n-1 $ 以下で $ 3 $ 以上の奇数の平方数を数え上げれば問題文の条件を全て満たす． これは $ a=2m+1 $ などと表現すれば二分探索で求めることができる． 前計算が要らずに $ O(T \log{n}) $ になり，うれしい（？）

謝辞

前計算をしない $ O(T \sqrt{n} )$ が普通に 358 ms で通りました．実行時間の見積もりが下手すぎて涙…。

個人的ポイント

• 連立方程式が出てきたらとりあえず文字を減らすよう頑張る．
  • 文字が $ 2 $ つ以下にできたら後は大体算数か二分探索．
• 次数が大きい方から決め打つと，十中八九嬉しい．
  • これはもう脳死でやれるだろ（自戒）
• 整数組数え上げ問題はちゃんと最初の条件をちゃんと確認する．
  • ちゃんと確認しないと頭悪い日だと混乱してしまう…
  • 整数条件と不等式
• なんか軽い $ 10^{8} $ ループぐらいならもう脳死で投げちまうか．
  • C++ は最強なので大体通る気がしてきたぞ．

ソースコード

提出URL1(前計算)

提出URL2(二分探索のみ)

提出URL2(前計算なし)

▶ソースコードを展開

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
using ll=long long;
 
const ll N_MAX=1e9;
 
int main()
{
    vector<ll> v;
    for(ll a=1; a*a<=2*N_MAX+1; a++){
        if ((a*a&1) && (a*a-1)/2>=a){
            v.push_back(a*a);
        }
    }
    int t; scanf("%d",&t);
    while(t--){
        ll N; scanf("%lld",&N);
        ll ans=upper_bound(v.begin(),v.end(),2*N-1)-v.begin();
        printf("%lld\n",ans);
    }
    return 0;
}