AtCoder Beginner Contest 241（Sponsored by Panasonic）のきろく

AtCoder Beginner Contest 241（Sponsored by Panasonic）に参加。

A - Digit Machine (100点)
B - Pasta (200点)
C - Connect 6 (300点、実行時間制限: 3 sec)
D - Sequence Query (400点)
E - Putting Candies (500点)
F - Skate (500点)
G - Round Robin (600点)
Ex - Card Deck Score (600点、実行時間制限: 3 sec): 未提出
結果、感想

A - Digit Machine (100点)

$a_{a_{a_0}}$ が答えです。
見にくいので別表記すると $f(x) = a_x$ として $f^3(0) = f(f(f(0)))$ となります。

C - Connect 6 (300点、実行時間制限: 3 sec)

$4$ マス以上が黒であるような連続 $6$ マスが存在するとき、答えはYes、そうでないときNoとなります。
連続 $6$ マスは各マスから8方向へ6回探索すればよく、それぞれについて黒マスの数を数えればいいです。
尚、全てのマスについて調べるので8マスのうち半分は調べなくてもいいです((上, 下), (左, 右), (左上, 右下), (右上, 左下)の各組について片方のみでよい)。

斜めについて $6$ マスに達してないのにYesにしてしまうというミスで4WAしました...

D - Sequence Query (400点)

$k$ は高々 $5$ であるので、std::multisetやstd::mapで管理したとき、イテレータの移動が高々 $5Q$ 回なので、間に合います。
前にbegin()を超えるかよりも後ろにend()を超えるかを判定する方が楽だったりするので、 $c_i = 2$ のクエリについては全体に $-1$ を掛けたもので行うと少し楽になるかも(人に依る?)。

std::multisetでbegin()やend()を超えて操作を行ってしまったコードを出してしまい、1TLEしてしまいました...

E - Putting Candies (500点)

ダブリングを行います。

${\mathrm{dp}}_{i,j} = (\text{$X=i$ から $2^j$ 回の操作を行った後の飴の個数})$

とします。このとき $N$ で割った時の商と余りに注目することで

${\mathrm{dp}}_{i,j} = \left\{ \begin{array}{ll} i + A_i & (j = 0)\\ \displaystyle \left\lfloor \frac{{\mathrm{dp}}_{i,j-1} }{N} \right\rfloor N + {\mathrm{dp}}_{{({\mathrm{dp}}_{i,j-1} \mod N)},j-1}& (j \neq 0) \end{array} \right.$

となるので、 $K$ を二進数で表した時、 $1$ である桁を下から $s_1,\,s_2,\,\dots,\,s_n$ とした時、最初 $a = 0$ として $i$ を $1$ から $n$ へ順に

$a \leftarrow \displaystyle \left\lfloor \frac{a }{N} \right\rfloor N +{\mathrm{dp}}_{{(a \mod N)},s_i}$

を繰り返して、最終的な $a$ が答えとなります。
本番では各DPの値は (商, 余り) の組として実装しました。

F - Skate (500点)

$H$ も $W$ も最大で $10^9$ まで取りえるので、全てのマスについて調べることはできません。しかし、途中で立ち寄ることができるマスは障害物の上下左右いずれかの隣接マスのみなのでスタート地点を入れても高々 $4N + 1$ 箇所です。そのため、これらの限定した頂点についてのBFSで答えを求めることができます。
ぶつかる障害物についてはstd::map<int, std:::vector>での二分探索によって求めることができます。