AtCoder Grand Contest43に参加した話。

AGC43に参加した。結果を先に貼ると以下。

Ranking: 1036th / 3490
Rate: 651 → 780
Performance: 1490

よかったところもあり、反省すべきところもあり。C問題以降はまた別の機会に手を出すとして、今回は自分が取り掛かったA問題、B問題を自分の反省を含めて紹介する。

A - Range Flip Find Route

定番のグリッドの問題。 $H$ 行 $W$ 列のグリッドが与えられて各マスは白か黒で塗られている。白は通ることができるし、黒は通ることができない。右移動もしくは下移動だけかつ白いマスだけを通って(1, 1)から(H, W)を目指すゲーム。ゴールできる様に以下の操作をすることができる。

4つの整数 $r_0, \ r_1, \ c_0, \ c_1 \ (0 \leq r_0 \leq r_1 \leq H, \ 0 \leq c_0 \leq c_1 \leq W)$ を選び $r_0$ ~ $r_1$ 行かつ $c_0$ ~ $c_1$ 列に含まれるマス目の色を反転する（白であれば黒にし、黒であれば白にする）。

ゴールするために必要な操作の最小回数を求めよ。

考察

２０分くらいずっと考えていて、わからず困っていた。困ったときはDP頼み。DPにお願いしてこの問題を解いてもらおうと考えた。

具体的にはこんなDP。(1, 1)から(i, j)を目指すうえで必要な操作の最小回数についてのDP。

右移動もしくは下移動しかできないので、(i, j-1)における値と(i-1, j)における値がわかっていれば大丈夫。説明するの面倒なので、下にコードを貼っておきます。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main() {
  int h, w;
  cin >> h >> w;
  vector<vector<char>> G(h, vector<char>(w));
  for(int i=0;i<h;i++) for(int j=0;j<w;j++) cin >> G[i][j];
  vector<vector<int>> dp(h, vector<int>(w));
  for(int i=0;i<w;i++) {
    if(i == 0) {
      if(G[0][i] == '#') dp[0][i] = 1;
    }
    else {
      if(G[0][i] == '.') dp[0][i] = dp[0][i-1];
      else if(G[0][i-1] == '#') dp[0][i] = dp[0][i-1];
      else dp[0][i] = dp[0][i-1] + 1;
    }
  }
  for(int i=0;i<h;i++) {
    if(i == 0) continue;
    if(G[i][0] == '.') dp[i][0] = dp[i-1][0];
    else if(G[i-1][0] == '#') dp[i][0] = dp[i-1][0];
    else dp[i][0] = dp[i-1][0] + 1;
  }
  for(int i=1;i<h;i++) {
    for(int j=1;j<w;j++) {
      if(G[i][j] == '.') dp[i][j] = min(dp[i-1][j], dp[i][j-1]);
      else {
        int up = dp[i-1][j];
        int left = dp[i][j-1];
        int upc = G[i-1][j];
        int leftc = G[i][j-1];
        int candi_1 = 0, candi_2 = 0;
        if(upc == '.') candi_1 = up + 1;
        else candi_1 = up;
        if(leftc == '.') candi_2 = left + 1;
        else candi_2 = left;
        dp[i][j] = min(candi_1, candi_2);
      }
    }
  }
  cout << dp[h-1][w-1] << endl;
}

Editorial

経路を一つ決めたときにその経路を通れる様にするには何回操作する必要があるかを考えます。経路において、白いますから黒いマスに移動する回数に、 $s_{11}$ が黒の時のみ1を加えた値を $Z$ とします。実はこの経路を通れる様にするために最小の操作回数は $Z$ です。（一番重要なポイント）

操作を行ったときに、経路のマスの色がどの様に変化するかを考えます。これは、全く変化しないか、もしくは経路のある区間の色が反転することがわかります。また、経路の全ての区間について、そこを反転させる様な操作が可能であることもわかります。

以上の観察により、経路の色の列の区間を好きに反転させられるとき、全てのマスを白色にするには何回操作を行う必要があるか、を考えればいいことがわかります。そして、どの様な操作をしても $Z$ が必ず $1$ しか減らせないこと、また、 $Z$ を $1$ 減らすような操作が可能であることに気づくと、最小回数が $Z$ であることがわかります。

あとは $Z$ が最小の経路を探せばよく、DPを行うことでこの問題の答えを得ることができます。

解説ではなぜ最小の操作回数が $Z$ であるのかを丁寧に説明している。

A問題だけを最速で解いたら

A問題までだけ解いていて、もっともパフォーマンスが高かった人のデータを見る。

f:id:horoyoisawa:20200322075532p:plain — A問題だけ解けた人で最も速かった人

Ranking: 572nd / 3490
Performance: 1880

速解き重要。

B - 123 Triangle

1, 2, 3で構成される長さ $N$ の数列 $a$ が与えられる。次の規則で決まる数[x_{i, \ j}]がある。

$x_{1, \ j} = a_j$
$x_{i, \ j} = | x_{i-1, \ j} - x_{i, \ j+1} |$

$x_{N, 1}$ を求めよ。

