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

https://atcoder.jp/contests/cf17-tournament-round1-open/tasks/asaporo2_d 問題概要 N頂点の木とN要素の数列Sが与えられる。木のすべての辺に整数の長さを割り当てて、Siが木の頂点iとすべての頂点との最短距離の和と等しくなるようにせよ。与えられる入…

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 門松もどき

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

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

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

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

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

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

https://atcoder.jp/contests/tenka1-2016-final/tasks/tenka1_2016_final_c 問題概要 文字列SとM要素の文字列の集合Pが与えられる。SからPの要素を取り除くと、取り除いた要素に対応する点数Wが与えられる。任意の回数この操作を行ったときの、得られる点数…

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

https://atcoder.jp/contests/yahoo-procon2017-final-open/tasks/yahoo_procon2017_final_c 問題概要 整数MとN要素の数列Aが与えられるので、以下の形のQ個のクエリを順に処理せよ。 クエリ: Aの区間[l, r]の全要素にxを加算する。その後、同じ区間内にMの…

みんなのプロコン (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階へ移動するために必要なコス…

競プロ始めて1年半

はじめに ちょうどいいタイミングなので振り返りの記事を書きます。過去の同じような記事は以下 レーティング 半年前とのhighest比較がこちら AtCoder: 1919 -> 2177 Codeforces: 1952 -> 2064 Topcoder: 1428 -> 1549 AtCoderは8月あたり、Topcoderはつい先…

Topcoder SRM 711 Div.1 Easy - ConsecutiveOnes

問題概要 整数n, kが与えられる。n以上の整数のうち、2進表現で1がk個続く部分を持つような数で最小のものを求めよ。 0 <= n < 250 k <= 50 解法 1がk個続く箇所を全探索する。1が続く箇所より上位の桁はnと同じになるよう埋めるのが最善。より下位の桁は、…

Topcoder SRM 712 Div.1 Easy - LR

問題概要 N要素の数列S, Tが与えられる。Sに対してLとRという2種類の操作を行うことができる。操作の結果SをTに等しくできるか判定せよ。できるならば具体的に操作の列をひとつ示せ。なおTに等しくできる場合、操作の回数は100回以下になることが証明できる…

yukicoder No.109 N! mod M

https://yukicoder.me/problems/no/109 問題概要 T個の数の組(N, M)が与えられるので、それぞれでN! mod Mを求めよ 1 <= T <= 100 1 <= M <= 109 max(0,M−105) <= N <= 109 解法 まず自明なケースとして、NがM以上の場合答えは0である(N!で掛ける数の中に必…