人権なし

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

2019-05-05から1日間の記事一覧

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 までの順…

AtCoder Grand Contest 033

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

AtCoder Grand Contest 033:B - LRUD Game

問題 解法(嘘) 解答 問題 atcoder.jp 解法(嘘) 上下と左右はそれぞれ独立に考えられる.なので,先手が上下左右のうち 1 方向を決めて,その方向に貪欲に動かしていき,もう一方がその逆の方向に貪欲に動かしていくという操作を各方向シミュレーションす…

AtCoder Grand Contest 033:A - Darker and Darker

問題 解法 解答 問題 atcoder.jp 解法 問題文中の「辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる」は「黒色のマスと辺を共有して隣接する白色のマスが黒色になる」と言い変えられるので,全ての黒色の…

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 …

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). …

CPSCO2019 Session3:C - Camp Reception

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

yukicoder:No.826 連絡網

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