問題 解法 解答 問題 beta.atcoder.jp 解法 lcm(7, m) のマスは 0 のマスと塗られているかどうかは同じになるので，lcm(7, m) - 1 のマスまでマス目を塗るシミュレーションをすれば十分．縦 lcm(7, m) / 7 マス，横 7 マスの表を S と置く．S の下に新しく S…

問題 解法 解答 問題 beta.atcoder.jp 解法 A, B の "(" , ")" の数がそれぞれ |S| / 4 になっていればよい．S を先頭から見ていくとき，S を真ん中で半分にして考える． 前半分のとき， S_i == "(" で A の "(" が不足しているとき：A += "(" S_i == "(" で…

問題 解法 解答 問題 beta.atcoder.jp 解法 ある要素を inf にした場合，答えは２つに分けられた数列のそれぞれの中で完結する要素の総和が０である部分列の数の和になる．そこで，２つに分ける箇所を全探索し，それぞれについて前後の数列に当てはまる部分…

問題 解法 解答 問題 beta.atcoder.jp 解法 王都から各都市に行ったならばすぐに王都に戻るのが最適であるので，M 個の依頼からすぐにまた王都に戻ってくる時刻を１つに定められる．なので，２種類の依頼を１つにまとめてしまうことで，最大スケジューリング…

問題 解法 解答 問題 beta.atcoder.jp 解法 何回目に操作が終了するかで場合分けをする．k 回目に操作が終了する確率は (n / n) * ( ( n - 1 ) / n) * ( ( n - 2 ) / n) * ... * ( ( n - ( k - 2 ) ) / n) * ( ( k - 1 ) / n) になる．k 回目までのさいころ…

問題 解法 解答 問題 beta.atcoder.jp 解法 (x, y) の組をグラフ上の１つの頂点に対応させて考える．(x, y) に１回操作してなる数の組 (tx, ty) から (x, y) に辺を張る．そうすると，(x, 0) と (0, y) から到達できる組はいつか操作が終了する組だと分かる…

問題 解法 解答 問題 beta.atcoder.jp 解法 問題を読むと DP という気持ちになるので，以下のように DP を定義する： dp(i, f) := i 番目の要素まで見たときの最大値（f が true の時，効用を０にすることが可能で，f が false の時，効用を０に出来ない） f…

問題 解法 解答 問題 beta.atcoder.jp 解法 偶数行・列の長さの累積和と奇数行・列の長さの累積和の２つを計算しておく．そうすれば，各クエリにおいて座標が (偶数，偶数) と (奇数，奇数) の黒マスの面積の合計が O(1) で計算でき，この２つを足し合わせれ…

結果 A - Measure B - Exchange C - Align 結果 ３完（700 点・80:31），1389 位中 248 位，レート変動無し．途中参加になってしまったので Beginner の方に参加した．C 問題を一発 AC 出来たのはよかった． A - Measure beta.atcoder.jp B - Exchange beta.…

問題 解法 解答 問題 beta.atcoder.jp 解法 小さい数，大きい数，小さい数，... のように並べていくのが最適だと分かるので，隣り合う要素の差の合計の式を書くと， (a_2 - a_1) + (a_2 - a_1) + ... + (a_(n-1) - a_n) になる．ここで，両端の要素を除いた …

問題 解法 解答 問題 beta.atcoder.jp 解法 N 個の建物から K 個選び，それらを左から高さが増加していくようにすることを考える．制約より，選び方を bit 全探索する．i 番目の建物の前までの max を前計算で求めて置き，K 個選んだあとは，前計算の結果も…

問題 解法 解答 問題 beta.atcoder.jp 解法 好きな曲の BPM の範囲は，[140, 170), [280, 340), ... と両端の数値が２倍ずつ増えていき変化する．よって，BPM の範囲を全て列挙し，それぞれの範囲と [L, R) の共通範囲の個数を計算し，それらの和を求めれば…

問題 解法 解答 問題 beta.atcoder.jp 解法 ある連続する区間積が P になればよいので，この連続する区間が数列 A にあるかどうかを判定すればよい．尺取り法を使って考えると，区間積が P より大きくなったら左端を縮める，P より小さくなったら右端を伸ば…

問題 解法 解答 問題 beta.atcoder.jp 解法 まず，「よい文字列」が存在するときその長さは lcm(N, M) になるのは自明．なぜなら，lcm(N, M) の倍数で考えても見るべき X の場所の組は変わらないから． 長さを固定できたので，あとは構成した X が条件に当て…

問題 解法 解答 問題 beta.atcoder.jp 解法 「ゾンビ島」（ JOI 2015/2016 予選 問題５ ）にめちゃくちゃ似ている（というかほぼそのまま）． イノシシがいるマスから BFS で各マスのイノシシのいるマスまでの最短距離を調べる．ここで，最短距離が X 以下で…

