慣れてきた
・AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019: D - Nearest Card Game 500 トケタ
考えやすさのため、B[N-i+1]=A[i]として降順で考える。
高橋君抜きにすると、青木君の取るカードの場所は連結にゾーンで増えていく。なので、高橋君とこのゲームをやると大きい方から見てt, t, t, t, a, a, a, a, t, a, t, a, ....みたいな取り方になる。 最初にtがi個続くような取り方をgroup iとすると、group i より小さいところに属するかどうかはx>=(B[i+1]+B[2i+1])/2という判定ができる。groupは(N+1)/2まである。
あとはgroup i のときの和を求め、各X[j]に対し、どのグループに属するかをにぶたんするとよい。和はずらして求めることでO(N)、各クエリでO(log N)で判定できるので、全部でO(N+Qlog N)でできた！
取られるカードの挙動を考察したらなんとかこの解法にたどり着けたけど、結構むずかった...実装も、一直線ではあるが細かい偶奇を意識しないといけなくてそれなりに面倒だった。でもこれを解けたのはいい経験になったなぁ。計算量的にO(Qlog N)とかO(N log Q)とかだといいな、とか思うけど、結局は考察ありきなんだなぁ。
解説もちらっと見たが、解説でiとjに分けてるのは意味がない気がする...
・ARC 082: F - Sandglass 700 トケタ
記号のかぶりを防ぐため、ひっくり返す時刻をR[i]と大文字にしておく。
初期砂aをfixすると、各時刻でAにある砂の量がダイアグラムの要領でグラフ化できる。すべてのaについてそのグラフを書くと、Aにある砂の最大最小が定まっているため、aが端っこの方ではつぶれて同じグラフになってしまう。そこで、R[i]秒後において、グラフがつぶれていない区間(初期砂の量で表示)[l[i], r[i]], およびその両端での砂の量ls[i], rs[i]を前計算しておく。これは前の結果利用でO(N)でできる。変遷自体はやや面倒だが計算は簡単にできる。
すると、与えられた (t, a) について、tが区間[r[i], r[i+1]]にあるとして、上の情報があれば初期砂aのときの値が確定できる。
tがどの区間にあるかはにぶたんでlog Kでわかる (ソートされていることを用いれば、先に時間を取得して全体でO(N+Q+K)でできるかも)。よって全体でO(Nlog K)(or O(N+Q+K)??)でできる。
状況が把握しやすいため解きやすかったが、実装は大変だった。解説とだいたい同じ方針だが、考える過程が微妙に気がする。t変数ではなく、a変数で見るというのが大事か。競プロでは「ある変数で固定する」というのが思考の基本だということに最近気が付きました。「ある変数で固定＋その変数で全探索」のコンボが強すぎる。
・ARC 091: E - LISDL 700 トケタ
N>A*BならばA+1個の増加列かB+1個の減少列が存在します(鳩ノ巣原理)。なのでA+B-1<=N<=A*Bだとよくて、適当にブロックわけして実装しよう。実装ややだるいけど、おいしい構成ゲーでした。
・KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019: D - Double Landscape 500 トケタ
A's, B'sに同じのがあるとだめ。ソートしておいて、大きい方から置ける場所を決めていけばよい。iより大まで決めた時、置ける範囲は確定していて、iが置ける場所の数はA'sにあるかないかB'sにあるかないかの4択できまる。頑張ってシミュレートしよう。謎のWAが生えてキレそうだった(存在しないインデックスの配列を読み込んだっぽい...)。
・全国統一プログラミング王決定戦本戦: D - Deforestation 500 トケタ
この前のイベントソートってこれか！1つの竹に注目すると、そこから切り取られる竹の長さの総和は、最後に切り取った時間と一致する。よって、「与えられた区間に対し時間を投げて最大に更新する」というクエリを高速で行えればよく、これはイベントソートでできる。setで切り取られる時間を管理、priority_queueで「L[i]番目にT[i]を追加」「R[i]+1」番目にT[i]を削除」というイベントを管理して、竹の番号の昇順で見ていくとよい。
区間系クエリなので遅延セグ木が必要そうだが、最後にまとめて最大の長さを見るだけならイベントソートでできる。いいテクニックだなぁ～
・ARC 068: E - Snuke Line 復習
昔解けなくて解説見たやつの復習。区間がたくさんあって、各dに対しdの倍数を含む区間の個数を出す。区間の種類じゃなくて、dの倍数ののべの出現回数なら、いもす法とかでで被る区間の個数をあらかじめ持っておいて、逆数和全探索でできる。しかし種類だと困る。
そこで大事な考察。区間の長さがd以上だと絶対に止まるので探索しなくてよい。d未満だと0回か1回とまる。よって、dを見るときに区間の長さdのものについて区間加算して、逆数和全探索するとよい。区間加算は都度やんないといけないが、遅延セグ木でlog Mでできる。
かかる計算量は区間の長さによるソートO(Nlog N), 区間加算と逆数全探索でO(M*logN*logM). よって間に合う。
典型的な議論を考察を用いてうまく合わせるので好き。こういうのコンテストで通せたらテンション高いなぁ。
・AGC 004: C - AND Grid トケタ
構成ゲー。連結な赤の板と連結な青の板を重ねて紫の場所ができ、紫の位置が与えられる。このときもとの赤青の板を復元せよ、というもの。赤と青が紫でない位置で重なってはいけない、という制約がある。
「上下の行に赤をべたっと塗って、それをつなげる」という方針でできた。つなげるときは、端の列から見ていって紫マスがあれば塗って1列飛ばす(隣り合う列は紫マス以外赤く塗らない)という風にする。そして赤いが紫でないマスをすべて青とする。
つくり方から赤板が連結なのはよい。列で塗らなくとも、隣の列を列で塗っていればつながる。また青板については「盤面から単独赤マスだけ切り取る」と考えれば明らかに連結である。
思いつきさえすればやさしい。今回は思いついたので体感難易度400くらい。AGC700は難易度よくわからんね。
・ARC 081: F - Flip and Rectangles 700 疲れた
考察はできて、最大長方形のアルゴリズムまでは帰着できたが、そこからが大変だった...とりあえず、そのアルゴリズムは何とか習得したのでよしとしよう...
・ARC 094: E - Tozan and Gezan 700 トケタ
同じ列なら0. そうでないなら、A[i]>B[i]なるiの中でのB[i]の最小をdとするとsum-dとなる。先手はその最小dを取る組以外を触りつづけることでsum-d手稼げるし、後手もその組以外を触り続けることでsum-d手以下にはできる。
数オリCじゃーん。もうちょっと複雑になるかと思ったがそうでもなかった。
・ARC 094: F - Normalization 700 トケタ
a, b, cは0, 1, 2で扱う。
操作で列の総和のmod3は変化しない。一方xxyという並びがあるとxxy ,xyy型でmod3が同じものはすべて作れる。そうなると、
1) 全部同じなら変化しないので1通り
2) 1) 以外で、同じ数字が隣り合う場所があれば、mod3で一致して同じ数字が隣り合う場所のある列全部が作れる。
3) 同じ数字が隣り合う場所が無ければ、2)のものと自分自身が作れる。
となる。dp[N][i]で、総和mod3が i で同じ数字が隣り合う場所が無い数列の個数とすると、last digitで場合分けしてカウントできる。だいたい2べきくらいなんだけど0mod3のときずれるので一応計算しておくとよい(2べき+2or-1なんかな)。これを余事象として答えが出せる。N<=3だといろいろ面倒なので分けておくと吉。
mod3の不変量が分かればなんとかなった。ちょっと面倒だったけど...
・ARC 057: E - キャンディーとN人の子供 / Children and Candies 800 トケナイ...
だからさぁ...明示的な公式求めようとするの無駄だからやめませんか？完全に無駄というわけじゃないけど、大事なのは「うまく遷移を求めること」だからさぁ、もっとそれ意識しような、はぁ...
条件の言いかえは大事だが、明示的な公式はいらないからなまじで。そのへんのバランス意識しような。
・キーエンス プログラミング コンテスト 2019 E - Connecting Cities 600 トケナイ
いやむずくないですかこれ。MSTなのはよいが、いらない辺を減らす発想にいかなかったのはよくない。3点ループのうち最大コストなのは落とせます。
しかしそれを思いついたとして、ちゃんと削れたかは謎。「自分より右にあってかつ規模が小さいもののうちコスト最小のものを残す」をどうやったら思いつけるのか。解答の不等式が全然見えないんですがそれは。容易に示せても気付けないと意味ないんだよなぁ...どうやったら思いつくんだろう...
・キーエンス プログラミング コンテスト 2019 F - Paper Cutting 900 トケナイ
ぐぬぬ...こういうのトケナイと強みが活かせないのでは？
破片の個数はxかyかだけにしかよらないやんけ、となってxとyの個数をfixしたらどうかとか思ったけど全然だめだった。オーダーの時点で気付くべきだったかもしれん。
答えは期待値でした、おしまい。これあるんよなたまに。やめてくれ～答えの総数を出すとき、ランダムにして期待値にするというのはたまにやるので注意。左上が(i,j)の長方形の個数というのも頭いいな～もうだめだ...
・AtCoder Regular Contest 099 E - Independence 700 トケタ
条件は「補グラフが二部グラフ」というもの。二部グラフで各グループの頂点数がa<bのとき、aとbが近い方がうれしい。
二部グラフ判定はできる。あとは各連結成分で頂点数をカウントして、うまく分けてできる頂点数の内N/2に近いものをみるとよい。これもDPでできる。Nが小さいので愚直な実装でできる。
すぐ言い換えができてうまく解けたが、実装に無限に時間がかかった...10分くらいでさばきたいなあ...
・AtCoder Regular Contest 064 E - Cosmic Rays 600 トケタ
バリアを頂点と思うと距離について最小経路問題なので、ダイクストラするとよい。簡単だったいぇーい。どーでもいいけど始点終点も半径0のバリア(頂点)とみなしたら実装楽だった。一応「バリア間の移動は最短距離で行くのが最適」という考察があってのこの方針なので注意。
・Atcoder Grand Contest 001 B - Mysterious Light 500 トケタ
左下を直角と思うと、長方形から正方形をポコポコ取っていく互除法っぽくなる。
互除法のアルゴリズムで、正方形を取るごとに長さをカウントする(同じ長さの正方形は一気に足す)と、互除法するくらいの計算量で解ける。おいしい。
・Atcoder Grand Contest 003 C - BBuBBBlesort! 600 トケタ
隣り同士入れ替えとひとつ飛ばし入れ替えを行ってソートする。隣同士入れ替えの回数の最小は？という問題。
ひとつ飛ばし入れ替えは何回使ってもいいので、順番の偶奇さえ一致されればよい。イメージは順番の偶奇を表すoxの文字列をoxox...oxに変えたい(oが偶数)。初期列で奇数番目にあるoの個数をdとすると、初期列で偶数番目にあるxの個数もdで、後ろから考えて隣り合うoxをd回入れ替えると、あとはひとつ飛ばし入れ替えだけで実現できる。なので、最初の順番を保持してソートして、ソート後とで順番の偶奇が異なるものをカウントし、2で割ったものが答え。実装もこれくらいならできる(mapなんかなぁ、pariにしてsetつかっちゃった)。偶奇注目するだけでできた。よきよき。
・Atcoder Regular Contest 102 D - All Your Paths are Different Lengths 700 トケタ
構成ゲー。Lが2べきだと始点から{0, 1}, {0, 2}, {0, 4}, {0, 8}, ...とつなげていけばよい。一般の場合も途中ショートカットルートを開通させることでできる。簡単やった。
・Atcoder Regular Contest 073 D - joisino's travel 400 トケタ
ワーシャルフロイド＆bitDP. 集合を表すbitDPのときは、最初にbitでループを回そうね！(そうするとうまくループが回る)
・Atcoder Regular Contest 080 D - Recording 400 トケタ
区間がたくさんあって、いくつかの数直線に重ならないようにぺたぺた貼る。最小何本いる？という問題。前から貪欲に取れば、重なっている数のmax分だけあれば足りる。重なりの個数はいもす法でカウント可能。
チャンネルの概念いる？とか思ったが、実は罠があって、同じチャンネルで終了とともにすぐ始まるような2番組は続けて録画できる。なのでそういった番組をくっつける必要がある。チャンネルごとにいもす法でカウントしておけば問題ない。
・CODE FESTIVAL 2017 Final D - Zabuton 700 トケナイ
ぐぬぬ、これは自力で解けたかもしれない...
適当に並べたとき、置けなかった人は後ろに回しても問題ない。なので連続で座布団を置ける長さの最大を求めたい。人1からkまで連続で置けたとすると、P_1+...+P_i<=H_{i+1}が成り立つ。ここで隣り合う人i, i+1についての条件を見ると、S=P_1+...+P_{i-1}とおいて、S<=H_i かつ S+P_i<=H_{i+1}という条件になり、並びをi+1, iに変えるとS<=H_iかつS<=H_{i+1} かつ S+P_{i+1}<=H_i となる。ここで、i, i+1になんらかの制約があったとき片方から片方が言えないかを考えると、差を取ってH_{i+1}+P_{i+1}<=H_i+P_i ならばスワップしても成立する。すなわち、H+Pが小さい順に並べ替えても成立する。
よって、H+Pが単調増加な列だけチェックすればよく、そのためには、最初からH+Pの小さい順に並べ、前から取るか取らないかを見ていくとよい。「できるならなるだけ座布団の和を減らして次の人に渡したい」という議論により、有名なオーバーキルDPでできる。dp[i][j]をi人目まで見てj人とる時の最小値として、不可能な場所をINFとすると、最後まで更新してdp[N][j]がINF未満の最大のjが答えとなる。
いやーいい問題だなぁ。はじまりは全探索、そのうち調べたいものを絞り、考察により適切に順序を入れて、オーバーキルDP. 典型議論をうまく組み合わせて倒せる。自力で解けたら気持ちいいだろうなー。
・ABC 116: D ? Various Sushi 400 トケナイ
いやむずくね？種類数をどう扱っていいのか分からんすぎた。
同じネタだったらおいしい方から食べるべきで、順に食べるとき種類数が増えるのは一番最初のネタを食べるときのみ。よって各種類で一番おいしいネタだけ特別扱いして、それを何個食べるか(=何種類食べるか)で場合分けすればよい。この計算だと本来実現しない食べ方もあるが、実現する食べ方よりも値が小さいので問題ない。
順に食べていくというところから、満足度がどう変化するかの差分を考えれば、この解法を思いつくかもしれない。いもす法じゃないけどlocalに差分を取るのは大事かもなぁ。地味に考えにくいのは種類の概念を捨てるという点で、そのへんは柔軟な発想が大事か。
・Mujin Programming Challenge 2018: D - うほょじご 400 トケタ
数論的な議論は忘れよう！ペアを頂点としてDFSすればOK. 遷移で逆順に辺を引き、(0,0) で終了扱いしておいて、(0,0) 始点で到達できるかDFS, 到達できない点をカウントすればよい。ただし999までちゃんとペアを用意しておこう。頭を使わずできるときに、頭を使わないの大事。
