AtCoder Beginner Contest 109
Updated:
Source codes
Solutions
A - ABC333
$AB \% 2 = 1$ が必要十分条件。
B - Shiritori
実際にしりとりをすれば良い。 Ruby だと、 dic = {} として順次登録する。 $i = 0, \dots, N - 2$ に対し w[i][-1] == w[i + 1][0] かつ dic[w[i + 1]].nil? が条件である。
C - Skip
$x[i] \gets \lvert x[i] - X \rvert$ とする。 $\gcd(x[0], \dots, x[N-1])$ が答えである。 $N = 1$ の場合は $x[0]$ が答え。
ポイント
解説放送を見て ll gcd(ll x, ll y) の簡単な実装を把握した。
ll gcd(ll x, ll y)
{
return y ? gcd(y, x % y) : x;
}
D - Make Them Even
コンテスト中に思いついた解法
$0$-indexed とする。コインが偶数か奇数かだけが問題である。奇数の場合 a[i][j] = true とし、そうでない場合は false としよう。
まず各行 $i = 0, \dots, H - 1$ に対し、以下の操作を行う。
int cnt = 0;とする。 $j = 0, \dots, W - 1$ に対し、 $a[i][j]$ がtrueならば、カウンタcntをみる。- 偶数だったら $y = j$ として記憶しておく。
- 奇数だったら $y’ = j$ として、 $k = y, \dots, y’ - 1$ に対して $swap((i, k), (i, k + 1))$ を行う。
- いずれの場合も
cnt++;とする。
- 最後までみていって
cntが奇数ならば、 $y’ = W - 1$ として同じことをする。この場合odd[i] = true;とする。偶数ならばfalseとする。
次に int cnt = 0; とする。 $i = 0, \dots, H - 1$ に対し $odd[i]$ が true ならば、カウンタをみて、上記と同様のことを今度は縦方向にする。今度は $swap((k, W - 1), (k + 1, W - 1) )$ をする。
以上の操作により、コインの合計数が偶数なら全てのマスが偶数個になる。奇数個ならある $1$ マスをのぞいて偶数個になる。前者も後者もそれ以上にはなり得ないのでこれで解答を与えている。
模範解答
この問題は $1$ 次元だと超簡単である。そこで $HW$ マスを連続した $1$ 次元の列で巡る。この列 $\{ (x_i, y_i) \}$ に対して上の最後の操作をすればよろしい。
解説放送の解答
$a[i][j]$ には普通に数字を入れる。 $i = 0, \dots, H - 2$ に対し $j = 0, \dots, W - 1$ に対し $a[i][j]$ が奇数ならば $move((i, j), (i + 1, j))$ を実行する。その後 $j = 0, \dots, W - 2$ に対し $a[H - 1][j]$ が奇数ならば $move((H - 1, j), (H - 1, j + 1))$ とする。
ポイント
実装が重すぎたのかなぁ。みんな早いですね。 2 次元平面を繋げて 1 次元に落とす という定跡を使う。かなり難しいと思っていたけどここで使うとは。
解説放送の解答の場合は、 ライツアウトの解法 に近い。
Others
今日から AtCoder と GitHub の所属組織を Chaldea Security Organization にした。