問題 解法 解答 問題 beta.atcoder.jp 解法 １円，10 円，100 円の順番に分ける枚数を決めていく．この時，各硬貨の枚数が偶数になれば条件を満たす．ここで，各硬貨の枚数に mod 20 をとる．なぜならば，１つ上の硬貨に位上げしても，位上げの枚数は必ず偶…

問題 解法 解答 問題 beta.atcoder.jp 解法 0 ~ L - 1 の長さのパスを作りたいのだから，とりあえず長さ 2^0, 2^1, 2^2, ... , 2^20 の辺を張っておきたいと考える（2^20 までなのは，2^20 > 10^6 であるから）（log2(10^6) が大体 20 なので制約から察する…

問題 解法 解答 問題 beta.atcoder.jp 解法 まず，それぞれの到達させたい点と原点の距離の偶奇が一致することを確かめる．一致しなければ，どんなに頑張っても不可能． それぞれの到達させたい点と原点の距離の偶奇が一致するとき，ロボットの腕の長さを 2^…

問題 解法 解答 問題 beta.atcoder.jp 解法 奇数個のコインがあるマスから (1, 1) -> ... -> (1, W) -> (2, W) -> ... -> (2, 1) -> ... のように他の奇数個のコインがあるマスにコインを移していく．これをやると，最小でも HW - 1 個は偶数個にすることが…

結果 C - /\/\/\/ D - Robot Arms E - Tr/ee 結果 １完＋部分点（1 WA, 53:25），978 位中 451 位，パフォーマンス 1647，レート 1542 (+12, Highest)．C 問題で WA をし，正解するのが遅くなってしまったのが痛かった．また，もう少し早い段階で D 問題の部…

問題 解法 解答 問題 C - /\/\/\/ 解法 数列の奇数個目と偶数個目で新しく数列を２つつくり，それぞれの中で最も多く登場する要素の数を N / 2 から引いたものが答えになるが，これだと，それぞれ同じ数字が当てはまってしまう場合が考えうる．そのため，「…

結果 C - String Transformation D - Factorization 結果 D 問題を解き１完，1932 位中 940 位．400 点であった D 問題を解けたのはよかったが，C 問題が難しく解けなかった．D 問題より C 問題の方が難しいと感じた． C - String Transformation コンテスト…

結果 A - 配点 B - みかん C - 半分 結果 ２完，1136 位中 250 位．A, B 問題をスムーズに解けたのは良かったが，目標であった３完に届かなかったのが残念． A - 配点 Submission #3241070 - CODE FESTIVAL 2018 qual A B - みかん Submission #3241714 - CO…

問題 解法 解答 問題 D - Factorization 解法 M を素因数分解する．M の各素因数を N 個の箱に分けていくと考えればよい．このとき，単純に N ^ (各素因数の個数) を掛け合わせたものを答えにしてしまうと，重複が生まれてしまう．なので，重複組み合わせ H(…

問題 解法 解答 問題 C - String Transformation 解法 S -> T になるように各文字を置き換えるとき，S_i が T_i に対応するように１対１の関係になれば一致させることが出来る．逆に，１対１にならなければ一致させることは出来ない（１つのアルファベットを…

問題 解法 解答 問題 C - 半分 解法 「dp(i, j, f) := i 番目までで j 回操作するときの通り数（f := 今までの要素を 0 にしたかどうか）」で DP をする．f が true のとき，操作の回数が余ったとしても，どこか 0 である要素で余った回数を消費すれば良いの…

PCK に初めて出ました 競技前 競技直前 競技中 競技終了直後 競技終了後 予選通過チーム発表 本選 PCK に初めて出ました 高１になったので，高３の先輩と出ました（許可は得ていないので，名前を書くのはやめておきます）． 競技前 先輩と Discord でバチャ…

問題 解法 解答 問題 D - 高橋くんとマラソンコース N 個のチェックポイントが平面上の座標の点にあるとき，走者はチェックポイントを 1, 2, ... , N の順番に，チェックポイント間は最短距離になるように好きな経路を取る．このとき，「k 番目のチェックポ…

問題 解法 解答 問題 D - 見たことのない多項式 N 次多項式 P(x) があり，P(0), P(1), ... , P(N) が分かっているとき，P(T) を求める問題． 解法 さっぱり分からないので解説を読んだところ，ラグランジュ補間というものを使うらしいと分かった．これは，P(…

問題 解法 解答 問題 D - アットコーダーモンスターズ N 匹のモンスターには攻撃値と防御値がそれぞれ決まっていて，この中から K 匹選んでチームを作りたい．このチームの「不安定度」はチーム内のモンスター同士の攻撃値の差と防御値の差の min の max で…