AtCoder Grand Contest 013

更新日時:

問題ページ

問題

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. 赤ボールと青ボールを置く。
  5. 仕切りを置く。
  6. 赤ボールと仕切りを置く。
  7. 青ボールと仕切りを置く。
  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 はここで学んだ。

コメントする