人権なし

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

AtCoder 500 点問題

AtCoder Beginner Contest 133:E - Virus Tree 2

問題 解法 解答 問題 https://atcoder.jp/contests/abc133/tasks/abc133_e 解法 適当な頂点を根とする根付き木を考える.根から DFS をしていく.頂点 v にいるとき,その頂点の子の配色の通り数を考える.子は頂点 v の親と頂点 v の色それぞれと互いに異な…

技術室奥プログラミングコンテスト#4 Day1:L - じゃんけん

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_l 解法 以下の DP を考える. dp(i, j) := 頂点 i にいて,今 j 回まで操作が終わった時の,これから得られるスコアの総和の最大値 遷移は今いる頂点 i に留まるか,頂点 i につな…

技術室奥プログラミングコンテスト#4 Day1:K - 天使と宿題

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_k 解法 最終日には必ず写させてもらう必要がある.なぜならば,最終日分の宿題は N - 1 日までで写すことができないから.最終日で写せるページ数 (a_N) 日分は写すことができるの…

技術室奥プログラミングコンテスト#4 Day1:J - school competition 2

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_j 解法 N, M <= 20 と小さいので,両校とも考えられる全てのチームの編成を列挙することができる.ここで,各校全ての生徒がどちらかのチームに入るので,A チームのレートの総和…

AtCoder Beginner Contest 135:E - Golf

問題 解法 解答 問題 https://atcoder.jp/contests/abc135/tasks/abc135_e 解法 考察をしやすくするため X >= Y >= 0 となるように X, Y を変換してしまう.変換した場合は,答えを出力する際に元の X, Y に当てはまるように再度復元する必要があるので注意…

AtCoder Beginner Contest 134:E - Sequence Decomposing

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

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 Beginner Contest 132:E - Hopscotch Addict

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

AtCoder Beginner Contest 130:E - Common Subsequence

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

AtCoder Beginner Contest 131:E - Friendships

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

diverta 2019 Programming Contest 2:C - Successive Subtraction

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

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 が立っている…

M-SOLUTIONS プロコンオープン:C - Best-of-(2n-1)

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

AtCoder Beginner Contest 127:E - Cell Distance

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

M-SOLUTIONS プロコンオープン:D - Maximum Sum of Minimum

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

AtCoder Beginner Contest 128:E - Roadwork

問題 解法 解答 問題 atcoder.jp 解法 工事期間を [S_i - X_i, T_i - X_i) とすることで,座標 0 を出発する時間から行き止まりになる座標が分かる形に情報を変形することが出来る.このもとで考える.ここで,今工事中である座標をソートした形で持っておく…

Chokudai SpeedRun 002:J - GCD β

問題 解法 解答 問題 atcoder.jp 解法 最初のペア (A_0, B_0) のどちらかを選ぶかによって作れる GCD の最大値は一意に定まる.具体的には,A_0 を選んだ場合,その次のペアにおいては gcd(A_0, A_1) と gcd(A_0, B_1) のうち大きくなる方を選んだ方が自明に…

diverta 2019 Programming Contest:D - DivRem Number

問題 解法 解答 問題 atcoder.jp 解法 問題文中の条件を式にあらわすと,N = k(m + 1) となる.よって,k を 1 <= k <= √N の範囲で動かし,条件を満たすような m を探せばよい.O(√N). 解答 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 …

いろはちゃんコンテスト Day1:I - リスのお仕事

問題 解法 解答 問題 atcoder.jp 解法 木を頂点,枝を辺として無向グラフを考える.このとき,前に移動した枝の隙間の大きさを状態として加えたダイクストラ法を用いて,頂点 1 から各頂点まで休まなければいけない最小の回数が求まる.よって,答えは (dist…

エクサウィザーズ 2019:C - Snuke the Wizard

問題 解法 解答 問題 atcoder.jp 解法 答えとして知りたいのは,各ゴーレムがどこのマスにいるかではなく,マスから落ちるかどうか.また,各ゴーレムが最初の位置関係から逆転することはない(一緒の位置になることはある).これを踏まえると,左のマスか…

CODE THANKS FESTIVAL 2018:G - Sum of Cards

問題 解法 解答 問題 atcoder.jp 解法 (a_i, b_i) というカードに対して a_i, b_i を頂点として間に辺を張ることを考える.そうすると,いくつかの輪の関係になる.ここでそれぞれの輪は共通の頂点を持ったりしない. それぞれの輪ごとに数字の種類を決めた…

全国統一プログラミング王決定戦本戦:D - Deforestation

問題 解法 解答 問題 atcoder.jp 解法 竹を切るとき,最後に切った時刻が分かれば得点が分かる.なので,竹 L_i から竹 R_i の最後に切った時刻の総和を求められれば,各イベントの得点がわかる.最後に切った時刻は区間 [L_i, R_i] ごとに更新されるので,…

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019:D - Restore the Tree

問題 解法 解答 問題 atcoder.jp 解法 問題文中に 書き足された各辺 u→vu→v は、ある頂点 uu からその子孫であるような頂点 vv に向かって伸びています とあるので答えは一意に定まる(これを見落としていて複数答えがあるのでないかとちょっと悩んでいた)…

AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019:D - Nearest Card Game

問題 解法 解答 問題 atcoder.jp 解法 2人の操作後の各カードの所属は,N が偶数のとき「TATA...TAAA...ATT...T」のように高橋君と青木君が交互になっている区間(区間1)・青木君の区間(区間2)・高橋君の区間(区間3)となっている.また.区間2と区…

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019:D - Double Landscape

問題 解法 解答 問題 atcoder.jp 解法 各マス (i, j) に書くことが出来る数字の最大値を max_(i, j) とする.また,数字 i が書くことが出来る数字の最大値になっているマスの個数を cnt_i とし,数字 i を書く時点で書くことが出来るマスの総数を avail_i …

COLOCON -Colopl programming contest 2018-:D - すぬけそだて――トレーニング――

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 番目の候補の時刻から先で j 回起動するときの解の最大値 と DP をおく.このとき,愚直に全ての候補を選んでいては O(N^3) になってしまう.ここで,「今の時刻 + X を超える時刻のうち一番早いもの」と…

DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦:B - GCDロボット

問題 解法 解答 問題 atcoder.jp 解法 求める整数は gcd(a_1, Z), gcd(a_2, Z), ... , gcd(a_N, Z) の公倍数である必要があるので,この公倍数のうち最小のものを求めるので,答えは lcm(a_i, Z) になる.O(N). 解答 atcoder.jp

Tenka1 Programmer Contest:D - IntegerotS

問題 解法 解答 問題 atcoder.jp 解法 K を2進数表記したとき,「0 ~ 2^(k - 1) の位が 1,2^k の位が 0,2^(k + 1) ~ 2^30 の位は K のそれぞれの位と同じ」数を考える.この数を OR で超えない中で整数を出来るだけ選べばよいので,各 k についてそれぞれ…

codeFlyer (bitFlyer Programming Contest):D - ハンコ

問題 解法 解答 問題 atcoder.jp 解法 紙の (N + 1) 行目~ (H - N) 行目,(M + 1) 列目~ (W - M) 列目 はそれぞれ同じ模様になるので,この2つの区間を座標圧縮することが出来る.また,ハンコの1つ1つの黒マスが紙を黒くする領域は長方形になるので,…