水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder で青になるまでにやったこと

青コーダーになりました!!!

前日に 200 - 800 (300) - 1000 - 1000 - ... という初心者お断りな配点が発表された AtCoder Grand Contest 030,A と B 部分点でパフォーマンス 2000 越えをし,青コーダーになることが出来ました.1年半以上の間水色コーダーとして停滞していたので素直に嬉しく喜びたいですが,着水(水色落ち)は許されないと考えると気を抜けないなと思います.どうもありがとうございました.

f:id:babcs2035:20181229234857p:plain

f:id:babcs2035:20181229235214p:plain

水色から青になるまで

AtCoder300 - 500 点問題を解きまくりました.ただ,1回 AC して満足してしまうとなかなか実力が思ったように伸びず,レートも停滞気味になってしまいました(上のレート遷移グラフでの2度のスランプはこれを特に示すものです).また,学業が忙しくなり,レートを上げる機会であるコンテストに,高1に入って以降,あまり出れなくなりました.なので,2018 年 9 月以降は 400 - 500 点問題の解きなおしを中心に進め,出れなかったコンテストは AtCoder Virtual Contest などを活用して後からでも解くようにしました.偉そうに書いていますが,これからもこれを続ける,あるいは,より精進をしなければ着水は避けられないと自戒しているところです.

これからの目標

コンテストにもっと出るようにします.これは,配点が AGC 030 のように鬼畜であっても出るようにします.とにかく出るようにします(したいです,定期考査や模試前は流石に出れませんが...).

500 - 600 点問題を解けるように精進します.そうでないと,着水は避けられず,大きなスランプに陥る可能性が十分出てきます.

2019 年中にレート 1800 ~ 2100 を目指します.高2は益々学業も忙しくなりそうですが,競プロも何とか両立してやっていければと思っています.

これからもどうぞよろしくお願いします.

 

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019

結果

6問中4問正解(1200 / 2700 点, 115:24),1986 位中 405位,パフォーマンス 1750,新レート 1652 (+11, Highest).目標であった4問正解を達成できたのでよかったが,D 問題を通すのが極めて遅くなってしまったため,あまりパフォーマンスが伸びず,レートも微増にとどまった.考察力をつけてもっと早く通せるようにしたい.

f:id:babcs2035:20190113234605p:plain

f:id:babcs2035:20190113234611p:plain

f:id:babcs2035:20190113234620p:plain

f:id:babcs2035:20190113234625p:plain

A - Beginning

atcoder.jp

B - KEYENCE String

atcoder.jp

C - Exam and Wizard

babcs2035.hateblo.jp

D - Double Landscape

babcs2035.hateblo.jp

 

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019:D - Double Landscape

問題

atcoder.jp

解法

各マス (i, j) に書くことが出来る数字の最大値を max_(i, j) とする.また,数字 i が書くことが出来る数字の最大値になっているマスの個数を cnt_i とし,数字 i を書く時点で書くことが出来るマスの総数を avail_i とする.

前処理として,A_i == B_j を満たす (i, j) の組が存在した場合,数字 A_i (B_j) はマス (i, j) に書くしかない.なぜならば,もしマス (i, j) 以外に書いたら必ず条件に反してしまうから.このような数字の集合を kotei とする.

また,kotei に属さず,A_i, B_j に表れている数字の集合を must とする.must のそれぞれの要素について,A_i を書き込むことのできるマスは A_i < B_j を満たすマス (i, j),B_j を書き込むことのできるマスは B_j < A_i を満たすマス (i, j) であるので,各 must の要素について書き込める先のマスの個数を数えておく.このような数字 i を書き込める先のマスの個数を musts_i とおく.

数字を N*M ~ 1 の順番に書いていくことを考える.書き込む数字を i (N*M >= i >= 1) とおく.まず,avail_i に cnt_i を加える.これは新しく cnt_i 個のマスに書くことが出来ようになったということを意味する.

ここで,i が kotei に属しているならば,i を書き込むマスの場所の通り数は1通りである.i が must に属しているならば,通り数は musts_i 通りである.もし,i がこの2つのどちらにも属していないならば,avail_i 個のマスのどこでも書き込んで良いので avail_i 通りである.i + 1 への遷移する際,avail から 1 を忘れずに引く(i を書き込んだ先のマスを引く必要があるため).全部で O(NMlogNM).解法・実装を工夫すれば O(NM).

