問題 解法 解答 問題 atcoder.jp 解法 頂点 X_1, X_2, ... , X_100000, Y_1, Y_2, ... , Y_100000 をおき，(x, y) に点があるとき頂点 x と y に辺を張ることを考える．こうしてできたグラフ上では長さが 3 のパスができる．このパスの始点と終点を新たに結…

問題 解法 解答 問題 atcoder.jp 解法 完全グラフにおいては最短距離が 2 であるような頂点の組み合わせは 0 通りになる．ここから辺を 1 本ずつ取っていくと，この頂点の組み合わせは 1 つずつ増えていく．よって，まず最初に完全グラフを作り，その後 K 本…

結果 A - Security B - Bite Eating C - Anti-Division D - Megalomania 結果 6 問中 4 問正解（1000 / 2100 点, 21:10），5060 位中 1007 位，パフォーマンス 1324，新レート 1524 (-20)．A - D 問題までを比較的早く通せたが，E 問題を最後まで通すことが…

問題 解法 解答 問題 atcoder.jp 解法 期限 B が小さいものから順に仕事をこなしていくのが最適になる．B を昇順にソートした後の A において，A_1 + A_2 + ... + A_i <= B_i ならば i 番目の仕事はクリアとなるので，この不等式の左辺をできるだけ小さくす…

問題 解法 解答 問題 atcoder.jp 解法 A - 1, B 以下の整数で C でも D でも割り切れない整数の数をそれぞれ求め，後者から前者を引けば答えになる．C でも D でも割れる数の扱いに注意する．O(1)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 取引所 A でいくつかのどんぐりを金属に変え，取引所 B で金属を全てどんぐりに変えていくつかのどんぐりを金属に変え，取引所 A で金属を全てどんぐりに変えるように行動すればよい．途中の取引所 B で金属を全てどん…

結果 A - Ball Distribution B - Picking Up C - Successive Subtraction 結果 6 問中 2 問正解（400 / 3200 点, 185:44），3470 位中 1820 位，パフォーマンス 904，新レート 1544 (-53)．A, B 問題で深刻な誤読をしてしまい，ペナルティーも時間も多くなっ…

問題 解法 解答 問題 atcoder.jp 解法 A の各要素の正負を反転させることを考える．全ての要素の正負を反転させたり，1 つも反転させないことは不可能．なぜならば，1 回以上の操作によって選ばれた 2 つの要素は x - y という形になり，最低 1 つは反転させ…

問題 解法 解答 問題 atcoder.jp 解法 まず，N^2 個（正確にはもっと少ない）ある (p, q) の組を全列挙する．その後，各 (p, q) の組について必要となるコストの回数を計算する．ある頂点 v から移動量が (p, q) または (-p, -q) であるような頂点 u があれ…

問題 解法 解答 問題 atcoder.jp 解法 a + b == a XOR b となるためには，a と b で任意の bit の桁が 1 と 1 になってはいけない．1 XOR 1 は 0 となるが，1 + 1 は 10 と繰り上がりが発生し a + b != a XOR b となってしまう． L の中で bit が立っている…

問題 解法 解答 問題 atcoder.jp 解法 各行・列について障害物がある x, y 座標をソートして配列に持っておく．これを前処理として行っておく． 各マスについて，そのマスから見て上下左右の最も近い障害物の座標は，前処理で求めておいた配列上で二分探索を…

問題 解法 解答 問題 atcoder.jp 解法 dp(i) := i 段目まで登る通り数 として DP を考える．通り数は i が「壊れている床」のとき 0 通り，そうでないときは dp(i - 1) + dp(i - 2) 通りとなる．O(N)． 解答 atcoder.jp

人権的な時間に開催された Codeforces コンテストのみに参加してきました．最初のころは競プロ自体になれていなかったためか，デフォルトのレートからかなり減少が続いていましたが，緑になってからは安定してレートを伸ばすことができました．Systest で落…

結果 A. Filling Shapes B. Plus from Picture C. Beautiful Lyrics 結果 ６問中２問正解（1070 点），5543 位中 1070 位，新レート 1620 (+33, Highest)．B 問題が Systest で落ちてしまったが，何とかレートをあげることができ，青コーダーになれたのでよ…

