問題概要 与えられる整数n, kに対して、各行・各列をみたとき異なる数がちょうどk個存在するようなn * nのグリッドを構成せよ。解が複数ある場合は使われる数の種類が最大になるものを答えること。 3 <= n <= 50 1 <= k <= n/2 解法 1 2 3 0 0 0 0 4 5 6 0 0…

問題概要 0～9の各数字について、それぞれを何回まで使ってよいかを示した配列amountが与えられる。amountの制限を守って桁数がblank1の非負整数A, blank2の非負整数Bをつくるとき、ありえるA, Bのすべての組合せにおけるA*Bの総和を求めよ。 max(amount) <=…

問題概要 整数d, kが与えられる。最短距離がdであるような頂点のペアがちょうどk個あるような無向グラフを構成せよ。ただしすべての辺の距離は1とし、辺・頂点とも最大で1000個までとする。 2 <= d <= 50 1 <= k <= 50000 解法 (D-1)個の頂点を一直線につな…

問題概要 ある連続した期間の前半d1日で合計w1個の単語を覚え、後半d2日で合計w2個の単語を覚えたい。任意の連続する2日間において覚える単語の数が高々1しか変わらないように単語を覚えるという制約のもとで、このような単語の覚え方が可能か判定せよ。 d1,…

http://tdpc.contest.atcoder.jp/tasks/tdpc_cat 問題概要 1～Nまでの番号がついたN匹の猫がいる。任意の猫2匹の組合せには親密度が設定されており、各猫の幸福度は自分との距離が1以内のところにいるすべての猫との親密度の和で定義される。1次元の数直線上…

http://tdpc.contest.atcoder.jp/tasks/tdpc_target 問題 半径ri, 中心(xi, 0)のN個の円が与えられる。この中からどの2円をとっても片方がもう片方の内部に厳密に含まれるようにいくつかの円を選ぶとき、選べる円の最大数を求めよ。 解法 円cとx軸上の2交点…

http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi 問題概要 iとwの2種類の文字のみからなる文字列Sが与えられる。Sのある連続部分文字列が"iwi"となっているとき、その部分を取り除く操作を行うことができる。Sに対して最大何回この操作を行えるか求めよ。 |S…

http://tdpc.contest.atcoder.jp/tasks/tdpc_knapsack 問題概要 N個のものがあって、それぞれに重さw・価値v・色cが設定されている。重さ合計の最大値Wと使える色の種類の最大値Cが与えられるので、その範囲内で価値の合計が最も高くなるような組合せを選ん…

http://tdpc.contest.atcoder.jp/tasks/tdpc_ball 問題概要 一次元の座標xiにN個の目標物が設置されている。座標xを狙ってボールを投げると等確率でx-1, x, x+1のいずれかにボールが飛んでいき、そこに目標物があればそれを倒せる。狙う座標を最適に選んだと…

http://codeforces.com/contest/854/problem/D 問題概要 (N+1)個の町があり、1～Nの町に一人ずつ人が住んでいる。また 町0 → 町(1～Nのどれか) に飛ぶ飛行機と、町(1～Nのどれか) → 町0 に飛ぶ飛行機の2種類がある。飛行機を使って1～Nの町の人を全員町0に呼…

https://csacademy.com/contest/round-46/task/ultimateorbs/ 問題概要 N個のオーブが座標1～Nに順番に並んでいる。各オーブには強さGiが設定されており、左隣あるいは右隣のオーブに対して 自分の強さ＋D >= 相手の強さ であればそのオーブを吸収できる。吸…

http://codeforces.com/contest/850/problem/C 問題概要 先手と後手に分かれて以下のような2人ゲームを行う。まずN要素の数列Aが与えられる。プレイヤーは手番ごとに素数pと正整数kを選び、数列のうちpkで割り切れる要素をpkで割る。ただしどの要素も割り切…

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://codeforces.com/contest/850/problem/B 問題概要 N要素の数列Aが与えられる。以下の操作を好きなだけ繰り返して、数列の全要素のGCDが1でなくなるようにしたい。目的を達成する最小のコストを求めよ。 操作1. コストxで数列から任意の1要素を取り除く…

http://codeforces.com/contest/850/problem/A 問題概要 5次元空間上のN個点が与えられる。この中のある点aについて、異なる点b, cを取ってきたときにab, acのなす角が90度未満となるb, cが存在するとき、aを悪い点と呼び、そうでない場合良い点と呼ぶ。良い…