解答

atcoder.jp

一発 AC 出来たのでよかった.考察にものすごく時間がかかった.

f:id:babcs2035:20190113233650p:plain

 

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019:C - Exam and Wizard

問題

atcoder.jp

解法

まず,A_i < B_i の状況であるものは必ず A_i を B_i まで上げる必要があるのでこれらは答えの個数に加わる.

上げる必要がある準備度の総和を sum とし,準備度が十分であるものの余剰分(B_i - A_i)を降順ソートしたものを D とすると,

D_1 + D_2 + ... + D_k >= sum

となる最小の k を知れればよいとなる.この k を 1 ~ N について確かめていき求めればよい.答えは (必ず準備度を上げなければいけない試験の数) + k になる.O(NlogN).

解答

atcoder.jp

一発 AC 出来たのでよかった.比較的簡単目な 400 点問題だと感じた.

f:id:babcs2035:20190113231604p:plain

 

AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

結果

5問中3問正解(600 / 1700 点, 39:10),1970 位中 420 位,パフォーマンス 1696,新レート 1641 (+6, Highest).何とかレート Highest 更新出来たが,D 問題を WA が多発し,通せなかったのが悔しい.バグらせていると考えられるので,実装力を付けなければいけないと感じた.

f:id:babcs2035:20190112233127p:plain

f:id:babcs2035:20190112233135p:plain

f:id:babcs2035:20190112233141p:plain

f:id:babcs2035:20190112233149p:plain

A - Bulletin Board

atcoder.jp

B - Contests

atcoder.jp

C - Alternating Path

atcoder.jp

 

CODE THANKS FESTIVAL 2018:F - Coins on the tree

問題

atcoder.jp

解法

問題文の条件より,i 枚目のコインをある頂点 v に置くと決めた場合,(i + 1) 枚目以降のコインを頂点 v とその子孫の頂点に置くことが出来なくなる.よって,1 枚目のコインから順に置く場所を決めていく.

(i - 1) 枚目のコインまでで S 回操作したとき,i 枚目のコインをある頂点 v に置くことを考える.このときにかかる操作の回数は (頂点 v の深さ) + 1 になる(根の深さを 0 とする)ので,i 枚目のコインまでの操作の回数は (S + depth_v + 1) になる.

このとき,(i + 1) 枚目のコイン以降で操作しなければならない回数は (K - S - depth_v - 1) になる.この回数が多すぎると全てのコインを置いても操作の回数が余ってしまい,少なすぎると全てのコインを置くことができなくなってしまう.この判定は,少なくとも (i + 1) 枚目のコイン以降で操作しなければいけない回数を minSum,多くても (i + 1) 枚目のコイン以降で操作しなければいけない回数を maxSum とすると,

minSum <= (K - S - depth_v - 1) <= maxSum(*)

を満たすかどうかで可能.minSum は深さが小さい頂点 (M - i) 個,maxSum は深さが大きい頂点 (M - i) 個それぞれにコインを置くのにかかる操作の回数の合計になる.

以上のことを踏まえて,各 i についてその時にコインを置くことが可能である頂点の中から(*)の条件式を満たす最小の v を探せばよい.もし,このような v が1つも無い場合に答えは -1 になる.O(M * N^2).

解答

atcoder.jp

一発 AC 出来たのでよかった.

f:id:babcs2035:20190108204517p:plain

 

Educational DP Contest / DP まとめコンテスト

結果

26 問中 12 問正解(1200 / 2600 点, 216:15),1124 位中 252 位.AC した問題は全て WA を出さずに通せたのでよかった.間で解けない問題がありパスしてしまった.

f:id:babcs2035:20190107174148p:plain

f:id:babcs2035:20190107174157p:plain

A - Frog 1

babcs2035.hateblo.jp

B - Frog 2

babcs2035.hateblo.jp

C - Vacation

babcs2035.hateblo.jp

D - Knapsack 1 

babcs2035.hateblo.jp

E - Knapsack 2 

