ARC
https://atcoder.jp/contests/arc090/tasks/arc090_d 問題概要 正整数nに対してf(n)をnの10進表記での桁数と定義する。与えられる整数Sに対してf(l)+f(l+1)+...+f(r)=Sを満たすような(l, r)の組が何通り存在するか求めよ。 S <= 108 解法 まず桁数が少しでも…
https://atcoder.jp/contests/arc040/tasks/arc040_d 問題概要 N行N列のグリッドが与えられる。グリッドの各マスは床もしくは障害物である。指定されたマスからスタートして「現在の向きに直進し、90度どちらかに向きを変える」という操作を繰り返してすべて…
https://atcoder.jp/contests/arc027/tasks/arc027_4 問題概要 N個の石が一直線に並んでおり、石x からは 1 ~ Hx 個先のどれかの石にジャンプすることができる。以下の形式のクエリがD個飛んでくるのでそれぞれに解答せよ。 整数s, t (s < t) が与えられる…
https://atcoder.jp/contests/arc045/tasks/arc045_d 問題概要 整数Nと、XY平面上の(2N+1)個の点が与えられる。各点はX座標またはY座標が同じ他の1点とペアになることができる。ただしすでにペアをつくっている点が他の点とペアになることはできない。すべて…
https://atcoder.jp/contests/arc084/tasks/arc084_d 問題概要 N個の非負整数Aiが黒板に書かれている。黒板に書いてある数に対して「数をひとつ選びそれを2倍したものを黒板に書き足す」「数をふたつ選びそれらのbitwise xorをとったものを黒板に書き足す」…
https://atcoder.jp/contests/arc041/tasks/arc041_d 問題概要 N頂点M辺の無向グラフが与えられる。このグラフの各辺を以下のルールに従って赤か青のどちらかで塗っていくとき、各辺を初めに指定されている色で塗ることができるか判定せよ。 ルール: 自由に…
https://atcoder.jp/contests/arc020/tasks/arc020_4 問題概要 N個の町があり、隣り合う町同士は道で結ばれている。町iと町(i+1)を結ぶ距離はDiとして与えられる。いまN個の町からK個の町を選び順に移動していくことを考える。このとき訪れる町に重複があっ…
https://atcoder.jp/contests/arc004/tasks/arc004_4 問題概要 整数N, Mが与えられる。NをM個の整数の積として表す方法が何通りあるか求めよ。構成要素が同じでも並び順が異なればそれぞれ1通りとして数えるものとする。 |N| <= 109 M <= 105 解法 掛け算の…
https://atcoder.jp/contests/arc039/tasks/arc039_d 問題概要 N頂点M辺の無向グラフとQ個の旅行計画が与えられる。各旅行計画は始点、中継点、終点をあらわす頂点の組(A, B, C)からなる。各旅行計画について、一度も同じ辺を通ることなく始点→中継点→終点と…
https://beta.atcoder.jp/contests/arc083/tasks/arc083_d 問題概要 2次元平面上に2N個のロボットと2N個のボールがある。ロボットはx軸上のx座標1〜Nの箇所にN個、y軸上のy座標1〜Nの箇所にN個それぞれ設置されている。x軸上のロボットは起動されるとx=a上に…
https://beta.atcoder.jp/contests/arc071/tasks/arc071_d 問題概要 整数Nが与えられたとき、以下の性質をすべて満たす数列が何通りあるか求めよ。 数列は無限長で、各要素は1〜Nのいずれかの整数である 数列の第N項以降はすべて同じ値である 数列のある要素…
https://beta.atcoder.jp/contests/arc097/tasks/arc097_d 問題概要 N頂点の木が与えられる。木の各頂点には白か黒どちらかの色がついている。任意の頂点からスタートし、以下の2種類の動作を任意の順序で繰り返すとき、すべての頂点の色を黒にするために必…
https://beta.atcoder.jp/contests/arc079/tasks/arc079_d 問題概要 N頂点N辺の弱連結有向グラフが与えられる。すべての頂点にそれぞれひとつの非負整数aiを割り当てることを考える。「ある頂点uから伸びる有向辺(u, v)でuと繋がっているすべての頂点vに割り…
https://beta.atcoder.jp/contests/arc093/tasks/arc093_c 問題概要 N頂点M辺のグラフが与えられる。各辺にはコストがある。すべての辺をそれぞれ白か黒かで塗り分けるとき、以下の条件が満たされるような塗り方は何通りあるか。条件:「白の辺も黒の辺も少…
問題概要 N軒の焼肉屋が横一直線に並んでおり、それぞれの間の距離は数列Aで表される。またM枚のチケットを1枚ずつ持っており、チケットjを焼肉屋iがある地点で使うことでB(i, j)の幸福度を得ることができる。好きな地点からスタートして自由に移動してチケ…
https://beta.atcoder.jp/contests/arc097/tasks/arc097_c 問題概要 1~Nの番号がついた黒いボールと1~Nの番号がついた白いボールの計2N個のボールが横一列に並んでいる。隣り合う2つのボールをスワップするという操作を行って、黒白それぞれを独立に見たと…
https://beta.atcoder.jp/contests/arc078/submissions/2417009 問題概要 N頂点M辺の単純連結無向グラフが与えられる。このグラフから任意の辺集合を取り除いて頂点1から頂点Nまでの単純パスがただ1通りに定まるようにするとき、取り除く辺のコストの和の最…
問題概要 長さNの01文字列Sが与えられる。M個の数字ペア(Li, Ri)が与えられ、Sの区間[Li, Ri]の文字を自由に並び替える、という操作を順に行ったあとのSとしてありうるものが何通りあるか求めよ。ただしLiは必ず昇順になっているものとする。 N, M <= 3000 …
http://arc084.contest.atcoder.jp/tasks/arc084_b 問題概要 正整数Kのある正の倍数を10進法で表したときの各桁の和の最小値を求めよ。 2 <= K <= 105 解法 以下のようなグラフを考え、最短経路問題を解く。 頂点は0~(K-1)のK個 頂点x → 頂点(x+1)%K にコス…
http://arc083.contest.atcoder.jp/tasks/arc083_c 問題概要 N頂点の根付き木とN要素の数列Xが与えられる。木の各頂点に白or黒の色と非負整数を割り当てるとき、頂点nを根とする部分木に含まれる頂点のうちnと同じ色のものに割り当てられた数の合計がX_nとな…
http://arc078.contest.atcoder.jp/tasks/arc078_c 問題概要 ある正整数Nが設定されている。64回以内の質問クエリでNを特定せよ。質問クエリで正整数nを投げると、「n <= N かつ str(n) <= str(N)」または「n > N かつ str(n) > str(N)」 のときYESが、そう…
http://arc082.contest.atcoder.jp/tasks/arc082_d 問題概要 砂時計に合計X[g]の砂が入っている。砂は1秒に1[g]のペースで上から下に落ちる。砂時計はr1, r2, …, rK秒後にひっくり返される。ここでQ個のクエリ(ti, ai)が与えられるので、初めに砂時計の上の…
http://arc082.contest.atcoder.jp/tasks/arc082_c 問題概要 二次元平面上のN個の点が与えられる。これらの点の部分集合Sであって凸多角形をなすものについて考える。このようなSの凸包に対し、凸包の周上の点と内部の点の数の合計をnとし、2n-|S|をSのスコ…
http://arc081.contest.atcoder.jp/tasks/arc081_d 問題概要 H×Wの2次元のマス目が与えられる。各マスは白か黒のどちらかで塗られている。任意の行または列を選びその行または列に含まれるすべてのマスの色を反転させる、という操作を好きなだけ行えるとき、…
http://arc081.contest.atcoder.jp/tasks/arc081_c 問題概要 文字列Sが与えられる。Sの部分列ではないような文字列のうち、最も短いものを求めよ。答えが複数ある場合には辞書順で最小のものを答えること。文字列はいずれも英小文字のみからなるものとする。…
http://arc080.contest.atcoder.jp/tasks/arc080_d 問題概要 1, 2, ...と順に番号の振られた無限枚のカードと、N要素の数列Xがある。数列Xに含まれる番号のカードは表向きで、それ以外は裏向きである。奇素数pと連続するp枚のカードを自由に選びそれらを裏返…
http://arc080.contest.atcoder.jp/tasks/arc080_c 問題概要 偶数N、1~Nの順列P、空の数列Qがある。Pが空になるまで以下の操作を行う。 操作: Pの隣り合う2要素を選び、順序を保ったままQの先頭に追加する。 これによってできるQのうち、辞書順で最小のもの…