###### tags: `Codeforces` `競プロ` `ログ` Codeforces Round #492 (Div1) === 初のDiv.1コンテスト。渡る世間はプロばかり。 [コンテストリンク](http://codeforces.com/contest/995) A. Tesla (※自動車会社名) === [問題リンク](http://codeforces.com/contest/995/problem/A) ## 概要? スライドパズルの要領で駐車場に車を入れよう! ## 解説 概要が雑だが気になる人は本文を読んでほしい。ここで説明する分量ではない。 本番で思いついたのが以下のようなアルゴリズムで、Editorialもこれと全く同じ解法だった。 1. 駐車場に接している車は入れてしまう。 2. 車を全部反時計回りに移動させる(キャタピラの要領)。 3. 1に戻り、全ての車が入ったら終わる。 2の時点で車が移動できない、つまり$K = 2N$で全ての車が駐車場に隣接していない場合だけ`-1`と出力すればよい。 そうでない場合、各車は多くても1周$=2N$しか移動しないので、制約から最悪でも$10000$回程度の移動で終わる。 と、言うのは簡単だが実装がアホみたいに重い。特に実装が難しいのが * ループが回しにくい * 2で適当に1周回してしまうと車が衝突してしまう可能性があり、空きマスから移動させなければならない の2点。最初はループを4分割して管理性最悪の継ぎ接ぎコードを書いていたが、結局バグに対処しきれずうんざり。 こういったコードを書いているときは、すぐに書くのを中断してもっと効率的な書き方を考えるのが大切。実際、そのあと「**ループを配列にしちゃえばいいじゃーん**」ってことに気づいて全部書き直したら、コード量は格段に減ったし一発で通った。 ## 回答例 ```cpp= using namespace std; template <typename T> using V = vector<T>; template <typename T, typename U> using P = pair<T, U>; #define fst first #define snd second #define pb push_back #define mp make_pair #define SIZE(v) (LL((v).size())) #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) #define NREP(i, n) FOR(i, 1, n + 1) // Usual REP runs from 0 to n-1 // Natural REP runs from 1 to n /* ---------- ここまでマクロ ---------- */ int main() { int N, K; cin >> N >> K; V<V<int>> place(5, V<int>(N + 1)); // 1-indexedで記録 NREP(i, 4) { NREP(j, N) { cin >> place[i][j]; } } V<P<int, P<int, int>>> ans; // 手順を記録 (id, (c, r)) V<P<int, int>> loop(N * 2 + 1); // ループの回る順番を記録する配列 REP(i, N) { loop[i] = mp(2, i + 1); loop[i + N] = mp(3, N - i); } loop[N * 2] = loop[0]; // [(2,1),(2,2), ... ,(2,N), // (3,N),(3,N-1), ... ,(3,1),(2,1)] while (true) { bool finish = true; // 1. 格納できる車を格納 NREP(j, N) { if (place[1][j] > 0 && place[1][j] == place[2][j]) { ans.pb(mp(place[2][j], mp(1, j))); place[2][j] = 0; } else if (place[2][j] > 0) { finish = false; } } NREP(j, N) { if (place[4][j] > 0 && place[4][j] == place[3][j]) { ans.pb(mp(place[3][j], mp(4, j))); place[3][j] = 0; } else if (place[3][j] > 0) { finish = false; } } // 上のコードは1,2行目と,3,4行目で2つに分けているが、 // place[i][j] == place[i^1][j]的な方法もある if (finish) break; // 全部格納できたら終了、出力へ // 2. 車を反時計回りにローテーション // まずは空きマスを探す int begin = -1; REP(i, N * 2) { auto p = loop[i]; if (place[p.fst][p.snd] == 0) { begin = i; break; } } // 空きマスがない->車が移動できないので不可能 if (begin < 0) { cout << -1 << endl; return 0; } // 次いで手順を記録する // 空きマスを始点として、時計周りに1周見ていく FOR(i, begin, 2 * N) { auto p = loop[i + 1]; if (place[p.fst][p.snd] > 0) { ans.pb(mp(place[p.fst][p.snd], loop[i])); } } REP(i, begin) { auto p = loop[i + 1]; if (place[p.fst][p.snd] > 0) { ans.pb(mp(place[p.fst][p.snd], loop[i])); } } // それから実際に移動する // 移動自体は空きマスとかガン無視でいい // リアルタイム更新みたいな破壊的な方法は、やめようね! V<V<int>> to = place; REP(i, N * 2) { auto p = loop[i], sp = loop[i + 1]; to[p.fst][p.snd] = place[sp.fst][sp.snd]; } place = to; } // 最後に手順を出力 cout << SIZE(ans) << endl; for (auto p : ans) { cout << p.fst << " " << p.snd.fst << " " << p.snd.snd << endl; } return 0; } ``` メインパートがコメント抜きでも約80行、これは重い。 実際この問題は点数の割に重すぎるため、どう考えても飛ばすのが正解。この問題に50分くらい掛けてしまったために、10分で解けるB問題の点数が下がったのが悔やまれる[^point]。問題の識別眼がまだまだ鍛えられてないなぁと実感した。実践経験不足だろうか。 [^point]: 覆水盆に返らずとは言うが、もし最初に解いてればもう100点は稼げていた。それでもAが遅すぎて20位くらいしか変わんないけど。 B. Suit and Tie[^sat] (集合写真) === [問題リンク](http://codeforces.com/contest/995/problem/B) [^sat]: タイトルの「Suit and Tie」は直訳すると「スーツとネクタイ」だが、慣用句的に「格調高い」という意味があるらしい。 ## 概要 $1 \sim N$がそれぞれ2個ずつ入った長さ$2N$の配列がある。 隣り合う要素を何度かswapして同じ数字が隣り合うようにするとき、最小のswap回数を求めよ。 ### 制約 * $1 \leq N \leq 100$ ## 解説 先程「10分で解ける」と言ったが、実際AtCoderでも300点くらいの問題である。というのも、**貪欲に頭の要素からペアを作る**だけで事が済む。 下手に真ん中の方からペアを作ると、そのペアをまたぐように分かれているペアについて、操作数が2増えてしまうことからも分かるだろう。 ## 回答例 ```cpp= using namespace std; template <typename T> using V = vector<T>; using ll = long long; #define FOR(i, a, b) for (ll i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) #define NREP(i, n) FOR(i, 1, n + 1) // Usual REP runs from 0 to n-1 // Natural REP runs from 1 to n /* ---------- ここまでマクロ ---------- */ int main() { ll N; cin >> N; V<ll> A(N * 2); REP(i, N * 2) { cin >> A[i]; } ll ans = 0; // 総swap回数 while (!A.empty()) { NREP(i, N * 2 - 1) { if (A[i] == A[0]) { // swap回数は転倒数、ここでは移動距離と同じ ans += i - 1; } } V<ll> tmp; // A[0]以外の要素を順番通りに抽出 // 下手にeraseとか使うとバグりそうなのでやめといた REP(i, N * 2) { if (A[i] != A[0]) { tmp.push_back(A[i]); } } A = tmp; N--; } cout << ans << endl; return 0; } ``` 私が本番中に解けたのはこの2問まで。 C. Leaving the Bar (千鳥足) === [問題リンク](http://codeforces.com/contest/995/problem/C) ## 概要 $N$個の二次元ベクトル$\vec{v_i}$が与えられる。 Allenは最初原点にいて、各ベクトルについて$\vec{v_i}$か$-\vec{v_i}$だけ移動する。言い換えるなら、最終的に $$ \vec{p} = \sum_i c_i \vec{v_i} \hspace{2ex} (c_i = \pm 1) $$ にいることになる。このとき、$| \vec{p} | \leq 1.5 \times 10^6$を満たすように各$c_i$を決めよ。 ちなみに、以下の制約下では条件を満たす$c_i$のパターンが必ず存在する。 ### 制約 * $1 \leq N \leq 10^5$ * $|\vec{v_i}| \leq 10^6$ ## 解法 最初「ノルムが大きい順にソートして、絶対値ができるだけ小さくなるように$c_i$を決める」という脳筋解法をぶん投げたら案の定通らなかった。その時点ではAがまだ解けてなかったので即諦めたが、気になってEditorialを見たら中々に面白い解法だった。 Editorial解法の肝は > 3つのベクトルがあるとき、そのノルムの最大値を$r$とする。 > 3つから適切に2つのベクトルを選ぶと、その和差でノルムが$r$以下になるものが必ず存在する。 という定理。正三角形を思い浮かべるとなんとなく分かるのだが、詳しくは[Editorial](http://codeforces.com/blog/entry/60217)を見ていただきたい。 これを$N$個のベクトルに順番に適用すると、制約から最終的にノルムが$10^6$以下の2つのベクトルが残る。これらの和差のノルムの最小値は高々$\sqrt{2} \times 10^6$なので、条件を満たすようにできる。 上の定理は大学入試でも出てきそうな感じはある。幾何問題難しいね。 ## 回答例? Coming soon... D. Game (ゲーム) === [問題リンク](http://codeforces.com/contest/995/problem/D) ## 概要 関数$f:\{0, 1\}^N \rightarrow \mathbb{R}$($N$桁のbit列に実数を対応させるような関数)がある。 AllenとBessieは**ランダムに決められた**順番で$N$桁からなるbit列の各桁の値を決めていき、最終的に得られたbit列を$x$として$f(x)$を最終的なスコアとする。 Allenはスコアを最大化するように、Bessieはスコアを最小化するようにするとき、スコアの**期待値**を求めよ。 ちなみにこの問題は$f$の一部が変わる$r$回のクエリ制になっている。 ### 制約 * $1 \leq N \leq 18$ * $0 \leq f(x) \leq 10^9$ * $0 \leq r \leq 2^{18}$ ## 解法 ゲーム系かと思ったら点数がバラバラだし、順番はランダムだしでなんかよく分からない問題。無論$2^N$の全順番を試していては余裕でTLEだし、実装方法もよく分からない。 まぁ答えを言ってしまうと、期待値は $$ \frac{1}{2^{N}} \times \sum_{x=0}^{2^N-1} f(x) $$ つまり **$f$の平均**で出せてしまう。えぇ...。 [Editorial](http://codeforces.com/blog/entry/60217)での説明はだいたい以下の通り: > $x$番目のbitを$t$にしたときのスコアの期待値を$v_{x,t}$とおく。このとき、$\frac{v_{x,0}+v_{x,1}}{2} = \mathbb{E}(f)$が成り立つ。 > > さて、最初がAllenの番だったとする。このときAllenは$v_{x,t}$が最大となるような$x, t$について操作を行うことになる。 > > このとき、$v_{x,1 - t} = 2 \mathbb{E}(f) - v_{x,t}$から$v_{x, 1-t}$が$v$の最小値となる。よって最初がBessieの番である場合、Bessieは${x, 1-t}$について操作を行うことになる。 > > したがってスコアの期待値は$\frac{v_{x,t}+v_{x,1 - t}}{2} = \mathbb{E}(f)$となる。 なんか分かるような分からないような...。確率論難しいね。 ## 回答例 ```cpp= using namespace std; template <typename T> using V = vector<T>; #define DOUBLE(n) static_cast<double>(n) #define FOR(i, a, b) for (ll i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) // Usual REP runs from 0 to n-1 #define fcout cout << fixed << setprecision(10) /* ---------- ここまでマクロ ---------- */ int main() { ll N, R; cin >> N >> R; ll sum = 0; V<ll> A(1 << N); REP(i, 1 << N) { cin >> A[i]; sum += A[i]; } fcout << DOUBLE(sum) / (1 << N) << endl; // ここからクエリ REP(i, R) { ll z, g; cin >> z >> g; sum -= A[z]; A[z] = g; sum += g; fcout << DOUBLE(sum) / (1 << N) << endl; } return 0; } ``` 感想 === なんか最近、問題の難易度を見極める力が試されている気がする。しかし私の実力で解けるのはA,Bだけ(運がよければDも)だったし、Aの実装が遅かった時点でまぁ実力もそんなもんなんだろうか。 ![](https://i.imgur.com/lKvhNE6.png) 結果はこんな感じ。ラッキーセブン。でもレートは2下がった。 初のDiv1コンテストだったが、早くもDiv2への郷愁の念に駆られている。しかし私は決してくじけない。