だらだら競プロ適当解説：AtCoder Beginner Contest 003
AtCoder Beginner Contestの第３回。
なんやかんやで緩く続いている。継続は力らしいし、やらないよりはやったほうが力が付くだろう。
記事を書いてよかったと思うのは、いつもなら解答を見て理解したらそれでいいやみたいな流れだったが、実装するところまでやっているので、予期せず詰まる部分に気が付けたことである。
総評
AからCは典型的なABC問題といっていいだろう。ABC1やABC2と比べて必要な知識はそれほど変わりがない。
D問題は競プロ特有の問題である。競プロをやろうという人にとってはこなすべき内容だが、単純にアルゴリズムの勉強をしようとする人にとっては競プロバイバイの原因になりうるおおよそ固有問題である。知らないと解けないの節が強いので、少し考えて分からなかったら解答を見るのがよいかもしれない。
A - AtCoder社の給料
サイコロで給料が決まるので面数が定まったときの期待値を求める問題。
略解
for (int i = 0; i < N; i++) { sum += 10000 * (i + 1); } cout << fixed << sum / N << endl;
ポイント
一般的な期待値の計算方法が分かれば問題ない。
これについても問題文に丁寧に記載されているので参考にすれば解けないことはないだろう。
B - AtCoderトランプ
ワイルドカードを含む２つの文字列がやってくるのでそれを一致させれるか確認する問題。
略解
string atcoder = "atcoder@";//@もまぜると処理が楽. for (int i = 0; i < S.size(); i++) { if (S.at(i) != T.at(i))//２つの文字列を前から比較していく. { // @かそうでないかで分ける. if (T.at(i) != '@' && S.at(i) != '@') { isWin = false; break; } if (T.at(i) == '@') { if (atcoder.find(S.at(i)) == std::string::npos) { isWin = false; break; } } else if (S.at(i) == '@') { if (atcoder.find(T.at(i)) == std::string::npos) { isWin = false; break; } } } }
C - AtCoderプログラミング講座
動画をいくつか見るので、もっともレートが高くなるように順番を選んでみてください。
略解
cin >> N >> K; for (int i = 0; i < N; i++) { cin >> R[i]; } sort(R, R + N); for (int i = N - K; i < N; i++) { ret = (ret + R[i]) / 2.0f; } cout << fixed << ret << endl;
ポイント
発想さえ分かれば比較的素直に解ける問題。
K個選ぶ際には直感的に高いレートのものを選んだほうがよいことは分かる。
それが分かれば、その高レートグループをどの順で見るのがいいのかを考えればよい。
適当に小さなケースで試してみるというのが良いと思うが、式を書くことでも分かる。
ABCの順に動画を見た場合次のようになる。
(((０＋A) / 2＋B) / 2)＋C) / 2=A / 2^3 + B / 2^2 + C / 2
先に見る方が最終的なスコアに対する影響が小さくなることが確認できる。
このことから、高レートのK個の中でもっとも小さいレートのものから視聴すればよい。
D - AtCoder社の冬
部屋があり、区切られた区画とサーバやデスクの数が与えられる。
それが部屋内に何パターンできるかを求める問題。
競プロ特有の1000000007の余りで解を出す。
略解
ll CombiMemo[901][901]; /// <summary> /// パスカルの三角形でメモしちゃう. /// </summary> void MemoCombi() { for (int i = 0; i < 901; i++) { for (int j = 0; j < i + 1; j++) { // はしは１ね. if (j == 0 || j == i) { CombiMemo[i][j] = 1; } else { // うえの２つを足します. CombiMemo[i][j] = (CombiMemo[i - 1][j - 1] + CombiMemo[i - 1][j]) % 1000000007; } } } } int main(){ int R, C, X, Y, D, L; cin >> R >> C; cin >> X >> Y; cin >> D >> L; // 面積からいくつ区画が作れるか考える. // 部屋の縦がRに対してYなのでY方向にはR-Y+1パターンあるはず. int Ypat = C - Y + 1; // X方向も同様. int Xpat = R - X + 1; // コンビネーション数. MemoCombi(); int ans = (Ypat * Xpat * CombiMemo[D+L][D]) % 1000000007; cout << ans << endl; return 0; }
ポイント
まず問題を２つに分割して整理するところからはじめる。
1つは部屋にXY領域の区画をいくつ作れるか。
もう1つはサーバとデスクを区画内にどう配置するかである。
これらは独立した問題であって、両方を掛け算することですべての組み合わせが得られるということに着目する。
（サーバとデスクのどう配置されていようが、XY領域の区画数にはなんら影響はないのである）
部屋にいくつ区画を作れるかは実際に書いてもらえば分かりやすいが、まず部屋の一番左上に区画を作ってそれを下にずらしたり、右にずらしたりするイメージである。
下にずらせる個数と右にずらせる個数をかければ全通りが出せることが分かる。
次にサーバとデスクをどう配置するかだが、この組み合わせはコンビネーションというもので表すことができる。
だいたい高校１年くらいで習う気がするが、区別のつかないものの組み合わせを出すのがコンビネーションで、区別のつくものの組み合わせがパーミュテーションくらいの雑な認識でいい。
ここでは個々のサーバとデスクは区別がつかないのでコンビネーションを用いる。
そこで私ははじめ以下のようにコンビネーションを書いた。
ll Combination(int n, int m) { ll ret = 1; for (int i = 0; i < m; i++) { ret *= n - i; } for (int i = 0; i < m; i++) { ret /= i + 1; } return ret; }
これ自体は比較的王道なコンビネーションの関数なのだが、如何せん数が大きくオーバーフローする。
競プロ特有の余りを使う問題だが、余りの計算は足し算や引き算、掛け算では逐一とっても問題ないが、割り算では特殊な操作が必要になる。
参考：「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
この場合、割り算が含まれるので逆元というのを求めないといけない。
これをやってもいいし、サイトからコピってきてもよいが、正直おそらくこれはABCの範囲ではないので、解法にのっとってコンビネーションの求め方を変えることで対応した。
いわゆるパスカルの三角形の方法でコンビネーションを計算する。
これは上から順に計算しなければいけないので、計算時間がかかるが、今回は雑に計算しても９００＊４５０程度でコンビネーションが計算できることからこの手法で事足りる。
ほかにもコンビネーションと余りの計算はどうやら競プロ頻出らしく、いろいろ手法があるようである。
参考：競プロでよく使う二項係数(nCk)を素数(p)で割った余りの計算と逆元のまとめ | アルゴリズムロジック
101点解法については気が向いたら解いてみようかな。
少しめんどくさそうなのでひとまずは保留する。
