AtCoder Beginner Contest 175をPythonで解く-Shinoryo's Weblog

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 175を, Pythonで解いてみた結果を書き連ねていこうと思います.

A - Rainy Season

$\left| S \right| = 3$なので, 3連続から順にif文で分類していくことで解けます.

もちろん, 3文字に限らないようにコーディングすることもできます.

itertools.combinations()で, リストからある数だけ取り出す組み合わせを列挙します. 今の場合, 配列$L$(小さい順にソート済)から3つ$i$, $j$, $k$を選ぶ組み合わせを列挙します. そして, 以下の条件を全て満たすものを数えます.

$X$は絶対値を考えていいので, 始めにabs(X)として絶対値にしてしまいます.

$X$を$D$で割った商を$T$とします.

$K < T$ならば, $X - D \times K$が答えです.
$K \geq T$ならば,
- $K - T$が偶数ならば, $A = X - D \times T$が答えです(原点をはさんで往復移動すれば元に戻ってこれます).
- $K - T$が奇数ならば, $D - A$が答えです(原点を挟んで1回負に移動した点の座標の絶対値が答えになります).

この問題においては, 上の図のように, 移動は置かれたマスの属するサイクル上でのみ行われます. これを念頭に置いておきます.

各マス始まりということでループをして($N$マスに対して), それぞれのマスから始まるサイクルを調べます. そして何回移動するか(最小で$1$回, 最大で$K$回)でまたループをして, それぞれの場合の得点を調べます.

対称性より, サイクルのマスの総数より大きい回数は調べなくてよいです. サイクルを周回した方が得点合計が大きくなる可能性をまとめて考慮することができます.

ちなみに, Python3.8だとTLEとなってしまいましたが, PyPy3だとACでした. やっぱりよく分からないですね.

E以降は私の能力不足故に省略いたします.