Codeforces Round #487 (Div2) LOG === 久々のCodeforcesコンテスト。昨日はABCの方に専念したが、今日は他にやることもない[^todo]のでもちろん参加。 中々に疲れたコンテストになりました。 [^todo]: 中間試験...... Eは問題を見てすらいないので本記事では触れません、悪しからず。 ちなみに問題名の和訳はオリジナル。センスなくても許して。 目次 === [:contents] A. A Blend of Springtime (混じり合う春花) === [問題リンク](http://codeforces.com/contest/989/problem/A) ## 超要約 'A','B','C','.'の4文字からなる文字列が与えられる。 このとき、連続する3文字の部分文字列で'A','B','C'を1つずつ含むものがあるか判定せよ。 ## 解説 本質的には上の通りなのだが、問題文がめちゃくちゃ読みづらい。 「花が枯れる」とか「種が広がる」とか結局何が言いたいんだ。 しかし忘れてはならない。**これこそがCodeforcesである。** 何にせよ提出コードは以下の通り。簡単な尺取り法。 ```cpp= int main() { string S; cin >> S; V<int> cnt(3, 0); // 区間に含まれるA,B,Cの数を数える REP(i, SIZE(S)) { if (S[i] != '.') { cnt[S[i] - 'A']++; } bool flag = true; REP(j, 3) { if (cnt[j] == 0) { flag = false; break; } } if (flag) { cout << "Yes" << endl; return 0; } // 外れる要素を抜くのをお忘れなく if (i >= 2) { cnt[S[i - 2] - 'A']--; } } cout << "No" << endl; return 0; } ``` もちろん尺取りじゃなくて地道に全探索しても余裕で通る。 AtCoderなら200点ってところだろうか。 B. A Tide of Riverscape (満ち干く河) === [問題リンク](http://codeforces.com/contest/989/problem/B) ## 要約 1,0,.からなる文字列が与えられる。 .を1か0に置き換えることで、$i$文字目と$i + p$文字目が異なるような$i$が存在するようにできるか判定せよ。 出来なければNoを出力、出来るなら条件を満たすように置き換えた例を1つ出力せよ。 ## 解説 Aに比べれば趣旨は理解しやすいし、言うほど難しくもない。 順番に$i$文字目と$i + p$文字目を比較して、どちらか一方でも.ならYesで適切に置き換え、そうでなくても文字が異なればYes。 ただこの問題、曖昧なのが$p=n$のケース。問題文からこれがYesなのかNoなのかがよく分からない。 私はNoにしたけど通ったので、もしかしたらテストに入っていないのかもしれない[^B_gaba]。 [^B_gaba]: でもこれ普通に考えてYesじゃない?なんで通ったんだろうか。 で、提出したのがこれ。 ```cpp= int main() { const string num = "01"; // .に値入れるときに使う int N, p; cin >> N >> p; string S; cin >> S; bool judge = false; REP(i, N - p) { if (S[i] != '.' && S[i + p] != '.' && S[i] == S[i + p]) continue; // 上の条件を満たさないiが1つでもあればYes judge = true; if (S[i] == '.' && S[i + p] == '.') { // 両方.ならとりあえず0と1に変える S[i] = num[0]; S[i + p] = num[1]; } else if (S[i] == '.') { // 一番上のnumを使って、.じゃない方と被らないように変える S[i] = num[(S[i + p] - '0' + 1) % 2]; } else if (S[i + p] == '.') { S[i + p] = num[(S[i] - '0' + 1) % 2]; } } if (!judge) { cout << "No" << endl; return 0; } for (char c : S) { // N-pからpは調べてないので、.が残っていることに注意 if (c == '.') { cout << 1; } else { cout << c; } } cout << endl; return 0; } ``` 通ったはいいがイマイチ釈然としない。 普通に落ちてもおかしくなかったし、問題に落ち度があるとしか思えない。 細かいところを無視すれば、AtCoderなら300点の下位といったところだろうか。 C. A Mist of Florescence (霞みの中の花畑) === [問題リンク](http://codeforces.com/contest/989/problem/C) ## 概要 A,B,C,Dが書かれたグリッドについて、互いに隣接しあった同じ文字の集団をグループとする。 このとき、A,B,C,Dのグループ数がそれぞれ$a, b, c, d$になるように長方形のグリッドを作成せよ。グリッドのサイズは制約内なら不問。 ## 解説 俗に言う構築系問題。思いつけば一発のひらめき勝負。 1. $50 \times 50$のグリッドを用意します。 1. 上半分をA、下半分をBで埋めます。 1. 上半分に$c$個のCと$b-1$個のBを1マス間隔で埋めます(詳しくは下図)。 1. 同様に下半分に$d$個のDと$a-1$個のAを埋めます。 1. 出力します。 例えば``10 15 20 25``の場合の出力は、グリッドを$20 \times 20$とすると以下の通り。 ```= CACACACACACACACACACA // Cを20個埋める AAAAAAAAAAAAAAAAAAAA CACACACACACACACACACA AAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAA BABABABABABABABABABA // Bを14個埋める AAAAAAAAAAAAAAAAAAAA BABABABAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAA BBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBB ABABABABABABABABABBB // Aを9個埋める BBBBBBBBBBBBBBBBBBBB DBDBDBDBDBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBB DBDBDBDBDBDBDBDBDBDB BBBBBBBBBBBBBBBBBBBB DBDBDBDBDBDBDBDBDBDB // Dを25個埋める ``` そしてこれを実現するコードがこちら。 ```cpp= int main() { int a, b, c, d; cin >> a >> b >> c >> d; cout << 50 << " " << 50 << endl; V<string> pic(50, string(50, 'B')); // 全部Bで埋める REP(i, 25) { // 上半分をAで埋める pic[i] = string(50, 'A'); } REP(i, c) { // Cをc個、1マス間隔で置いていく pic[(i / 25) * 2][i % 25 * 2] = 'C'; } REP(i, b - 1) { pic[(i / 25) * 2 + 10][i % 25 * 2] = 'B'; } REP(i, d) { pic[49 - (i / 25) * 2][i % 25 * 2] = 'D'; } REP(i, a - 1) { pic[39 - (i / 25) * 2][i % 25 * 2] = 'A'; } for (string s : pic) { cout << s << endl; } return 0; } ``` 「こんな解法思いつくか!」って?私も初見はそう思った。 だが初見ではないんだなこれが。 初見だった人はこの問題を解いてみましょう。↓ [AtCoder Beginner Contest 089-D 「Grid Components」](https://beta.atcoder.jp/contests/abc092/tasks/arc093_b) というわけでAtCoderなら500点相当の問題。 解説にも書かれていたが、人によって全然実装方法が違うのが面白い。 ## D. A Shade of Moonlight (陰る月光) [問題リンク](http://codeforces.com/contest/989/problem/D) ### 概要 数直線上に長さ$l$の雲が$n$個浮かんでおり、それぞれ速度$1$か$-1$で動いている。 ある雲のペアについて、絶対値が$w_{max}$以下の風を吹かせることで、同時刻にどちらも原点を覆うようにしたい(風速はペアごとに独立でよい)。 このようにできる雲のペアはいくつあるか。 ### 感想 一言で言うならクソ重い幾何問題。 式をコネコネしている間に頭がこんがらがって、結局戦意喪失という結果に。キツかった。 解説はどう説明しているのかと気になって見てみたら、時間軸を取ることで目視しやすいようにし、さらに月を風で動かすことにすることで単純化していた。なるほど、賢い。 それでも答えは相当煩雑っぽいが。 コンテスト中の正答者数が50人程度だった辺り、Dにしては相当の難問だったようだ。早々に見限ってhackに移ればよかったかな〜[^hack]とか思ったり思わなかったり。 [^hack]: 実は今まで参加してきたコンテストでは一度もhackしたことがない。lockしてからミスに気づいたら悲しいじゃんね。 感想 === 全体的にう〜んな感じのコンテストだった。 Cに関しては初見だったら相当厳しかっただろうが、初見じゃないこと自体が精進の現れでもある。 なお、成績はいつも通り3完、全体231位(Rated内で202位)で過去最高記録。Dが超絶重いタイプの問題だったおかげでもある。次で紫に乗りたいところ。 ちなみに5日後の6/17にRound #488があるらしい。**01:35から**。殺す気か。