天下一プログラマーコンテスト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の全要素…

Codeforces Round #499 (Div. 1): D. Mars rover

http://codeforces.com/contest/1010/problem/D 問題概要 N頂点の根付き木が与えられる。すべての葉にはあらかじめ1か0の入力が与えられており、葉以外の頂点はすべて「子から来たビットを入力として論理演算をし、その出力を親に送る」機能を持っている。演…

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つの…

yukicoder No.95 Alice and Graph

https://yukicoder.me/problems/no/95 問題概要 N頂点M辺の無向グラフが与えられる。グラフの頂点には0~(N-1)の番号が付いている。はじめプレイヤーは頂点0にいて、一度の移動で一辺で繋がれた2頂点間を移動できる。また頂点nをはじめて訪れたとき(2n - 1)…

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種類の操作を自由な順…

yukicoder No.529 帰省ラッシュ

https://yukicoder.me/problems/no/529 問題概要 N頂点M辺の単純無向連結グラフとQ個のクエリが与えられる。クエリには以下の2種類が存在する。クエリを順に実行した結果を出力せよ。 クエリ1. 頂点uに価値wの獲物が出現する クエリ2. 頂点sからtに、同じ辺…

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通りに定まるようにするとき、取り除く辺のコストの和の最…

yukicoder No.584 赤、緑、青の色塗り

https://yukicoder.me/problems/no/584 問題概要 1×Nのグリッドを以下のルールを守って赤、緑、青で彩色するとき、ありうる塗り方は何通りか。 R個のマスが赤、G個のマスが緑、B個のマスが青になるようにし、残りのマスは未彩色のまま残す 3マス以上連続して…

yukicoder No.96 圏外です。

https://yukicoder.me/problems/no/96 問題概要 N個の中継局が二次元平面上の相異なる整数座標上に存在する。中継局と中継局は距離10以下であれば通信でき、無線機と中継局、無線機と無線機は距離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の完了後でないと行えない。初めにいる部…