#define long long long

akouryy's programming blog

Codeforces Round #341 (Div. 2): 1741 → 1849

  • こどふぉ4回目。目指せ1900。

codeforces.com

公式解説: Codeforces Round #341 (Div. 2) Editorial - Codeforces


IN()マクロを試用した。

A. Wet Shark and Odd and Even

奇数を0~1個使わない。やるだけ。  O(N)

Submission #15696444 - Codeforces

0:04:45

B. Wet Shark and Bishops

 X + Y X - Y をそれぞれカウントする。やるだけ。  O(N + X + Y)

Submission #15699364 - Codeforces

0:13:14

C. Wet Shark and Flowers

各隣接について独立な2確率のORを求める。やるだけ。  O(N)

Submission #15702869 - Codeforces

0:30:43

D. Rat Kwesh and Cheese

精度ゲー。logをとる。やるだけ失敗。  O(1)

Submission #15707898 - Codeforces

1:02:17

RubyのFloatはdoubleらしい。long doubleが必要な問題だった(それだけが原因じゃない)

後で通したやつ: Submission #15733632 - Codeforces

E. Wet Shark and Blocks

 A_i および  j \in \mathbb{Z} \cap [0, X) について、  m [(10 j + A_i) \bmod X ] [ j ] を1増やす。
たとえば、入力  A = \{2, 7, 10 \}; X = 8 とすると、  m = \begin{pmatrix}
0 &0 &0 &2 &0 &0 &0 &2 \\
0 &1 &0 &0 &0 &1 &0 &0 \\
2 &0 &0 &0 &2 &0 &0 &0 \\
0 &0 &1 &0 &0 &0 &1 &0 \\
0 &2 &0 &0 &0 &2 &0 &0 \\
0 &0 &0 &1 &0 &0 &0 &1 \\
0 &0 &2 &0 &0 &0 &2 &0 \\
1 &0 &0 &0 &1 &0 &0 &0 \\
\end{pmatrix} となる。
ちょっと考えると  m^B が答えになるとわかるので行列の繰り返し二乗法をする。  O( N + X^3 \log B )

Submission #15712992 - Codeforces

1:45:26

結果

Standings - Codeforces Round #341 (Div. 2) - Codeforces

順位 名前 得点 Hack A B C D E
89*1 syaro 4160 492 948 1320 (-1) 1400


rating: 17411849

行列の繰り返し二乗法をなんとか書けてよかった。

次こそ1900超えたい。

*1:Div.2内の順位