CODE THANKS FESTIVAL 2018 参加記

11/25にCODE THANKS FESTIVAL 2018に参加してきました。

www.recruit-jinji.jp

予選

予選A: ABCを解いて114位
予選B: ABCを解いて183位

ほどほどな結果でTHANKS通過権を手に入れました。（来年こそは本戦に行きたい！）

過去のcodefes歴は

2016年：本戦通過（この年は本戦枠が上位200位だった）
2017年：THANKS通過 → 参加記

です。

当日

来た #code_festival pic.twitter.com/tnnpTvzxHG
— Ark (@arkark_) 2018年11月25日

会場は、昨年と同じくコワーキング・スペースMONOでした。

開会

いつものかっこいいオープニングからスタートでした。codefesに来たんだと実感させる安心感。

開会後は昼食を食べてからコンテストまで待機。

また、chokudaiさんからAtCoderステッカーをいただきました！ありがとうございますm(_ _)m

わーい！ pic.twitter.com/bNLJkLUl1l
— Ark (@arkark_) 2018年11月25日

コンテスト

CODE THANKS FESTIVAL 2018 | Atcoder
- parallelはこっち

参加者100名のうち上位50位に入れば、パーカーGETです。今までの「○○点以上」の絶対評価から、相対評価に変更されました。コンテスト終了まで確定しないし、競争感があっていいですね。

以下、各問題の自分の考察と解法。

A - Two Problems (100)

ifで場合分けして、可能性のある最大得点を出力するだけ

Submission #3662140

B - Colored Balls (200)

入力 $X, Y$ に対し

$\begin{cases}3a + b = X \\ a + 3b = Y\end{cases}$

を満たす非負整数の組 $(a, b)$ が存在するかを判定する問題。

$a,b$ に関して連立方程式を解くと

$\begin{cases}a = \frac{3X - Y}{8} \\ b = \frac{3Y-X}{8}\end{cases}$

となるので、 $3X - Y$ と $3Y-X$ が「 $8$ で割り切れるか」と「非負であるか」をチェックすれば良い。

Submission #3662638

C - Pair Distance (300)

\begin{aligned} \sum_{i=1}^N \sum_{j=1}^{i-1} \mathrm{abs}(x_i - x_j) \end{aligned}

を求める問題。ただし $N \leq 10^5$ なので愚直にやると間に合わない。

まずは ${x_i}$ を昇順にソートして、ソート結果を ${y_i}$ とすると

\begin{aligned} \sum_{i=1}^N \sum_{j=1}^{i-1} (y_i - y_j) \end{aligned}

を求めることと同値となり、absが取れて嬉しい。

あとは式変形をすると

\begin{aligned} & \sum_{i=1}^N \sum_{j=1}^{i-1} (y_i - y_j)\\ =& \sum_{i=1}^N \sum_{j=1}^{i-1} \sum_{k=j}^{i-1} (y_{k+1} - y_k) \\ =& \sum_{i=1}^N \sum_{k=1}^{i-1} \sum_{j=1}^{k} (y_{k+1} - y_k) \\ =& \sum_{i=1}^N \sum_{k=1}^{i-1} k (y_{k+1} - y_k) \\ \end{aligned}

ここで

\begin{aligned} t_i := \sum_{k=1}^{i-1} k (y_{k+1} - y_k) && (i=1,\cdots, N) \end{aligned}

とおくと

\begin{aligned} t_i = \begin{cases} 0 & (i = 1)\\ (i - 1)(y_{i} - y_{i-1}) + t_{i-1} & (i > 1) \end{cases} \end{aligned}

となるので、この漸化式を元に $t_i$ を累積しつつ答えを計算することで $O(N)$ を達成する。前処理のソートを考慮すると全体で $O(N\log N)$ となり、間に合う。

Submission #3663119

D - Concatenation (300)

これは前方から貪欲に計算するだけ。B,Cよりもかんたんな気がする・・・

Submission #3663290

E - Union (400)

DP問題。

dp[i][j]： $0$ から $i$ までの整数を見たときに、 $0$ から $i-1$ までの整数が $0$ 個となり、整数 $i$ が $j$ 個となるような場合の数

とおいて、遷移に従ってDPを更新する。

$j$ は $300 + 300/2 + 300/2/2 + \cdots \lt 600$ くらい確保しておけば安全。また、通常 $i$ は $N$ 以下であるが、入力列「 $a_1, a_2, \cdots, a_N$ 」を「 $a_1, a_2, \cdots, a_N, 0, 0, \cdots$ 」の無限列に拡張すれば、末端を気にせずDP更新ができて、実装が楽。コンテスト中は念の為 $i\leq 1000$ で多めに確保した。