Ark's Blog

数学とか競プロとか参加記とか備忘録とか

ようこそ

CODE THANKS FESTIVAL 2018 参加記

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

www.recruit-jinji.jp

予選

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

過去のcodefes歴は

  • 2016年:本戦通過(この年は本戦枠が上位200位だった)
  • 2017年:THANKS通過 → 参加記

です。

当日

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

開会

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

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

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

コンテスト

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

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

A - Two Problems (100)

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

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 - Y3Y-Xが「8で割り切れるか」と「非負であるか」をチェックすれば良い。

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)となり、間に合う。

D - Concatenation (300)

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

E - Union (400)

DP問題。

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

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

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

f:id:ark4rk:20181127232931p:plain この時点で、なんとABCDE早解き3位でした。・・・が、FGHが解けず、残り時間は座る人をやっていました(´・ω・`)

ACは取れなかったけど、コンテスト中での考察は以下のとおりです。

F - Coins on the tree

辞書式順序なので、小さいものから貪欲に確定していけば最終的な答えが得られそう!でも「ちょうどK回の操作」の制限がうまく解法に乗っかからなかったので断念。(解説によれば、うまく帳尻が合うとのことでなるほど〜となったけど、そこまで考えられなかった)

G - Sum of Cards

 b_i = a_iとなるペアをつなげると、サイクル分解みたいになって幸せそうとか考えてた。(解説によれば、この考察は的を得ていたようなので、あと一歩という感じ。自分はまだDPの構築が苦手だなと思う。)

H - Median Game

なにもわからなかった・・・ゲーム問題への苦手意識があるので良くない。 (解説によれば、中央値なので二分探索に帰着でき、なるほどなあとなった。)

結果

100人中18位でした!パーカーをゲットしました!かなり奮闘できたんじゃないかと思う。

f:id:ark4rk:20181127233902p:plain

途中まで3位で舞い上がってたんだけど、結局むずかしい問題が解けずに終わってしまった。私は今、青コーダーなんですが、F,G,Hあたりが解けるようになれば黄色になれる気がするので解けるように精進したい。

解説&懇親会

コンテスト後はchokudaiさんによる解説と懇親会がありました。

色々楽しめました!

感想

THANKSはもちろんたのしかったけど、やっぱり来年こそは本戦に出場したいです。競プロ力をあげたい。

運営の方々ありがとうございました!!!

追記

帰宅後にF,G,Hを解きました。

Gは、計算量的にぎりぎりなので、遅い言語だときびしいんじゃないかな