人権なし

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

JOI 夏季セミナー 2019 に通りました

7/21 に選考結果が来ると思いきや,1 日ほど遅れたみたいですね(選考がかなり難航していた?).去年も参加して今年も通ることができたのでよかったです.例年以上に一般枠での応募が多かったようで,TL の方々でも落ちている方がいらっしゃるようです.も…

AtCoder Beginner Contest 134:E - Sequence Decomposing

問題 解法 解答 問題 https://atcoder.jp/contests/abc134/tasks/abc134_e 解法 単調増加列の数を最小化すればよい.既に色を塗った整数以外で新しく単調増加列を構成することを考える.ここで,残っている数字の中で最も大きいもののうち一番左にあるものは…

AtCoder Beginner Contest 134:D - Preparing Boxes

問題 解法 解答 問題 https://atcoder.jp/contests/abc134/tasks/abc134_d 解法 i = N, (N - 1), (N - 2), ... の倍数の順番に考えていく.そうすると i 番目の箱にボールを入れるかどうか決める際 i * 2, i * 3, ... 番目の箱にボールを入れるかどうかは既…

AtCoder Beginner Contest 126:F - XOR Matching

問題 解法 解答 問題 https://atcoder.jp/contests/abc126/tasks/abc126_f 解法 M = 0 のとき,答えは自明に (0, 0). M = 1 のとき,K = 0 のときしか答えは存在しない. それ以外のとき,K < 2^M ならば答えが存在する.なぜならば,K >= 2^M のときには 0…

AtCoder Beginner Contest 126:E - 1 or 2

問題 解法 解答 問題 https://atcoder.jp/contests/abc126/tasks/abc126_e 解法 (X_i, Y_i) のカードは他方が分かればもう片方もわかる関係である.なので,(a, b), (b, c) とあったとき a が分かれば b も c も同時にわかる.このようなカードの連結成分内…

AtCoder Grand Contest 035:C - Skolem XOR Tree

問題 解法 解答 問題 https://atcoder.jp/contests/agc035/tasks/agc035_c 解法 N = 2^k であるときは No.なぜならば,N - (2 * N) のパス間で k bit 目が 1 であるものはないため,xor を N にすることは不可能だから.そうでないときは全て Yes となる.…

AtCoder Grand Contest 035:B - Even Degrees

問題 解法 解答 問題 https://atcoder.jp/contests/agc035/tasks/agc035_b 解法 まず,辺の数が奇数の時は答えは No になる.偶数の時は答えを構成することができる. 簡単な場合として根付き木を考える.このとき各頂点の出次数の偶奇は葉から各辺の向きを…

AtCoder Grand Contest 035:A - XOR Circle

問題 解法 解答 問題 https://atcoder.jp/contests/agc035/tasks/agc035_a 解法 (a ^ b) == c は (a ^ b ^ c) == 0 と同値より,高々 3 種類の数字しか登場してはならない.3 種類の場合は (a ^ b ^ c) == 0 となる a, b, c がそれぞれ N / 3 個,2 種類の場…

AtCoder Beginner Contest 132:E - Hopscotch Addict

問題 解法 解答 問題 https://atcoder.jp/contests/abc132/tasks/abc132_e 解法 各頂点についてけんけんぱの k 歩目 (0 <= k <= 2) で到達するために辺を通る回数の最小値を求めることを考える.これは,各頂点について 3 つの状態(けんけんぱの歩数)をも…

AtCoder Beginner Contest 132:D - Blue and Red Balls

問題 解法 解答 問題 https://atcoder.jp/contests/abc132/tasks/abc132_d 解法 i 回操作が必要なとき,青玉が連続している区間が i 個あるということなので,(N - K) 個ある赤玉の間と左端と右端の (N - K + 1) 個の隙間に青玉の区間を i 個当てはめればよ…

AtCoder Beginner Contest 132:C - Divide the Problems

問題 解法 解答 問題 https://atcoder.jp/contests/abc132/tasks/abc132_c 解法 (N / 2 + 1 番目に難しい問題の難易度, N / 2 番目に難しい問題の難易度] のどれかを K と設定するのがよい.ソートすればこれは求まる.O(NlogN). 解答 https://atcoder.jp/c…

AtCoder Beginner Contest 130:F - Minimum Bounding Box

問題 解法 解答 問題 atcoder.jp 解法 x_max, x_min, y_max, y_min の座標となる点が変化するタイミングのみ調べればよい.なぜならば,変化するタイミング間では求める面積は広義単調増加・減少になるので,間ではなく両端のタイミングでその区間での面積の…

AtCoder Beginner Contest 130:E - Common Subsequence

問題 解法 解答 問題 atcoder.jp 解法 まず,問題文の解釈から.選んだ部分列の数字を文字列を連結させて読むのではなく,数列としてみたときに等しいものの個数を求める.例えば {1, 3, 3, 3} と {1333} は,各項を文字列としてみて連結させると同じものに…

AtCoder Beginner Contest 130:D - Enough Array

問題 解法 解答 問題 atcoder.jp 解法 ある区間 [l, r] の和が K 以上であるとき,区間 [l, r + 1], [l, r + 2], ... , [l, N] のそれぞれの和も当然 K 以上なので,各 l について最初に区間の和が K 以上となる r が分かればよい.この l, r は尺取り法によ…

AtCoder Beginner Contest 130:C - Rectangle Cutting

問題 解法 解答 問題 atcoder.jp 解法 与えられた長方形の重心を通るような面積を半分にする直線は,長方形の対角線である 2 本が考えられる.それ以外の点で半分にする直線は 1 本に定まる.O(1). 解答 atcoder.jp

プログラミングバトル 本戦 - BCU30:B - Interval Addition

問題 解法 解答 問題 atcoder.jp 解法 広義単調増加となっている部分列の個数が答えになる.無駄に最初から全体に +min(A) してから・・・などと考えると反例が出てくるので注意する(1 WA した). 解答 atcoder.jp

AtCoder Beginner Contest 131:F - Must Be Rectangular!

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

AtCoder Beginner Contest 131:E - Friendships

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

AtCoder Beginner Contest 131

結果 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 Beginner Contest 131:D - Megalomania

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

AtCoder Beginner Contest 131:C - Anti-Division

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

diverta 2019 Programming Contest 2:D - Squirrel Merchant

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

diverta 2019 Programming Contest 2

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

diverta 2019 Programming Contest 2:C - Successive Subtraction

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

diverta 2019 Programming Contest 2:B - Picking Up

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

AtCoder Beginner Contest 129:E - Sum Equals Xor

問題 解法 解答 問題 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 Beginner Contest 129:D - Lamp

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

AtCoder Beginner Contest 129:C - Typical Stairs

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

Codeforces で青になりました

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

Codeforces Round #566 (Div. 2)

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