問題 長さnの数列aが与えられる この数列に「好きな要素を1個選んで2で割る(あまりは切り捨てる)」という操作をk回行う k回の操作の後の数列としてありうるものの個数を求めよ1 0 0 解法 最後に出来る数列は各要素に操作を行った回数だけで決まる また途中で…

問題 重み付き連結無向グラフが与えられる またq個のクエリが与えられ、各クエリで頂点uiとvi間の最短距離を出力する1 m-n 1 解法 制約より、グラフから辺をm-n+1本適切に削れば木になる この木をT、削った辺をMとする Tにおける2点間の距離は、適当な頂点を…

問題 nimのある状態において、その1手で勝利を確定させられるような石の取り方をwinning moveと呼ぶ (ただし例えば(3,2,3)という状態から(1,2,3)と石を取るのと(3,2,1)とするのは別のmoveとする) 以下の条件を全て満たすnimの状態を1個作る ・山の数はn個 (1…

問題 h*wの行列aがあり、最初は(r,c)にチップが置いてある Vasyaはランダムな「今チップが置いてあるマスに書かれた数より小さい数が書いてあるマス」にチップを動かすという操作を、チップを動かせなくなるまで続ける チップを動かす度に、動かす前のマスと…

問題 長さnの数列aが与えられる aの連続する部分列のうち、総和がt未満になるものの個数を求めよ1 |a[i]| |t| 解法 とりあえず累積和sを取る a[i]が全部正なら累積和が単調増加になるから二分探索で解けるけど、今回は負の数もあるから無理 BITが使えれば各i…

問題 各頂点にAかBと書かれた無向グラフが与えられる 好きな頂点から始めて辺を辿って移動し、通った頂点に書かれた文字を順に並べて文字列を作る このとき文字A、Bのみからなる任意の文字列が作れるかどうかを判定2 1 解法 グラフが条件を満たすとき、ある…

問題 数直線上にn個のゴミがあり、左からi番目は位置a[i]にある これらを全て位置0にあるゴミ箱に入れたい ロボットが最初位置0にいて、ゴミをk個持っている状態で距離1だけ移動するには(k+1)^2だけエネルギーを使う またゴミを1個拾うのと持っているゴミを…

問題 y=yaとy=ybに挟まれた領域(チューブ)がある このチューブの両側の壁上にいくつかのセンサーが付いている (x座標は非負整数) 両側の壁上の任意の格子点を2つ選び、それらを通るようなレーザーを放射するとき、最大で何個のセンサーに同時に光を入射でき…

問題 {1}, {2}, ..., {n}というn個の集合が与えられ、これらを併合する操作をm回行う 時刻iでは要素a[i]を持つ集合とb[i]を持つ集合を併合する 次にq個のクエリが与えられるのでそれに答える クエリの内容: 要素xjとyjが同じ集合に併合されるのは何回目の操…

問題 最初キャンディがn個あり、左から昇順に1-nの番号が書かれている キャンディが1つだけになるまで以下の操作を繰り返す 操作: 番号が平方数のキャンディを全て捨て、残ったキャンディにまた左から昇順に番号をつける 最後に残るキャンディは初期状態で何…

問題 線分がn本与えられる これらのうち1本以上が通る格子点の個数を求めよ ただし異なる2本の線分は交差することはあるが同一直線上にあることはない1 ー10^6 解法 まず線分ごとに格子点の数を計算して足し合わせる (x1,y1)と(x2,y2)を結んだ線分上の格子点…

問題 h*wのグリッドのいくつかのマスにアヒルがいる (ただし各行[列]にいるアヒルはたかだか1匹) アヒルはコスト1で上下左右に1マス動かせる 全てのアヒルを連続する1行[列]に整列させるためにかかるコストの最小値を求める1 解法 ①まず全てのアヒルを上下移…

問題 タテhヨコwの長方形のいくつかのマスにコインが置いてある 「長方形全体を上下左右方向どれかに1マスぶん動かす」という操作ができ、その際に最初長方形があった領域からはみ出したマスに置いてあったコインは落下して消える 長方形に載ったコインの総…

問題 自然数nを"素数でない自然数"の和で表すとき最小で何個の数が必要か1 解法 nが3のときは3 (1+1+1) そうじゃないときはnが素数なら2 (1 + (n-1)) nが素数じゃないなら1 (n) ∵ nとn-1が両方素数になるのはn=3のときだけだから class MagicDiamonds { publ…

問題 以下の条件を満たす有向グラフを1つ作れ ・頂点数20以下で、全ての頂点には1〜Nの相異なる番号が付けられている ・辺数60以下で、全ての辺には0〜10^6の整数の長さが付けられている ・全ての辺は番号の小さい方の頂点から大きい方の頂点に向かって向き…

問題 a+bx、c*d^y (01 1 解法 2^40≒10^12だからc*d^yの方はdが2以上ならすぐ全通り試せる a+bxで表せるm以下の数字の個数を(m-a)/b+1で求めてからc*d^yを一個ずつ見ていき、その数がa+bxで表せない数なら答えを+1数字pがa+bxで表せるとき、a+bx = p ∴ x = (p…