問題 解法 解答 問題 codeforces.com 解法 まず，同じ母音の数で分類する．その中で，最後の母音が同じもの同士を下の句のペアになれるものとしてまとめる（seconds とおく）．ここでまとめられなかったもの同士を上の句のペアになれるものとして別にまとめ…

問題 解法 解答 問題 codeforces.com 解法 十字架の中心部分をまず見つける．中心部分の条件は，自身と上下左右のマスが * であること．このようなマスを 1 つ見つけたら上下左右に連続する * を . に置き換えていく．この操作後，* が残っていれば NO，残っ…

問題 解法 解答 問題 atcoder.jp 解法 ある任意の頂点を 1 つ選び，その選んだ頂点からほかの全頂点との間の距離の偶奇で色を分ければよい．なぜならば，ある頂点 v, u と最初に選んだ頂点 r との距離がそれぞれ偶奇が等しければ， v -> r -> u の距離は当然…

問題 解法 解答 問題 atcoder.jp 解法 各さいころの目ごとに得点を K 以上にするために必要な確率を求め，1 / N と掛け合わせたものを合計したものが答えになる．コインが表が出続けなければならない回数は，得点が 2 倍されていく過程をシミュレーションす…

問題 解法 解答 問題 atcoder.jp 解法 "BC" という文字列は分断されたり "B" と "C" が独立して操作に影響を与えることはないので 1 つの文字に置き換えて考えてしまってよい．"BC" を "X" と置き換えると，問題文中の操作は s の連続した部分文字列であって…

問題 解法 解答 問題 atcoder.jp 解法 公差 d が 0 のとき，求める答えは x * x * ... * x となるので x^n． そうでないときについて考える．まず，各項を d で割る．そうすると，t = x * mod_inverse(d) とおくと， t, t + 1, t + 2, ... , t + n - 1 と初…

問題 解法 解答 問題 atcoder.jp 解法 引き分けがない（勝ち負けが必ずつく）として考えると，ゲームが行われる回数 M は N <= M <= 2 * N - 1 の値を取りうる．それぞれの M に対する決着がつくまでの確率は，a = A / 100, b = B / 100 とおくと， C(M - 1,…

問題 解法 解答 問題 atcoder.jp 解法 まず，それぞれ 2 人がもう一方がいなかった場合にゴールまでたどり着けるかを調べる．これは，[A, C], [B, D] 中に岩が 2 つ以上連続している箇所があったら乗り越えられないので，到達不可能となる．この時点でどちら…

結果 A - Sum of Interior Angles B - Sumo D - Maximum Sum of Minimum 結果 6 問中 3 問正解（800 / 2900 点, 49:19），3283 位中 571 位，パフォーマンス 1632，新レート 1597 (+3)．500 点の D 問題を結果的に通すことができてよかったが，解法ミスに気…

結果 A - Apple Pie B - Guidebook C - Switches D - equeue 結果 6 問中 4 問正解（1000 / 2100点, 27:14），5186 位中 371 位，パフォーマンス 1805，新レート 1594 (+27)．目標であった 5 問正解は達成できなかったが，4 問目までを早く通すことができた…

問題 解法 解答 問題 atcoder.jp 解法 まず，求める答えは x 方向の差の絶対値の合計と y 方向の差の絶対値の合計に分解できる．まず x 方向の差の合計について考える．ここで「差が k となるような 2 つの駒の置き方」を求める．これは x 方向の長さは M で…

問題 解法 解答 問題 atcoder.jp 解法 M 回の操作は順序を入れ替えても問題ないので，C_i が大きい順に行っていくのがよい．また，A_i を小さい順に操作するかどうかを決めていく．今見ている操作が i 番目で今見ている要素が j 番目のとき，C_i が A_j より…

問題 解法 解答 問題 atcoder.jp 解法 全ての [L_i, R_i] に含まれるカードの枚数を求めればよい．これは，L_i のうち最も大きいものと R_i のうち最も小さいものの差になる．この２つの位置が逆転するとき，答えは 0 となるので注意．O(N)． 解答 atcoder.j…

問題 解法 解答 問題 atcoder.jp 解法 まず c を降順にソートする．ある頂点に c_1 を置いたとき，この頂点に隣り合う頂点に書く数字は c_2, c_3, ... とするのがよい．なぜならば，あえて小さい整数を最初に選んだ頂点に近づけても (c_1 - (小さい整数)) だ…