babcs2035.hateblo.jp

G - Longest Path 

babcs2035.hateblo.jp

H - Grid 1 

babcs2035.hateblo.jp

I - Coins 

babcs2035.hateblo.jp

K - Stones 

babcs2035.hateblo.jp

L - Deque

babcs2035.hateblo.jp

M - Candies

babcs2035.hateblo.jp

P - Independent Set 

babcs2035.hateblo.jp

 

Educational DP Contest:P - Independent Set

問題

atcoder.jp

解法

dp(i, f) := 頂点 i を黒で塗れるかどうかが f のとき,頂点 i から到達できる頂点を塗り分ける通り数

と定義する.このとき,

dp(i, f) = dp(v_1, true) * dp(v_2, true) * ... (f == false のとき)

dp(i, f) = dp(v_1, false) * dp(v_2, false) * ... + dp(v_1, true) * dp(v_2, true) * ... (f == true のとき)

(v は頂点 i から直接行ける頂点)

と漸化式が立つ.状態数 O(N),遷移 O(N) だけれども,各辺は1回しか見ないので O(N + N).

解答

atcoder.jp

実装に関して,無限ループを避けるため,親の頂点を dp の引数に持ちながら dp すればよい.

f:id:babcs2035:20190107173548p:plain

 

Educational DP Contest:M - Candies

問題

atcoder.jp

解法

dp(i, j) := i 人目までで j 個分けるときの通り数

と定義する.このとき,

dp(i, j) = dp(i - 1, j) + dp(i - 1, j - 1) + ... + dp(i - 1, j - a_(i - 1))

dp(i, j) = 1 (j == 0 のとき)

dp(i, j) = 0 (j < 0, i == 0 のとき)

と漸化式が立つが,これでは遷移が O(a_i) となってしまい TLE になってしまうので,漸化式の置き方を工夫することで,

dp(i, j) = dp(i - 1, j) + dp(i, j - 1) - dp(i - 1, j - a_(i - 1) - 1)

と遷移が O(1) に抑えることが出来る.O(NK).

解答

atcoder.jp

mod を取る系の数え上げはこうした漸化式を工夫して変形させるテクが使えるらしい.

f:id:babcs2035:20190107172741p:plain

 

Educational DP Contest:L - Deque

問題

atcoder.jp

解法

dp(i, j, k) := 数列 a_i ~ a_j の中で k が操作するときの (X, Y) の値

と定義する.このとき,

dp(i, j, k) = ( dp(i + 1, j, (k + 1) % 2).X + a_i, dp(i + 1, j, (k + 1) % 2).Y ) か ( dp(i, j - 1, (k + 1) % 2).X + a_j, dp(i, j - 1, (k + 1) % 2).Y ) のうち最適なもの (k が太郎のとき)

dp(i, j, k) = ( dp(i + 1, j, (k + 1) % 2).X, dp(i + 1, j, (k + 1) % 2).Y + a_i ) か ( dp(i, j - 1, (k + 1) % 2).X, dp(i, j - 1, (k + 1) % 2).Y + a_j ) のうち最適なもの (k が次郎のとき)

dp(i, j, k) = (0, 0) (j < i のとき)

と漸化式が立つ.状態数 O(N^2),遷移 O(1) となり O(N^2).

解答

atcoder.jp

dp の値を std::pair<LL, LL> とおいたので重くなった.

f:id:babcs2035:20190107172221p:plain

 

Educational DP Contest:K - Stones

問題

atcoder.jp

解法

dp(i, j) := 石が i 個あり操作するのが j のとき,j が勝てるかどうか

と定義する.このとき,残りの石の状態のうちどれかが相手を負けにすることが出来るならば,自分を勝ちにできることを踏まえると,

dp(i, j) = !dp(i - a_1, (j + 1) % 2) OR !dp(i - a_2, (j + 1) % 2) OR ... !dp(i - a_k, (j + 1) % 2) (a_k <= j)

と漸化式が立つ.状態数 O(K),遷移 O(N) になり O(NK).

解答

atcoder.jp

「相手を負けにする ⇔ 自分を勝ちにする」を利用する.

f:id:babcs2035:20190107171457p:plain