AtCoder

天下一プログラマーコンテスト2013 決勝: A - 天下一有無

https://beta.atcoder.jp/contests/tenka1-2013-final/tasks/tenka1_2013_final_a 問題概要 N×Mのグリッドの各マスに対して「着色されたマスが縦・横・斜めで隣り合わない」かつ「最低1マスは着色されている」という条件のもと色を塗るとき、何通りの塗り方…

天下一プログラマーコンテスト2016予選B: D - 天下一数列にクエリを投げます

https://beta.atcoder.jp/contests/tenka1-2016-qualb/tasks/tenka1_2016_qualB_d 問題概要 N要素の数列a1, a2, .., aNに対してA個の加算クエリとB個の調査クエリが与えられるので順次処理せよ。 加算クエリ: 数列の区間[L, R]にXを加算する 調査クエリ: S回…

SoundHound Programming Contest 2018 Masters Tournament 本戦: E - Hash Swapping

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_e 問題概要 長さNの文字列がM個与えられる。それらに対するQ個のクエリを順次処理せよ。 swapクエリ: x番目の文字列とy番目の文字列の、l番目からr番…

SoundHound Programming Contest 2018 Masters Tournament 本戦: D - Propagating Edges

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_d 問題概要 N頂点0辺の無向グラフに対してQ個のクエリが飛んでくるので順次処理せよ。 addクエリ: 頂点u, v間に辺を張る completeクエリ: 「頂点u」…

SoundHound Programming Contest 2018 Masters Tournament 本戦: C - Not Too Close

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_c 問題概要 N頂点の無向グラフで、頂点に1からNまでの番号がついており、自己辺・多重辺を持たず、すべての辺の長さを1としたとき頂点1-2間の最短距…

SoundHound Programming Contest 2018 Masters Tournament 本戦: B - Neutralize

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_b 問題概要 N要素の数列Aが与えられる。Aの中から連続するK個の要素を選んでその値を全て0にするという操作を何度でも行えるとき、最終的なAの全要素…

AtCoder Regular Contest 097: F - Monochrome Cat

https://beta.atcoder.jp/contests/arc097/tasks/arc097_d 問題概要 N頂点の木が与えられる。木の各頂点には白か黒どちらかの色がついている。任意の頂点からスタートし、以下の2種類の動作を任意の順序で繰り返すとき、すべての頂点の色を黒にするために必…

AtCoder Regular Contest 079: F - Namori Grundy

https://beta.atcoder.jp/contests/arc079/tasks/arc079_d 問題概要 N頂点N辺の弱連結有向グラフが与えられる。すべての頂点にそれぞれひとつの非負整数aiを割り当てることを考える。「ある頂点uから伸びる有向辺(u, v)でuと繋がっているすべての頂点vに割り…

SoundHound Inc. Programming Contest 2018 -Masters Tournament-: E - + Graph

https://beta.atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_e 問題概要 N頂点M辺の単純連結無向グラフが与えられる。辺iには整数siが設定されている。すべての頂点にある整数を割り当てるとき、すべての辺において「辺…

AtCoder Grand Contest 012: D - Colorful Balls

https://beta.atcoder.jp/contests/agc012/tasks/agc012_d 問題概要 N個のボールが一列に並んでおり、各ボールには色と重さが設定されている。色が同じで合計の重さがX以下のボール2つの位置を入れ替える操作と、色が異なって合計の重さがY以下のボール2つの…

AtCoder Regular Contest 093: E - Bichrome Spanning Tree

https://beta.atcoder.jp/contests/arc093/tasks/arc093_c 問題概要 N頂点M辺のグラフが与えられる。各辺にはコストがある。すべての辺をそれぞれ白か黒かで塗り分けるとき、以下の条件が満たされるような塗り方は何通りあるか。条件:「白の辺も黒の辺も少…

AtCoder Regular Contest 067: F - Yakiniku Restaurants

問題概要 N軒の焼肉屋が横一直線に並んでおり、それぞれの間の距離は数列Aで表される。またM枚のチケットを1枚ずつ持っており、チケットjを焼肉屋iがある地点で使うことでB(i, j)の幸福度を得ることができる。好きな地点からスタートして自由に移動してチケ…

NJPC2017: F - ダブルス

問題概要 数直線の原点上に人が2人いる。時刻Tiに座標Xiへボールが飛んでくることを意味するN個の整数の組(Ti, Xi)が与えられる。このとき2人のうちどちらか一人が時刻Tiに座標Xiにいるとボールをキャッチすることができる。2人の移動速度をvとしたとき、す…

AtCoder Regular Contest 097: E - Sorted and Sorted

https://beta.atcoder.jp/contests/arc097/tasks/arc097_c 問題概要 1~Nの番号がついた黒いボールと1~Nの番号がついた白いボールの計2N個のボールが横一列に並んでいる。隣り合う2つのボールをスワップするという操作を行って、黒白それぞれを独立に見たと…

第2回 ドワンゴからの挑戦状 予選: C - メンテナンス明け

https://beta.atcoder.jp/contests/dwango2016-prelims/tasks/dwango2016qual_c 問題概要 N個の駅とM個の路線が与えられる。各路線はLi個の駅を順につないだ単純パスになっており、各辺に移動時間が設定されている。駅srcから駅dstに向かいたいが、一度だけ…

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選: C - 特別講演「括弧列と塗り分け」

https://beta.atcoder.jp/contests/discovery2016-final/tasks/discovery_2016_final_c 問題概要 対応の取れた括弧列Sと非負整数Kが与えられる。Sの各文字を赤か青の2色で塗り分けるとき、すべての対応括弧の組(S[i], S[j])について、Sの区間[i, j]において…

