問題記録

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の完了後でないと行えない。初めにいる部…

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

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

yukicoder No.127 門松もどき

問題概要 N要素の正整数列Aが与えられる。Aの部分列で門松もどきであるようなものの最大の長さを求めよ。ただし門松もどきとは 各要素の大きさが「左端→右端→左から2番目→右から2番目→...」で昇順になっているもの、または「右端→左端→右から2番目→左から2番…

yukicoder No.97 最大の値を求めるくえり

問題概要 xorshiftによって生成される要素数Nの擬似乱数列Aがある。Q個のクエリqiが与えられるので、それぞれにおいて {qi * a mod 100003 (a ∈ A)} の最大値を求めよ。 1 <= N, Q <= 100003 0 <= qi < 100003 解法 この問題の肝は、Aが乱数列であることから…

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

みんなのプロコン (2017) 本選 A - YahooYahooYahoo

問題概要 与えられた文字列Sに対して以下の3種類の操作をひとつ選んで適用する、ということを繰り返し、Sを"yahoo"という文字列が0回以上繰り返された形にしたい。最小何回の操作でこれを達成できるか求めよ。 操作1: Sの任意の1文字を別の文字に置き換える …

第4回 ドワンゴからの挑戦状 予選 C - Kill/Death

問題概要 AチームとBチームにわかれて対戦するゲームがある。このゲームでは試合終了後に各プレイヤーのリザルトとしてkill数とdeath数が表示される。リザルトは各チームごとにkill数の多いプレイヤーから順に表示される。kill数が同数の場合はdeath数の少な…

yukicoder No.614 壊れたキャンパス

問題概要 K階建ての棟がN個あり、棟a_iのある階と棟(a_i+1)のある階を結ぶ渡り廊下がM個ある。「コスト0で渡り廊下を渡る」「コスト1で同じ棟の1つ上または1つ下の階に移動する」の2種類の移動が行えるとき、棟1のS階から棟NのT階へ移動するために必要なコス…