人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

diverta 2019 Programming Contest:D - DivRem Number

問題

atcoder.jp

解法

問題文中の条件を式にあらわすと,N = k(m + 1) となる.よって,k を 1 <= k <= √N の範囲で動かし,条件を満たすような m を探せばよい.O(√N).

解答

atcoder.jp

f:id:babcs2035:20190512102228p:plain

 

diverta 2019 Programming Contest:C - AB Substrings

問題

atcoder.jp

解法

まず,各 s_i 中に含まれる "AB" の数を答えに加算する.これは,どういう順番で文字列を結合させても "AB" はそのままになるから.

問題は各 s_i の最初の 1 文字と最後の 1 文字をどう組み合わせていくかになる.よって,この 2 つの間の文字列は結合によって生じる "AB" に関与しない.文字列の結合によって新しく生じる "AB" の数は,max('B' が最初に現れる回数, 'A' が最後に現れる回数) となる.しかし,これら 2 つの回数に関与する文字列が全て "BA" であった場合,答えから -1 する必要がある.なぜならば,環状に文字列をつながない限り不可能であるから.O(N * |S|).

解答

atcoder.jp

f:id:babcs2035:20190512101754p:plain

 

CPSCO2019 Session3:F - Flexible Permutation

問題

atcoder.jp

解法

dp(i, a, b) := 1 ~ i までの全ての順列のうち,P_k > k となるような k の個数が a,P_k < k となるような k の個数が b である通り数

を考える.1 ~ i - 1 までの順列に新しく i を追加するとき,1 ~ i - 1 までの順列の末尾に i を追加し,追加した i をそのままにするか,任意の箇所と swap することで,1 ~ i の任意の順列を作ることが出来る.

ここで,swap する相手の箇所 k が P_k > k であるのか,P_k < k であるのか,P_k == k であるのかを場合分けして考える.swap する場合,P_k < i かつ P_i > k であるので,P_k > k であるとき,swap すると b が 1 増える.P_k < k であるとき,swap すると a が 1 増える.P_k == k であるとき,swap すると a と b がともに 1 増える.swap しない場合はともに変化しない.これらを DP の遷移とすると,

dp(i, a, b) = dp(i - 1, a, b - 1) * a + dp(i - 1, a - 1, b) * b + dp(i - 1, a - 1, b - 1) * (i - 1 - (a - 1) - (b - 1)) + dp(i - 1, a, b)

となる.O(N^3).P_k == k となるような k を組み合わせ計算で決め打ちしておき,N == A + B とすることで O(N^2) に落とすこともできる.

解答

atcoder.jp

f:id:babcs2035:20190505223143p:plain

 

AtCoder Grand Contest 033

結果

6 問中 2 問正解(900 / 6400 点, 22:30),1288 位中 486 位,パフォーマンス 1787,新レート 1567 (+27).A, B 問題を早解き出来たのはよかったが,C 問題と通せず終わってしまったためパフォーマンスがあまり伸びなかった.

f:id:babcs2035:20190505164137p:plain

f:id:babcs2035:20190505164144p:plain

f:id:babcs2035:20190505164149p:plain

A - Darker and Darker

babcs2035.hateblo.jp

B - LRUD Game

babcs2035.hateblo.jp

AtCoder Grand Contest 033:B - LRUD Game

問題

atcoder.jp

解法(嘘)

上下と左右はそれぞれ独立に考えられる.なので,先手が上下左右のうち 1 方向を決めて,その方向に貪欲に動かしていき,もう一方がその逆の方向に貪欲に動かしていくという操作を各方向シミュレーションすると,先手がマス目から落とすことが出来るかどうかを判定することが出来る.O(HW + N).

解答

atcoder.jp

f:id:babcs2035:20190505163215p:plain

 

AtCoder Grand Contest 033:A - Darker and Darker

問題

atcoder.jp

解法

問題文中の「辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる」は「黒色のマスと辺を共有して隣接する白色のマスが黒色になる」と言い変えられるので,全ての黒色のマスから BFS をすれば各白色のマスが黒色になるまでに必要な操作の回数が得られる.答えは各白色のマスに必要な操作の回数の max となる.O(HW).

解答

atcoder.jp

f:id:babcs2035:20190505162723p:plain

 

CPSCO2019 Session3:E - Enumerate Xor Sum

問題

atcoder.jp

解法

各 k ごとに考える.

A_1 ~ A_k までの XOR は累積和的に計算できる.この XOR を bit の桁ごとに見ていく.XOR の i bit 目が 1 のとき,A_1 ~ A_k それぞれの i bit 目が反転される.よって,A_1 ~ A_k それぞれの i bit 目が 1 である個数を cnt_i とすると,答えに 2^i * (k - cnt_i) が加算される.また,XOR の i bit 目が 0 のとき,A_1 ~ A_k それぞれの i bit 目はそのままになる.よって,答えに 2^i * cnt_i が加算される.これを各 i について計算すれば各 k について答えが求まる.cnt も累積和的に計算することが出来るので,全体で O(N * logA_max).

解答

atcoder.jp

f:id:babcs2035:20190505161348p:plain

 

CPSCO2019 Session3:D - Decode RGB Sequence

問題

atcoder.jp

解法

"RB" や "GG" と並ぶことはない.また,R は N - 1, N 文字目,G は 1, N 文字目,B は 1, 2 文字目に来ることはない.これらの条件のうち 1 つでも当てはまれば答えは No, すべてクリアしていれば Yes となる.O(N).

f:id:babcs2035:20190505160608p:plain

解答

atcoder.jp

CPSCO2019 Session3:C - Camp Reception

問題

atcoder.jp

解法

受付しなければいけない人がいる時間帯の区間の数が知りたいので,imos 法を用いて「ある時間 t に受付しなければいけない人がいるか?」を O(1) で知れるように前計算しておく.あとは,受付しなければいけない人が連続している区間を O(N) かけて数えればよい.全体で O(N).

解答

atcoder.jp

f:id:babcs2035:20190505155858p:plain

 

yukicoder:No.826 連絡網

問題

yukicoder.me

解法

P = 1 または N / 2 より大きい素数のとき答えは 1.なぜならば,前者は自明で,後者は 2 * P が N を超えてしまうため,1 ~ N の数の中で 2 と P をかけて合成数を作ることが出来ないから.

そうでないとき,家 i(i は N / 2 以下の素数)は家 P(P は N / 2 以下の素数,または,N 以下の合成数)と連結になることが出来る.なぜならば,家 i は家 2 * i (<= N) と連結であり,家 2 * i は家 2 と連結であるので,家 i は家 2 と連結になる.一方,家 P は家 i と同じ原理か,P 自体が合成数であるので(合成している数で一番小さい数は必ず N / 2 以下であるので)家 2 と連結である.なので,家 i と家 P は連結になる.また,家 j (j は N 以下の任意の合成数) も同様に家 P と連結になる.よって,答えは N - (N / 2 より大きい素数の数) となる.O(N√N).

解答

yukicoder.me

f:id:babcs2035:20190505145140p:plain