AtCoder Grand Contest 029
AtCoder Grand Contest 029 (AGC029)に参加しました!
AtCoder Grand Contest 029 旧版
AtCoder Grand Contest 029 beta版
解けた問題だけ解説をしていきますー
要項
AtCoder Grand Contest 029
rated
12/15(土) 21:10 ~ 23:20 (140分)
300-600-700-800-1200-2200 (6問)
ペナルティ: 5分
方針
A早解きを行い、その後BCDを全部読む
順位表と照らし合わせながら、簡単そうなのから順に実装していけば間に合うはず!
A - Irreversible operation
問題文
問題文
個のオセロの石が一列に並んでいます。
それぞれの石の状態は長さ の文字列 によって表されており、B
のとき左から 番目の石の表面は黒色、W
のとき左から 番目の石の表面は白色となっています。
ここで、以下の操作を行うことを考えます。
- 左から 番目の石の表面が黒色、左から 番目の石の表面が白色であるような () を一つ選び、その つの石をともに裏返す。
つまり、左から 番目の石の表面が白色、左から 番目の石の表面が黒色になるようにする。
最大で何回この操作を行うことができるか求めてください。制約
B
またはW
さて、まずは実験しながら考えていきます。
まず、一番左側にあるW
は絶対にこれ以上変化しません。同様に、一番右側にあるB
も変化しませんね。
これを考えていくと、どこかでB
が左側、W
が右側になる場所があります。
これは、操作を繰り返すと必ず入れ替えることが可能です。これを証明します。
今、ある部分文字列であって、BB...BBWW...WW
となっているところがあるとします。
これは、一番左側にあるW
とB
の入れ替えをB
の文字数だけ繰り返すことで、WBB...BBWW...WW
と置くことができます。
もっと複雑にWWBBWBWBWW
とかなっていても、同様の手法でW
をB
の手前にうごかす操作を繰り返せば最終的に必ず全てのW
をB
の左側に持ち込むことができます。
では、この時の操作回数はどうなるでしょうか?
これは、あるW
について、自身の左側にあるB
全てと入れ替えるので、各W
について自身より左側にあるB
の数を数えれば良いです。
また、この時左から順にみていけば、B
が出てきたときにカウントを1個増やし、W
が出てきたら加算するというコードで済む為、計算量はです。
ちなみに、答えはBB...BBWW...WW
のときが最大で、になるため、32bitの範囲を超えることに注意しましょう。
#include<iostream> int main() { std::string S; std::cin >> S; long long ans = 0, B = 0; for (int i = 0;i < S.length();++ i) { if (S[i] == 'B') ++ B; else ans += B; } std::cout << ans; return 0; }
B - Powers of two
問題文
問題文
高橋君は正整数が書かれたボールを 個持っています。 番目のボールに書かれている正整数は です。
高橋君は 個のボールからいくつかのペアを作って、それぞれのペアのボールに書かれた数の和が べきとなるようにしたいです。
ただし、同じボールが複数のペアに属することはできません。
最大でいくつのペアが作れるか求めてください。
ただし、正整数が べきであるとは、ある非負整数 を用いて と書けることを指します。制約
- は整数
さて、ペアに関してですが、ここでがより大きい物から順にペアを決めるものとします。
理由としては、まずとペアとなる値がであるとして、よりより、の値はただ一つに定まります。
また、ペアを作らないという選択より作るという選択の方が自明に最適なので、もしそのようながあるならペアにすべきです(これを逃すとのペアは無くなるため)。
さて、そうと決まればまずははソートしておきましょう。
次に決めていくわけですが、そのまま探すと計算量でTLEします。
そこで、考え方をちょっと変えて、先にペアの合計値を大きい方から決め打ちます。
これなら、ペアの合計値は2冪なので高々しかないため、計算量はで、これは十分間に合います。
#include<iostream> #include<algorithm> using namespace std; int main() { static int N, A[200000], ans = 0; cin >> N; for (int i = 0;i < N;++ i) cin >> A[i]; sort(A, A+N); for (int i = 1 << 30;i > 0;i >>= 1) { for (int j = 0, k = N - 1;j < k;) { if (A[j] < 0 || A[k] > 0 && A[j] + A[k] < i) ++ j; else if (A[k] < 0 || A[j] + A[k] > i) -- k; else { A[j] = A[k] = -1; ++ ans; } } } cout << ans; return 0; }
C - Lexicographic constraints
問題文
問題文
個の文字列が一列に並んでおり、どの隣り合う つの文字列に対しても、左に書いてある文字列の方が右に書いてある文字列よりも辞書順で小さいことが分かっています。
つまり、左から 番目の文字列を としたときに、辞書順で が成り立っています。
の長さが であると分かっているとき、 に含まれる文字の種類数として考えられる最小の値を求めてください。制約
- は整数
まず、の時を考えましょう。
これは簡単です、単にの後ろにa
を文字数と一致するまで付加すれば、いっさい文字数を増やさず作れるので最適です。
では、逆にの時はどうしましょうか?
これもまた簡単で、まず文字を一致するまで削り、次にその時の一番後ろの文字を1個分先の文字へ進めます。
ここで、もしもあなたが文字数を決め打っているならば、その文字数を超えた文字になった瞬間に今の文字をa
に戻し、1個手前の文字を代わりに1個分先の文字へ進め…と文字数を超えない文字になるまで繰り返します。
このシミュレーションは、高々で終わります。
ただ、このシミュレーションは文字数を決め打っていることを前提にしているため、そこを何とかする必要があります。
まず、もし文字数が個あるなら、各は番目の文字のみを使えば成立するので、つまり文字以下であることは確定です。
次に。もしある文字数で足りたなら、それより多い文字数では絶対に足ります。逆にある文字数で足りないならそれより少ない文字数では足りません。
ということは、文字数に対して二分探索を、シミュレーションを成功できたかどうかを鍵として行うことができます。
計算量はです。
#include<iostream> #include<stack> using namespace std; int main() { static int N, A[200001] = {}; cin >> N; for (int i = 1;i <= N;++ i) cin >> A[i]; int ans = 0, max = N, mid, halfDiff, tmp; while(halfDiff = max - ans >> 1) { // 二分探索 bool check = false; mid = ans + halfDiff; stack<pair<int, int> > stk; for (int j = 1;j <= N;++ j) { // シミュレーション if (A[j - 1] >= A[j]) { // 文字数が減るパターン while (!stk.empty() && stk.top().first > A[j]) stk.pop(); // 超過部分は削る if (stk.empty() || stk.top().first < A[j]) stk.push(make_pair(A[j], 1)); // stackに入ってないならA[j]番目はaでしょ while (++ stk.top().second > mid) { tmp = mid == 1 ? 1 : stk.top().first; if (tmp == 1) goto break_label; // 変化不能、よってシミュレーション失敗 stk.pop(); if (stk.empty() || stk.top().first != tmp - 1) stk.push(make_pair(tmp - 1, 1)); } } } check = true; break_label:; (check ? max : ans) = mid; } cout << max; return 0; }
D - Grid game
問題文
問題文
高橋君と青木君は 行 列のマス目を使ってゲームをします。
このマス目上には 個の障害物があり、 番目の障害物は にあります。
ただし、 行 列目 にあるマスを で表すことにします。
また、どの障害物も にはなく、 には つの駒が置いてあります。
そこで、高橋君と青木君は高橋君から始めて、交互に以下の行動のいずれかを行います。
- 駒を隣り合うマスに動かす。
ただし、駒の位置を としたとき、高橋君は にのみ、青木君は にのみ駒を動かすことができる。
また、動かすことのできるマスが存在しない、もしくは、動かす予定のマス目に障害物がある場合はこの行動をとることはできない。
- 駒を動かさず、マス目を元の状態のまま行動を終える。
回連続で駒が動かされなかった場合、そこでゲームを終了します。
高橋君はできるだけ多くの回数の行動 (駒を動かさないのも含む) を行ってゲームを終えたいですが、青木君はできるだけ少ない回数の行動を行ってゲームを終えたいです。
このとき、高橋君が行うことになる行動の回数は何回か求めてください。制約
- のとき
- は整数
さて、まず高橋君が動かなかったらどうなるでしょうか?
答えは、青木君が動かないので即座にゲームが終了します。
よって、高橋君は動ける限り動き続けるしかなく、行動の自由があるのは青木君だけであるということが分かります。
ということは、まず第回目の高橋君の移動が終わった時点では座標はになっているはずです。
青木君がすべきは、なるべく座標で見て近い障害物のうち移動可能なものを選んで、座標を合わせてからひたすら移動しないを繰り返すだけですね。
図を見てください。
これはサンプル2で、灰色と黒は障害物、赤は高橋君の移動、緑は青木君の移動となっています。
図から分かるように、障害物を昇順に並び替えると、貪欲にシミュレーションするだけで答えが求まるのが分かりますね(これ本当に800点か?)。
もちろん計算量はソートに依存するのでです。
#include<iostream> #include<algorithm> using namespace std; int main() { int H, W, N, diff = 0; static pair<int, int> point[200000]; cin >> H >> W >> N; for (int i = 0;i < N;++ i) cin >> point[i].first >> point[i].second; sort(point, point+N); // X昇順、同値ならY昇順 for (int i = 0;i < N;++ i) { if (point[i].first - point[i].second - diff > 0) H = min(H, point[i].first - 1); // この障害物を使って邪魔する else if (point[i].first - point[i].second - diff == 0) ++ diff; // 青木君が移動できないので、上を抜けるしかない } cout << H; return 0; }
結果
oox--- 2完(900点) 10:46-92:00(3WA) / 107:00
598位 パフォーマンス: 1649
レート: 1661→ 1660(-1)
コンテスト統計
パフォーマンスの算出にはac-predictorを用いています。
スコア 0点 300点 600点 800点 900点 1000点 1100点 1300点 1500点 1600点 1700点 1800点 2400点 2800点 3600点 3700点 3800点 4600点 4800点 5800点 時間 1:47 54:59 63:38 9:42 75:54 54:25 175:35 128:47 52:56 24:55 54:15 38:47 103:41 67:56 137:20 111:57 68:34 150:41 87:20 順位 1758 683 681 679 387 377 343 342 341 271 196 189 50 47 17 16 15 9 8 1 パフォーマンス 183 1563 1565 1567 1902 1916 1968 1969 1971 2094 2265 2284 2960 2988 3404 3426 3449 3624 3663 4347
パフォーマンス | 0 | 400 | 800 | 1200 | 1600 | 2000 | 2400 | 2800 | 3200 | 3600 | 4000 |
---|---|---|---|---|---|---|---|---|---|---|---|
スコア | 0点 | 300点 | 300点 | 300点 | 900点 | 1600点 | 2400点 | 2400点 | 3600点 | 4600点 | 5800点 |
時間 | 184:20 | 46:58 | 13:30 | 140:53 | 152:42 | 131:21 | 69:44 | 116:35 | 68:34 | 99:24 | |
順位 | 1758位 | 1757位 | 1492位 | 1075位 | 646位 | 323位 | 151位 | 69位 | 28位 | 9位 | 2位 |
感想
これは、解けるべき問題だった……!
C問題はstackとqueueを逆に書いて間に合わない、という大失態でした。
また、D問題がかなり簡単な問題(順位表には出てないけど)だったので、これも解くべきでしたね。
完全にミスです……やっぱり青適性なのかなぁ……。