第2回 ドワンゴからの挑戦状 本選: B - 道迷い

https://beta.atcoder.jp/contests/dwango2016-honsen/tasks/dwango2016final_b 問題概要 一次元上のN個の点を表す数列Xが与えられる。このうちのいずれかの点がオフィスだが、その点がオフィスであるかどうかは実際に訪れるまでわからない。ここで座標0から…

第2回 ドワンゴからの挑戦状 本選: A - 通勤

https://beta.atcoder.jp/contests/dwango2016-honsen/tasks/dwango2016final_a 問題概要 ニコ数を「10進法で表記したとき各桁が2, 5のみからなり、かつどの隣り合う2桁の数字も相異なる数」と定義する。初め L=1, X=0 である。以下の2種類の操作を自由な順…

AtCoder Grand Contest 022: C - Remainder Game

https://beta.atcoder.jp/contests/agc022/tasks/agc022_c 問題概要 N要素の数列A, Bがある。以下の操作を繰り返してAをBに一致させることができるかを判定せよ。可能ならば操作の最小コストも求めよ。 操作: 正整数kをひとつ選び、Aの各要素に対してそれぞ…

AtCoder Regular Contest 078: F - Mole and Abandoned Mine

https://beta.atcoder.jp/contests/arc078/submissions/2417009 問題概要 N頂点M辺の単純連結無向グラフが与えられる。このグラフから任意の辺集合を取り除いて頂点1から頂点Nまでの単純パスがただ1通りに定まるようにするとき、取り除く辺のコストの和の最…

CODE FESTIVAL 2017 Elimination Tournament Round 1: D - Ancient Tree Record

問題概要 N頂点の木とN要素の数列Sが与えられる。木のすべての辺に整数の長さを割り当てて、Siが木の頂点iとすべての頂点との最短距離の和と等しくなるようにせよ。与えられる入力においてはそのような割り当て方がただひとつ存在することが保証される。 N <…

CODE FESTIVAL 2016 Elimination Tournament Round 1: A - グラフ / Graph

問題概要 辺に正整数の重みが設定されたN頂点M辺の無向グラフと、Q個のクエリが与えられる。i個目のクエリでは頂点SiとTiが指定される。各クエリにおいて、「SiまたはTiを始点としたとき、集合に含まれる辺のみを使ってすべての頂点にたどりつくことができる…

CODE FESTIVAL 2016 Tournament Round 3: A - ストラックアウト / Struck Out

問題概要 1~Nまでの番号がついたN個のパネルがある。1度のゲームではK回ボールを投げてi回目にパネルjに当てるとi×Aj点が得られ、各回の点の和が得点となる。当てたパネルを順にP1, P2, ..., PK としたとき、1 <= P(i+1) - Pi <= M という条件の下でありう…

CODE FESTIVAL 2016 qual A: D - マス目と整数 / Grid and Integers

問題概要 R行C列のグリッドがある。このうちN個のマスに非負整数が書き込まれている。まだ何も書き込まれていない残りすべてのマスに対して、以下のルールを満たしながら数字を書き込むことが可能か判定せよ。ルール1: マスに書き込めるのは非負整数のみ。ル…

天下一プログラマーコンテスト2016本戦: D - 右往左往

問題概要 N個のタスクと2つの部屋がある。タスクiは部屋1で行うとAi, 部屋2で行うとBi時間かかる。またi回目の部屋の移動には C×(i-1)+D 時間かかる。またタスクにはM個の依存関係(Xi, Yi)があり、タスクYiはタスクXiの完了後でないと行えない。初めにいる部…

DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦: C - 01文字列

問題概要 空文字列Sに対して以下の3種類の操作を好きな順番で好きな回数行い、与えられた文字列Tに一致させたい。そのための最小コストを求めよ。 1. Sの先頭に0を挿入する(コストA)。 2. Sの末尾に1を挿入する(コストB)。 3. Sの01をすべてflipする(コストC…

AtCoder Regular Contest 065 : F - シャッフル / Shuffling

問題概要 長さNの01文字列Sが与えられる。M個の数字ペア(Li, Ri)が与えられ、Sの区間[Li, Ri]の文字を自由に並び替える、という操作を順に行ったあとのSとしてありうるものが何通りあるか求めよ。ただしLiは必ず昇順になっているものとする。 N, M <= 3000 …

天下一プログラマーコンテスト2016本戦 C - たんごたくさん

問題概要 文字列SとM要素の文字列の集合Pが与えられる。SからPの要素を取り除くと、取り除いた要素に対応する点数Pが与えられる。任意の回数この操作を行ったときの、得られる点数の最大値を求めよ |S| <= 2×105 M <= 5000 |P_i| <= 200 解法 Pの各要素がSの…

みんなのプロコン (2017) 本選 C - 倍数クエリ

問題概要 整数MとN要素の数列Aが与えられるので、以下の形のQ個のクエリを順に処理せよ。 クエリ: Aの区間[l, r]の全要素にxを加算する。その後、同じ区間内にMの倍数が何個あるかを出力する。 N, M, Q <= 105 A_i <= 109 解法 平方分割をする。 平方分割に…

みんなのプロコン (2017) 本選 B - チーム決め

問題概要 N要素の数列AとM要素の数列Bが与えられる。数列からK個の要素を選んで任意の順序で並べる、という操作を両方の数列に対して行ってできる数列をX, Yとする。好きな選び方ができるとき、max(|X_1-Y_1|, ..., |X_K - Y_K|)の最小値を求めよ。 N, M <= …