だらだら競プロ適当解説：AtCoder Beginner Contest 004
AtCoder Beginner Contestの第４回。
ぼちぼちやってく。
配信中になんやかんやいっていたが、
Ｄ問題は初めの想定通りだったので勘が鈍っていなくてよかったと感じた次第である。
【追記】D問題の想定解法を追記しました。
総評
今回のＣ問題は部分点形式であり、前回までのＡＢＣまでの単純早解きで順位に差をつける形式からＣでもふるいにかける形式に変わった。
Ｃは気が付けば大したことではないが、これまでの組めれば解けると異なり、競プロをやるなら計算量も気を付けるべしという出題者の意図を感じた。
D問題は典型に近い方法で解くことができるが、他の方法でも解けるため競プロ固有問題とはいいがたく、比較的万民向けであると言えた。
A - 流行
借りた金額を二倍にして返す。
略解
cin >> N;
cout << N*2 << endl;
ポイント
これまでのＡ問題で最も簡単かもしれない。
特に整形の必要もなく単純に２倍するだけである。
B - 回転
配列がやってくるのでそれを１８０度回転させた配列を出力する。
略解
string s = ""; for (int i = 0; i < 4*4; i++) { string tmp; cin >> tmp; s += tmp; } for (int i = 0; i < s.size(); i++) { cout << s.at(s.size() - i - 1); if (i % 4 == 3) { cout << endl; } else { cout << " "; } }
ポイント
入力順と逆順に出力すればいいことに気が付いたらあとはうまく整えればよい。
今回はstringに格納し、size()でforを回したが、もちろんvectorに格納してrbegin()等で後ろからforを回してもよい。
ただし、rbegin()を使う場合は改行判断がしづらくなるので、入力の際に改行も格納しておくというのがよさそうである。
C - 入れ替え
カードをN回入れ替えたときのカードの並び順を教えてください。
略解
string s = "123456"; int N; cin >> N; // forでグルングルンといても部分点はいける. //for (int i = 0; i < N; i++) //{ // char tmp = s.at(i % 5); // s.at(i % 5) = s.at(i % 5 + 1); // s.at(i % 5 + 1) = tmp; //} //cout << s << endl; // よく考えると規則性をもっている事が分かる. // ちょうど30で一周することが分かるので、30まで計算すればいい. int count = N % 30; for (int i = 0; i < count; i++) { char tmp = s.at(i % 5); s.at(i % 5) = s.at(i % 5 + 1); s.at(i % 5 + 1) = tmp; } cout << s << endl; // 本当はちゃんと考えれば一発で求まるんだけど、面倒よね. // その場合は以下の２点を考えれば解ける. // １：5で割った値でどの数字をいま動かしているか考える. // たとえば0なら1を動かしている最中(初期123456)だし // 3なら4を動かしている最中(初期456123)のはずである. // ２：5で割った余りでいま移動させている数字がどの位置なのかを考える. // 上記の初期値から何回先頭の数字を右にずらしたかが余りで分かるはずである. return 0;
ポイント
まず部分点を取ることを考えてみて、N回愚直に移動させるコードが書けることがひとまずのポイントだろう。
スワップ系の問題は競プロに限らずいろいろな場面で遭遇するため比較的知られている内容かと思われる。
文が長く、読むのが面倒であるが、mod(要するに余り)をつかって交換するという話が記載されているのでそれに沿って実装すればよい。
ここまでで部分点の獲得が可能である。
次のポイントはNが大きくなった時でも計算時間が足りる実装である。
計算時間の短縮には《根本的なアルゴリズムの改善》、《同じ動作の繰り返しの削減》、《枝刈り》等のやや誤魔化しに近い方法などがある。
今回は《同じ動作の繰り返しの削減》と《根本的なアルゴリズムの改善》のどちらも適用できるが、部分点からの発展で考えると《同じ動作の繰り返しの削減》に気が付くというのが良いと思う。
実際にノートなどで動きを書いていくと分かるが、ちょうどN=30でカードの並び順が一周することが分かる。
そのことからNを30で割ったあまりの回数だけforを回せばすべてのNで解が求められることが分かる。
この方法がおそらく非常に楽だと思う。
コメントに記載のように《根本的なアルゴリズムの改善》も可能で、5で割った解と余りから一意に盤面が定まるのでこの方法でもよい。
この場合、そもそも部分点解法をすっ飛ばしてしまってもよい。
個人的にはABCを主軸に参戦しているのであれば、部分点解を作成したうえで、発展させてほうが良いとは思う。
D - マーブル
箱が３つあってそれぞれの箱からそれぞれの色のマーブルを重ならないように取り出した場合の最小の移動コストを求める。
配信中で始めのほうにこれは貪欲で解けると言ったものの、ぶっちゃけめんどくさくて実装せず、
その後解法を見ても貪欲で解ける旨の記載がなかったのでそんな馬鹿なと思ったのだが、やはり貪欲で解けたので貪欲解を載せる。
とはいえ探索解のほうが実装が容易くバグをしこみにくいうえ、競プロ界隈ではスタンダードなため、そちらの解法をお勧めする。
探索解はまだ記載していないが、余裕が出たら追記する予定。
略解
int R, G, B; cin >> R >> G >> B; //RとBは入れ替え可能なので、常に大きいほうをRとすればBの処理を簡略化できる. if (R < B) { int tt = R; R = B; B = tt; } // 前提 // 移動コストはk(k+1)/2のシグマkの公式で求められる. int CostSum = 0; // オフセット値. int ROffset = 0; int GOffset = 0; int BOffset = 0; // まずGを処理しないと話にならないので、Gを両サイドに伸ばしていく. // 物事を簡単にするためにひとまずRとBは存在しない体で伸ばしてしまおう. // G個なのでそれぞれ左右に(G-1)/2個移動させるのがよい. int GRightK = (G - 1) / 2; int GLeftK = (G - 1) / 2; // あまりは左右のどちらかに振る、おそらくRとGのどちらが少ないかで振ればいいだろう. // 多いほうに振るとGとのバッティングが起こりやすいので.. if (R > B) { GRightK += (G - 1) % 2; } else { GLeftK += (G - 1) % 2; } // ひとまずコスト計算. // 押し出しが生じるかどうか. if (G > 199) { // 残りとLRを再調整. int Gremain = G - 199; GRightK = 99; GLeftK = 99; // ひとまず収まった分だけのコストを計算. CostSum += GRightK*(GRightK + 1) / 2 + GLeftK*(GLeftK + 1) / 2; // 残りを貪欲にLRに分ける. for (int i = 0; i < Gremain; i++) { //接しているはずなのでオフセットコスト＋移動コスト. // 左R. int tmpCostL = R + GLeftK + 1; // 右B. int tmpCostR = B + GRightK + 1; // コストは小さいほうがいい. if (tmpCostL < tmpCostR) { CostSum += tmpCostL; GLeftK++; ROffset++; } else { CostSum += tmpCostR; GRightK++; BOffset++; } } } else { // 押し出しがなければコスト計算しておしまい. CostSum += GRightK*(GRightK + 1) / 2 + GLeftK*(GLeftK + 1) / 2; } // Gの貪欲コスト計算終了. // Rの処理. int RRightK = 0; int RLeftK = 0; int RCost = 0; if (ROffset > 0) { // オフセットがかかっていたら // Gと均衡がとれているはずなので左にだけおく. RLeftK = R - 1; CostSum += RRightK*(RRightK + 1) / 2 + RLeftK*(RLeftK + 1) / 2; } else { // LRに分ける. for (int i = 0; i < R - 1; i++) { // 左空き. int tmpCostL = RLeftK + 1; // 右はGOffsetがいるかも. int tmpCostR = RRightK + 1; // 右の追加処理. { // 99個ならGOffsetが必要. if (RRightK >= 99) { tmpCostR += G; } // 緑をはじく. else if (RRightK + GLeftK >= 99) { tmpCostR += (GRightK + 1) - GLeftK; } // さらにBを押し出しているならそのコストも. if (G + RRightK >= 199) { tmpCostR += B; } } // コストは小さいほうがいい. if (tmpCostL < tmpCostR) { CostSum += tmpCostL; RLeftK++; } else { if (RRightK >= 99) { GOffset++; } else if (RRightK + GLeftK >= 99) { GRightK++; GLeftK--; } if (G + RRightK >= 199) { BOffset++; } CostSum += tmpCostR; RRightK++; } } } // 同様にBもやるよ.
ポイント
ここではあくまで貪欲解法でいく場合のポイントである。
部分点解法はそれぞれたかだか40個であるため貪欲解で求まることに気が付けばよい。
40個であれば左右に20個程度ずつ置くだけなので、それぞれの色で重なることはないため、ほとんど何のアルゴリズム的要素もない。
数学的に必要なのは、左右に置かれたときのコストの計算の仕方である。
コストは箱から右に1個置くなら1、2個置くなら1+2となってN個置くなら1+2+…+Nである。
これはいわゆるΣkというやつで高校ぐらいで習うのであるが、Σk=k(k+1)/2である。
これが分かれば左にkL個、右にkR個置いた時のコストが一瞬で求まるのである。
最小値は箱から近ければ近いほど小コストのはずなので左と右の数が拮抗するように配置すればよい。
上記を踏まえたうえで満点解法についてはその他の洞察が必要である。
私は直感で貪欲で解けるよって言ったのであるが、どういうことか説明すると以下の３点に気づいたためである。
１：マーブルが接さない場合は貪欲解が最適解であるということ(部分点解法からも分かる)
２：２種類のマーブルが接するとき相手を弾き飛ばすコストと自分が弾かれるコストが拮抗した時が最小コストである
３：連続的であり、局所解に陥ることがない
１はおそらく即座にわかる。
２は最小コストを考えると右に置くコストと左に置くコストが拮抗した時にお互いの境界が定まるということはなんとなく想像できるはずである。
もちろん接していても均衡していない場合はある。両者が均衡するまでもなく置き終わった場合がそれであり、１の状態はそれの特殊な例といえる。
３は結局のところ、ボックスの右に置くか左に置くかだけであり、片方は小コストで片方は大コストな処理で常に小コストを取ればいい問題だと思えば分かる。
コストを考えればマーブルが飛んで配置されることはないので物体的にも連続であるし、
すべてが接している場合はすべてのマーブルを配置した後にまるごと左か右かのコストが低くなる方向にずらし続ける問題だと思えば連続的にコストが改善されるという局所解のない問題であることが分かる。
さて貪欲で解けそうだと思ったうえで、どのように組んでもいいのであるが、個人的には以下のような方針を取った。
１：ボックスの左にkL個、右にkR個置いたという表現を取る
２：ボックスの位置より奥に弾かれた場合、全マーブル分オフセットされたという表現にする
上記のオフセット表現をするといい点は、コストの計算がΣkという大前提を崩さずに済むという点である。
これは計算量をより削減するのに効果的である。(貪欲解なうえで削減することにそこまで意味があるのかは置いておいて)
またRやBがオフセットされた場合はオフセットを戻すコストより、押し出しのコストのほうが安いことが分かっているので、それ以降の計算処理は必要なくなる。
他のポイントとしては押し出し処理を少なくするためにGから置く点や、押し戻し処理が少なくなるようにRとBの多いほうから置く点だろう。
コスト計算や配置状態と押し出しを考えると実装が複雑になりがちなため、早解きが求められる競プロの解法としてはおススメされない。
私が元ゲームライブラリ屋でありランタイム速度やメモリを気にする立場上組んだものの、正直なところコンテストのためだけなら脳死で探索解を書いた方がよい。
その場合、部分点が何も利いてこないので頭を切り替える必要が出てくるが、探索解が思いつくならおそらく初めから部分点はすっ飛ばしてしまうだろう。
そういう意味では部分点は逆に罠みたいに思えなくもない。
探索解については後日余裕ができたら書く予定である。
【追記】D - マーブル 想定解法
略解
#define INF (500000) // グローバルにしちゃうんですか先生！ int R, G, B; // [どこの場所の操作か][マーブルの残りの個数] // 上記の２つだけで盤面を表現可能. int memo[2001][300 * 3 + 1]; /// <summary> /// 再帰の部分 /// </summary> /// <param name="pos">どの場所の操作か /// 内部でposは1000のオフセット</param> /// <param name="remain">残りのマーブルの数</param> /// <returns>コスト</returns> int calc(int pos, int remain) { // R+G+B個以上は置けないので. if (remain == R + G + B) { return 0; } // ここから先の区間は探索の価値もないはず. if (pos < 1) { //置ききっていないのは論外. if (remain != R + G + B) { return 300 * 1000;//むっちゃ高い点. } else { return 0; } } // すでにメモがありますか？ if (memo[pos][remain] != INF) { return memo[pos][remain]; } //置いてこれになった時と、置かずにこれになった時の２択. // 置いてなった場合. // ここでコストを加算する. // いま置こうとしているのはRGBのどれか... int addcost; if (remain < B) { //B addcost = abs((pos - 1000) - 100); } else if (remain < B + G) { // G addcost = abs((pos - 1000) - 0); } else { //R addcost = abs((pos - 1000) - (-100)); } // 置けるということは前回ではremain + 1個だけ余っていたはず. int costP = calc(pos - 1, remain + 1) + addcost; // 置かないでなった場合は前回と残り数は同じはず. int costNP = calc(pos - 1, remain); // より小さいほうを残す. memo[pos][remain] = min(costP, costNP); return memo[pos][remain]; } int main(){ cin >> R >> G >> B; for (int i = 0; i < 2001; i++) { for (int j = 0; j < 901; j++) { memo[i][j] = INF; } } //メモ化再帰で解く. //左から置いていって、1000の位置の時に残り0個というイメージ. int cost = calc(2000, 0);//内部でposは1000のオフセット. cout << cost << endl; return 0; }
ポイント
本家の解説に合った形でコード化したもの。
メモ化再帰が利用可能かどうかの判断は個人的にもいまいちな部分がある。
一般的な再帰表現であれば大抵のものは適用可能だと思う。
ここで重要なのは「再帰表現」できることであって、「再帰探索」できることではない。
要するに再帰全探索できても、すべての情報が出そろった状態でなければスコアリングできないという場合は適用できない。
再帰関数によって得られるものが「盤面」ではなく、実際に求めたい「スコア」になるものと考えればよさそうだ。
今回の場合、ある地点にあるマーブルを置くと決めた時点でスコアが確定するため利用できたが、
例えばこれが「同色が連続する個数でスコアが変わる」というようなことになると、全探索は可能だがメモ化再帰はできない。(厳密にはこの形ではできないになる気がする)
実装自体は比較的簡単だ。
終了条件となる引数を与えた再帰関数をメイン関数内で実行すればよい。
再帰関数自体は上記のコードにあるように、置いて今の状態になったものと置かずに今の状態になったものの両関数を呼び出し、より低いコストのものを選べばよい。
F(場所,残りのマーブル数)としたとき、以下のような形の再帰関数になる。
F( 100, 20 ) = Min( F( 99, 21 ) + 置く加算コスト, F( 99, 20 ) + 置かない加算コスト )
（置かない加算コストは0だが）
メモ化再帰は競プロにおいては頻出なので参加していればいずれどういった場合に適用可能かどうか慣れてくるような気がする。