考察

開始30分から終了までずっと考えていたけど全く見当がつかなかった。どうやったら解けてたんだろ。考察はしてたけどほとんど意味のない迷走だったので割愛。

解説

まず入力から $1$ を引いて $a_i = 0, \ 1, \ 2$ としても構いません。 $x_{i, \ j}$ は全て $0, \ 1, \ 2$ のいずれかになります。まず答えの偶奇を考えてみます。すると $x_{i, \ j}$ は $x_{i-1, \ j}$ と $x_{i-1, \ j+1}$ のちょうどどちらか一方が奇数のときに奇数になることがわかります。よって次の問題が解ければ答えの偶奇がわかります。

各要素が $0, \ 1$ である $x_{1, \ 1}, . . . , x_{1, \ N}$ が与えられます。 $x_{i, \ j}$ を次の様に定義します。

$x_{i, \ j} = x_{i-1, \ j} \ \verb|^| \ x_{i-1, \ j+1}$

$x_{N, \ 1}$ を求めてください。ただし^は排他的論理和を表します。

これは次の様にして解けます。まずパスカルの三角形の様なものを考えると、 $a_i$ が答えへ寄与する回数は $\left( \begin{array}{c} N-1 \\ i \\ \end{array} \right)$ であることがわかるので、この偶奇が全て求まれば良いです。これは $Lucas$ の定理から求めたり、二項係数の式にしたがって $2$ で何回割り切れるかを求めたりすることで可能です。

これで答えが $1$ のケースは特定できました。 $0$ と $2$ を区別するために次のことを考えます。

入力に $1$ が存在するか？

存在する場合、答えは $2$ にならないことが示せます。よって次の様な手順で問題を解くことができます。

答えが奇数かどうか判定する。奇数なら答えは $1$ 。

入力に $1$ が含まれるか判定する。含まれるなら答えは $0$

そうでない場合、入力は $0$ か $2$ なので、全体を $2$ で割ると前のケースに帰着できる。

計算量は $O(N)$ です。

偶奇に着目できれば解けたかもしれない。だけどその先の部分問題が解けているかどうかはわからない。。

Editorialを参考にして即席で書いたコードがこちら。

#include <iostream> #include <vector> #include <set> #include <algorithm> #include <bitset> using namespace std; int main() { int n; cin >> n; bool one = false; vector<int> a(n); for(int i=0;i<n;i++) { char c; cin >> c; a[i] = c - '1'; if(a[i] == 1) one = true; } int ans = 0; for(int i=0;i<n;i++) { if(a[i] % 2 == 0) continue; else { bool even = false; bitset<32> x(n-1); bitset<32> y(i); for(int j=0;j<32;j++) { if(!x.test(j) && y.test(j)) { even = true; break; } } if(!even) ans ^= 1; } } if(ans == 1) { cout << 1 << endl; return 0; } if(one) { cout << 0 << endl; return 0; } for(int i=0;i<n;i++) { if(a[i] == 0) continue; a[i] /= 2; bool even = false; bitset<32> x(n-1); bitset<32> y(i); for(int j=0;j<32;j++) { if(!x.test(j) && y.test(j)) { even = true; break; } } if(!even) ans ^= 1; } cout << ans * 2 << endl; return 0; }

Lucusの定理クソほど便利ですね。

A問題とB問題が解けている人

A問題とB問題が解けている方の中でランキングが最も高い人と低い人を見てみる。まずは低い人から。

f:id:horoyoisawa:20200322100518p:plain — 終了1分前に通してる。。。。流石すぎる

Ranking: 546th / 3490
Performance: 1908

こうやって終了直前にACしたら最高の気分なんだろうなぁ。

次に高い人

f:id:horoyoisawa:20200322100924p:plain — 30分かからずB問題まで問いている。。。

Ranking: 152nd / 3490
Performance: 2561

オレンジパフォ！！！！速く解くのは大切だなぁ。凄すぎる。

感想と反省

今回も反省が多いなぁ。とにかく列挙してみる。

二次配列のブラケットを書くのが遅すぎる。。何回タイプミスをすればいいんだ。練習せねば。タイピング練習大切。
B問題がどうすれば気づけていたのかわからないなぁ。たくさん解くしかないんかなぁ。偶奇に着目することが重要ってわかってたはずなんだけどなぁ。結局解けてないのでまたいろいろ解いて感覚を磨くしかないのかもしれない。
いつものことだけど手が震えすぎ。緊張しないで書ける様に練習しろ。なんでこんな震えるんだ。。。。
速く解くことをかなり強調してるけど、というのも上のデータが示している通りだ。考察力以前に練習すればスピードは向上する。その部分を疎かにしたくない。
後半の２時間ずっとB問題を考えられたのはよかった。他の問題を見ないで。結局問題は解けなかったのだが、それでも一つの問題に集中できたのはいい。
次はB問題までを誰よりも速く解ければいいなぁ。

とにかくお疲れ様でした。今日のAtCoder Beginner ContestとGoogle Kickstart A Stage頑張りましょう。

horoyoisawaのゴミ箱

いろいろ書きます