AtCoder Grand Contest 013
Updated:
【AGC013】
— AtCoder (@atcoder) 2017年4月15日
ご参加ありがとうございました。
解説PDF：https://t.co/FRQElwvnsE
解説放送：https://t.co/PERsHOQSMV
問題
A - Sorted Arrays
素直に数える。貪欲法。
B - Hamiltonish Path
適当な頂点をパスの中間点とみなし、両側に伸ばす。伸ばせなくなったら終わり。 deque を使う。
C - Ants on a Circle
プログラミングコンテストチャレンジブックの冒頭の通り、蟻をすり抜けることにすると、答えの集合はすぐわかる。
隣の蟻が誰であるのかは変わらない。 番号$1$の蟻がどこに行くのかをいきなり求めるのではなく、 どの番号の蟻に対応するのかをまず求める。その蟻の答えは求まる。 答えの集合をソートし、どこに行ったのか求める。 そこを起点に番号を振り、出力する。
その他間違えたところ。
- 蟻が円周を$1$周すると、逆方向に進行する蟻とは$2$回出会う。
- $L$を$N$回足すとオーバーフローする可能性がある。注意深く余り算をする。
D - Piling Up
$1$次元の長さ$N$の線分を遷移する問題になる。タネがわかれば実装は簡単。
$dp[i][j][k] =$ 時刻 $i$ で頂点 $j$ にいる場合の数。 但し $k = 0$ のときは原点にタッチせず、$k = 1$のときはタッチ済み。
とする。$k$により重複を除いている。あとは遷移するだけ。
E - Placing Squares
解説にある通り、$2$つのボールと仕切りの挿入に問題を言い換える。 その後の遷移をメモする。
\[ dp[i] = \begin{pmatrix} dp[i][0] \\ dp[i][1] \\ dp[i][2] \end{pmatrix} \] とする。 \[ dp[0] = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \] である。
1 マスごとに、次の 8 種類のブロックをくっつける。
- なにもしない
- 赤ボールを置く。
- 青ボールを置く。
- 赤ボールと青ボールを置く。
- 仕切りを置く。
- 赤ボールと仕切りを置く。
- 青ボールと仕切りを置く。
- 赤ボールと青ボールと仕切りを置く。
右から仕切りまでの間を見る。
- 何もボールがない場合は、1, 2, 3, 4, 8 が置ける。
- 青ボールがある場合は、1, 3, 7 が置ける。
- 赤ボールがある場合は、1, 2, 6 が置ける。
- 赤・青ボールがある場合は、1, 5 が置ける。
ただし、仕切りが立てられない地点では、5, 6, 7, 8 は置かれない。 また、座標$N$では仕切りが置かれなければならないので、1, 2, 3, 4 は置かれない。 以上により、$A, B, C \in M_3(\mathbb{Z})$を以下の通り定義し、 普段は$A$、仕切りが置かれなければ$B$, $N$に遷移する際には$C$を $dp[i]$にかければよい。
\[
A = \begin{pmatrix} 2 & 1 & 1 \
2 & 1 & 0 \
1 & 1 & 1
\end{pmatrix},
B = \begin{pmatrix} 1 & 0 & 0 \
2 & 1 & 0 \
1 & 1 & 1
\end{pmatrix},
C = \begin{pmatrix} 1 & 1 & 1 \
0 & 0 & 0 \
0 & 0 & 0
\end{pmatrix}.
\]
余談
解説放送の rng58 さんは「言い換えたら後は簡単な問題」と仰っていたが、 この遷移が簡単であるとは到底思えない。 たしかに動的計画法自体に工夫するべき点が必要なわけはない。 私は動的計画法が苦手だが、プロい人から見れば動的計画法はむしろ楽勝なのだろう。
とくに $C$ の $(1, 1)$ 成分が $A$ の $(1, 1)$ 成分と違うところは間違えやすい。 しかしサンプルが通らないので提出前に気づくことはできる。
F - Two Faced Cards
解法を見る限り、区間和の更新のところに $O(\log N)$ が要求されるので、セグメント木か BIT が必要だろう。どちらも自信がないので少し修行してきます。
- http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_E これが多分必要。
- http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=DSL ここにあるのをついでにやろう。
- http://hos.ac/slides/20140319_bit.pdf BIT はここで学んだ。