がんばろう
・ARC 087: D – FT Robot 500
x, y方向に分けて進み方を集計し、DPするとよい。計算量O(N^2)でできる。bool値でdpするときはbitsetを使う習慣ができた。
・ARC 099: D – Snuke Numbers 500
算数ゲー。小さい方で実験すると、左から9が続くものが候補になりそうと分かる。そこで左から9がi個あってそれ以上がSの数"S"99...9を考えると、数式をいろいろいじってSの候補がiごとに分かる。計算によると、i=0だとSは1から9, i=1...9だとSは1から10i-1, i=10, ..., 14だとSは1から10i-11となる。個数はそんなにないので、全列挙するとよい。
本来真面目に証明すべきだが、めんどうなので軽くラマヌジャンしてしまった。まあいいか(よくない)。
・Tenka1 Programmer Contest 2018: D – Crossing 500
明らかにNが三角数なのが必要。k個集合があるなら集合2個の取り出し方がk(k-1)/2通り、一方N個の数字はこの取り出し方にちょうど1回顔を出すので、N=k(k-1)/2. あとは各i<jに対応する数字を放りこめばよい。ナメてる？
・Tenka1 Programmer Contest 2017: D – IntegerotS 500
いわゆる桁DPの基本形。ある数aがK以下の数に含まれる(bit的な意味で)かどうかは、Kを分解してチェックするとよく、Kで1の立つ桁iについて、桁がiより大でKと同じ、iは0, i未満は1となるような数K_iに分解するとよい。たとえばK=101101なら011111, 100111, 101011, 101100, これとKそのものでチェックするとよい。
bitorを使うような問題でたまーに見かける。覚えておこう。
・第5回 ドワンゴからの挑戦状 本選: A – Taro vs. Jiro 500
Kはみせかけ。2回分の移動は無視できる(まねっこ戦略による)。DFSで隣に青があるか(or赤があるか)をカウントするDP(メモ化再帰？)を2回ないし1回するとよい。DFSへの恐怖心はだいぶ消えたなぁ。
・CODE FESTIVAL 2018 予選B: C – Special Cake for CODE FESTIVAL 500
だいたい1/5に置ける。Xペントミノを並べるイメージで、その中心をXとするとよい。条件としては(i+2j)%5=0と書ける。ただしこれだと端っこで危ういので、まだ条件をみたしていない場所を探してXを置く。探すときは迷路探索的にvectorを置いておくとやりやすいゾ。パズルだった。
・みんなのプロコン 本選 (オープンコンテスト): A – YahooYahooYahoo 400
めんどくさそうだったので後回しだったやつだが、慣れにより普通に解けた。
i 文字目まで見るというキーをもったDPだけど、遷移させるためにyahooyahooyahみたいな「準yahoo文字列」を作るためのminも持っておく必要がある。k文字付け加えるというキーを持っておく。
遷移を書くのがやや面倒。k=0 を例にすると、
i 文字目を捨てるもの
i-1 文字目まででyahoまで作り i 文字目でoにするもの
i-1 文字目まででyahまで作り i 文字目でooにするもの
i-1 文字目まででyaまで作り i 文字目でhooにするもの
i-1 文字目まででyまで作り i 文字目でahooにするもの
を表し min を取るとよい。S の i 文字目により係数は微妙に変わる。Yahooをstringとして持っておけば楽に書けるかもだけど、添え字の管理がたるかったので愚直に書く＆コピペでやった。
遷移をちゃんと考えればそんなに面倒じゃなかった。成長を感じる (?)
元ネタは編集距離というらしい。二つの文字列 S, T があり、S に削除挿入置換をして T にするための最小回数が編集距離の定義で、これもDPでできる。具体的には S, T の i, j 文字目まで見た時の距離を考えて遷移を施すとよい。遷移は
削除：dp[i][j]=dp[i-1][j]+1
挿入：dp[i][j]=dp[i][j-1]+1
置換：dp[i][j]=dp[i-1][j-1]+cost, constは文字が一致なら0, 不一致なら1
となる。これを参考にすればもう少し簡単に書けたかもしれない。けどまあ、解ければいいんだよ解ければ(屑)
・みんなのプロコン 予選: C – 検索 400
問題は2つのパートに分かれていて、
-- 出したい文字列の中で検索ワードの最大を求める
-- 出したくない文字列について出さないための長さの最小を求める
の2つがある。どちらも二分探索でできます。計算量も大丈夫。
昔は二分探索の設定の仕方に苦手意識があったが、「半開区間にする」「どの区間にmax(or min)を入れるか」を意識することで苦が軽減された。いいはなしや...
・第4回 ドワンゴからの挑戦状 本選(オープン): A – アナログ時計 400
なにこれ？めんどいので新秒 (new second) を 1s = 59*11 nsで定めると、起こるすべてのことが整数で扱えるのでそうする。一応long longにしたが、intでできるかは謎。できなさそう。あとはまあ、判定が O(1) でできるんじゃないですかね...
・ARC 0830 D - Restoring Road Network 500
ワーシャルフロイドからの最小全域木かと思ったら、最小全域木じゃなかった(素)
まずワーシャルフロイド回して存在判定。そのあと各辺に関して、別の頂点を介していくコストと一致したら捨ててもよい。残した辺の和が答え。実装が楽でありがたいわぁ。でもあんまり証明考えずに書いちゃった(屑)
・AGC 005: C – Tree Restoring 700
木から数列を得ることを考える。最長のpathをもとにして考えると、できる数列の条件が分かる。pathにない点については、path上のどの頂点に接続するかを考えれば制約がある。結局、c[i] を i の個数として、c[i]>0 となる添え字の最小・最大を l, r とおくとき、
-- l = 2*r なら、c[r] = 1、r+1 < i <= lでは c[i]>=2
-- l = 2*r なら、c[r] = 2、r+1 < i <= lでは c[i]>=2
-- それ以外のパターンはない
あとはチェックしよう。パターンの不理解で2WAしました、キレそう。
・AGC 014: C – Closed Rooms 700
初手で届く場所までいって、そこから外まで最短距離でK個ずつ進めばよい。
久しぶりにBFS書いたのでとまどっちゃったよ。
・AGC 016: C – +/- Rectangle 700
小長方形で敷き詰められるならだめ。その条件は H%h ==0 AND W%w == 0.
他のパターンは「かぶり」が出るので、かぶりとそうじゃないところで値を調整するとよい。調整不足で3WAしました(呆れ)。
・AGC 016: B – Colorful Hats 700
これは本質情報ですが、数列から帽子を復元するんじゃなくて、条件を満たす帽子の方から数列を作る方を考えるといいと思います。そりゃそうだ。でも他の問題でもこういうの大事だよね。
・AGC 018: B – Sports Festival 700
全探索はもちろんダメで探索量を減らさないといけない。例1でいうと、1, 2, 3, 4, 5 全部やるとしたら 2, 5 しかしないので 1, 3, 4 は見なくてよい。また 2 が 3 個あるので、2 を残したら答えは3以上確定。なので列を前から見て一番多いのを捨てて、また一番前を見て一番多いのを捨てて、というのを繰り返せばよい。同じ数のものがあっても、捨てる順番は気にしなくてよい。これで1回の操作が O(N*M), 合計 O(M^2 * N) でできる。
なお、正当性を真面目に考えると、このアルゴリズムで捨てる順番に数列bができるが、一般に考えるケースについて、行う番号の中でb内先頭のものを考える。すると考えているアルゴリズムでその数字が先頭にあるときに判定した値以上になることが、アルゴリズムの定め方によりわかる。よってこれで正しく求まっているといえる。
「全探索から枝刈り」メソッドで、いらない操作を意識して捨てればできた。こういうのスパっととけると気持ちがいいね。
・AGC 022: C – Remainder Game 700
解くべき問題が多いので適切に固定してうまく分解していく。幸い数は大きくないのでやるべきことをちゃんとやればよさそう。
まず考察として、操作は大きい順に高々1回やればよいとわかる。操作を行う数の集合Sを固定したとき、aをbにできるかをどうやって判定するかは、各 d in Sについて i->i mod d という辺を張り、DFSすると判定できる。N個あってもできるので、これで判定問題は O(NA^2) でできる (A=50)。
当然全集合について判定するのは無理で、コストが 2 べきなことに注目すると、大きい方から入れるか入れないかを判定すればよいとわかる。桁DPのイメージ。pより大で入れるか決めたとして、pを入れるかどうかは、p-1以下をすべて入れてできるなら捨て、できないなら入れるとよい。最初にp=51で同じことをしておくと、そもそもできないパターンも判定できる。よって O(NA^3) でできた！
昔見た時めっちゃムズイと思ったけど、今見ると典型議論の寄せ集めという感じがする。グラフの遷移に帰着してDFS＋桁DP的な。しかしちゃんと典型まで分解して、個々のパーツを難なく書いて、組み上げるというところを着実にやる必要があって、そのへんの難しさはあるかもしれない。
・AGC 027: B – Garbage Collector 700
(k+1)^2をカウントするのがかったるいのでうまく計算する必要がある。
ゴミ箱がx_1, ..., x_k を取ってきて捨てるとする。移動のみのコストを考えるとすると、xの方で差分を取っているのを(k+1)^2の方の差分に変えると、a_i*x_i という係数のかかった和になり、その係数は遠いほうから 5, 5, 7, 9, ...となる。
次に移動回数 t を固定すると、どれを取るか決める＝係数を決めるときに
-- 遠い方から単調にできる、その方がお得
-- 5 の 1 個目, 5 の 2 個目, 7, 9, ...の個数はどれも k 以下で、遠い方が多い
-- その制約のもと、大きい数字はなるだけ減らした方がいい
と少しずつ改善でき、結局、各係数の個数は遠い方からk個ずつ取るのがよい。その和を計算するのにさらに x の累積和 sum をとっておく (＝2回めの差分を取る！) と、結局移動回数 t を固定したときの和は
-- 一番遠くの sum[N]*5
-- i = N-2t, N-3t, ... について sum[i]*2
-- 取る・捨てるコストの X*(N+t)
を全部足したものになる。これを 1<= t <=N について計算して比較するとよい。計算量は O(N^2) ではなく、逆数和 O(N log N) になっている。
自力で解けて気持ちいい！
なお、計算途中の答えが long long int からオーバーフローするかもなので注意。答え自体は収まるので、候補から消えたら途中で強制終了させるといいっぽい。実際の試験中なら原因不明でガチギレしてたと思う。。。
・AGC 028: C – Min Cost Cycle 700
DPでやろうにも遷移が書けなさそう...逆にいえば結構自由度があるということで、実際かなりのパターンで理想値を実現できる。2N 個の数で小さい方から N 個をマークすると、各頂点は oo, ox, xo, xx の形になっている。
このとき、oo が一個でもあると全部の o を拾え、ox だけ、xo だけのときも全部拾える。問題は ox, xo が 1 個以上あって oo, xx が無い場合で、このときは理想値を実現できない。しかし、o の中で一番でかいもの p と、x のなかで一番ちいさいもの q の位置で場合分けがおき、だいたいのパターンでは q-p の補正だけで済ませられる。p と q が同じ頂点ならまだだめで、p のひとつ下 p' と q のひとつ上 q' について、min(q-p', q'-p) で補正できる。実装は適当にペアを組んでソートすれば問題なくできます。
たまーにある「実はだいたい理想通り実現できます (貪欲？) 」パターン。愚直な全探索やDPがだめそうなら考えるとよさそう。数オリっぽくなりがちなので落ち着いて取りたいね。
解説放送ではもう少し別の視点から見ていたがだいたい同じだった。アイデアとして、「最小の最小を取っているので、全パターン考えて選べる」というを忘れないように。min(a, b)+min(c,d) = min(a+c, a+d, b+c, b+d) というアレです。たまに絶対値で abs(a-b) = max(a-b, b-a) からこれを使うときがあるよ。
・AGC 028: B – Removing Blocks 600
「総和は期待値」メソッド。略してSWKメソッド。笑えないよ！
1 番目について考えると、i 番目自身の寄与は 1 * (確率) で、その確率は i 番目までの中で i を一番最初に取る確率で 1 / i. よって全部で 1+1/2+...+1/N となる。真ん中の方についても、(右までの逆数和) + (左までの逆数和) -1 になる。累積和を取って O(N) でできるよ。
・ARC 086: D – Non-decreasing 600
N<=50 はハッタリでした。
全部正、全部負なら簡単にN-1回以内にできる。順に隣り合うものを比較して足していけば、別の不等号を邪魔せずできる。なのでN+1回くらいで全部正 or 全部負にしたいが、それは正最大を他に全部足すか、負最小を他に全部足すとよい。どっちをやるかは絶対値の大きい方で。当然 O(N) でできる。
「競プロは数学パズル」的なツイートを見たが、この問題はまあそうねという感じだった。ただDPとか考え出すとハマりそう。なので一応「操作の自由度が高い場合は、簡単に実現できるアルゴリズムがあるかも」という典型かもしれない。
・ARC 080 : E. Young Maids 800 トケナイ
辞書式なので逆から操作するのはよく、求めるアルゴリズムまで出せたが、計算量が O(N^2) から落ちずギブアップ。実は方針はよく、やりたいことをちゃんと考えれば計算量を落とせた...
やりたいのは「区間内で偶数/奇数番目の最小を出す」「区間を分割してその中で (偶数番目の) 最小を見る」というもので、前者はセグ木で、後者はpriority_queueでできる。言われてみると確かにそうだなぁ。アルゴリズムへの理解の乏しさ (というか、やりたいことの、できることへの帰着) が足りなかった。悔しかったので実装もしました。セグ木のモノイドによる汎用ライブラリがある (パクった) ので、使用に 1 分もかからないのがおいしい。今回みたいに偶数/奇数番目だとしても区間についての最小を何度も見るならセグ木がべんり。今後も使えそうなら使っていきたい。オーバーキルもありーや。
・ARC 069: E – Frequency 700
実験すると、a_iが最大の中で後ろの方から石を取っていくのが最善とわかる。あとはどうシミュレーションするか。自分はpriority_queueでやりました (いやまあソートしただけなんだけど)。解ける (計算量減らせるとは言ってない) パターンの問題。慣れないとね...
・第5回 ドワンゴからの挑戦状 予選: B – Sum AND Subarrays 400
累積和で和の集合をリストアップし、桁ごとに見るとよい。まだめんどさを感じるので桁系は苦手... なお ll で1<<k とかするときは 1ull<<k としておくといいぞ。
・COLOCON -Colopl programming contest 2018- 予選: C – すぬけそだて――ごはん―― 400
与えられた区間について、相異なる 2 数が互いに素になるような部分集合の個数を求めたい。区間の長さが高々 36 と短めなので全列挙方針でできそう。ただし全部列挙はさすがに足りない。なので「偶数は1個までしか入らない」というのを使うと、奇数の部分集合を全部列挙して、条件をみたすものと各偶数 (or なし) をぶつけてカウント、とすると足りる。計算量は h = 18 とおいてだいたい O(h^2*2^h) くらい、結構ギリでした。
制約に応じて「これでできそう」と考えるのもたまには大事。まあうまくいくことは少ないですが... でも全列挙できるなら全列挙！
・COLOCON -Colopl programming contest 2018- Final（オープンコンテスト）: B – 異世界数式 400
文字列をうまく置換する問題。実は、やるべき操作はカンマを対応する演算に変えるだけ。問題はどうやってカンマの位置まで演算を保持するかだが、それにはstackを使えばよい。演算が出てくるとともにstackに追加し、カンマが出てくればtopの要素に置き換え、括弧閉じが出てきたら捨てるとよい。カンマ以外の文字はそのまま入れよう。
なんとなく、高校時代の情報の授業を思い出した。上のは想定解どおりで、stackの使用をすぐ思いつけたのでよかった。
