E: Meaningful Mean - AtCoder Regular Contest 075 | AtCoder 問題概略 長さNの数列Aで、算術平均がK以上になる区間はいくつあるか。制約 N 10 ^5 a,K 解法 ある区間の算術平均がK異常かを判定するには、sum - K * len が0以上かを見ればいい。 これはaの各…

問題概略 (sx,sy)から(tx,ty)まで移動しようとしています。好きな向きへ速さ1で移動できる。 平面上にN個のバリアが貼ってあり、それぞれ半径が与えられる。 バリアは互いに重なっていることがある。 ゴールへ向かう時、バリアの外にいる時間は最短で何か。…

D - 通勤 問題概略 x軸上にN個のガソリンスタンドがあり、D地点にゴールがある。 地点0から燃料Fでスタートし、燃料がT未満でスタンドに着いた時、Fまで補充する。 ガソリンスタンドをいくつか壊した時、ゴールまでたどり着ける組み合わせはいくつか。解法 d…

C - Kill/Death 問題概略 1000個の物を100個の箱に入れたい、また、いくつかの区間で昇順になっている必要がある。N,M sum 解法 昇順について考えなければ、桁DPとして解ける。 dp[i][rem] := iまで見ていて、残り使える合計がrem 昇順になっていないといけ…

C: 駆引取引 - 「みんなのプロコン 2018」 | AtCoder制約 1≤N≤18 1≤xi,ci,vi≤10^15 与えられる入力は全て整数解法 この記事を参考にしました というかそのままです 駆引取引 [「みんなのプロコン 2018」C] - はまやんはまやんはまやんn個を売った時に、買え…

問題概略 ()からなる文字列が与えられる。 空文字列 ある括弧の対応が取れている文字列 A,B が存在し、 A,B をこの順に連結した文字列 ある括弧の対応が取れている文字列 A が存在し、 (, A, ) をこの順に連結した文字列 以上を括弧の対応が取れている文字列…

D - IntegerotS問題概略 N個の非負整数がああり、それぞれに価値がある。 いくつかをKを超えないようにorを取った時に価値を最大化したい。制約 1≤N≤105 0≤K 0≤Ai 1≤Bi≤109(1≤i≤N) 入力は全て整数である解法 最初桁DPのようなことをやろうとした。oo桁目以降…

問題概略 N個の正の整数が与えられる。 xorがKになるような選び方は何通りか制約 N K sum(ai) 解法 O(NK)が間に合うなら、[i][k] := i番目までの中からkを作る通り として [i+1][k] += [i][k] [i+1][k^A[i]] += [i][k] と現状から遷移できるものを足していけ…

問題概略 N+1人の参加者がいて、そのうちの一人とその他の時差が渡される。 片方の都市が0時の時、その値はmin(d,24-d)となる 1 0解法 答えは0~12なので全部試した。 基準の時刻を0として、その他の時刻をdiとしソートした。 左から順に見ていき、間がt秒未…

C: Gr-idian MST - CODE FESTIVAL 2016 qual B | AtCoder 問題概略 (H+1)*(W+1)個の頂点がある。 隣り合う縦に辺を貼るのに必要なコストはxの大きさにかかわらずpi 横も同様にqiかかる。 最小で全域機を作れ制約 H,W p,q解法 線を引いて考えてみると、辺の本…

B - GCD Sequence問題概略 要素数がNで互いに異なる整数であり、どの要素もそれ以外の合計との最大公約数が1ではなく、すべての要素の最大公約数が1であり、すべては30000以下である物を求めよ 3解法 ある要素とそれを除く要素の合計の最大公約数と、ある要…

問題概略 2個の白いボールが入った袋がN個あり、それらには数字が書いてある。 袋のボールを赤と青に塗り分けた時、(rmax - rmin) * (bmax - bmin) を最小化したい制約 N x,y 解法 全体の最大値、最小値は必ずどちらかに含まれる。 よって赤大 赤小 赤大 青…

B - 最短路問題問題概略 頂点1とiの距離がAiになるようなグラフの総数を数えよ。制約 10^5解法 全体を一気に考えると難しくなってしまう。例えば上を満たすような最小限のグラフを全通り作ってやり、そこに辺をどれだけ追加できるかのように考えると駄目。元…

問題概略 長さNの順列があり、一枚ずつ順に渡される。 自分は具体的な数字を知ることは出来ないが、選ぶ前に今までの中で最大かどうかを知ることが出来る。 K回選べるとして、最適な行動をした時に最大の数を選べる確率を求めよ。解法 状態があまりないので…

B - 石取り大作戦 問題概略 石がN個あり、先手は1~A個、後手は1~B個取れる。 最後の石を取ったほうが勝ちの場合、最適でどちらが勝つか。解法 A >=N の時は明らかに先手が勝つ。 それ以外の場合を考える。A==Bの時を考える。 N %(A+1)!=0 の時Aが勝ち、それ…

問題概略 B: ドキドキデート大作戦高橋君 - AtCoder Regular Contest 045 | AtCoder いくつかの区間が与えられる。それらの区間の中で、除いてもすべてを被覆出来る区間を出力せよ。制約 10^5解法 現状取り除いても大丈夫な区間を簡単に扱いたい。 いもす法…

B - Your Numbers are XORed... 問題概略 数列Bnが与えられる。Bi = Ai ^ A(i+1)%n となるような辞書順最小の数列Aを出力せよ。解法 xorはビットごとに計算が独立しているため、それぞれのビットについてA[0]のビットが0か1で成り立つかを見ていけば良い。 O…

問題概略 座標平面上にN個の点がある。それらとマンハッタン距離が等しい点Pを一つ求めよ。制約 1 x,y 解法 ある地点からマンハッタン距離が等しい点の集合はひし形になるため、45度回転させると正方形になる。 よって、与えられた点に回転行列(1 , -1) (45…

D - LCM Rush 問題概略 1~Nについて、lcm(i,K)を足し合わせた余りを求めよ。解法 約数は高々1400個しか無いのでgcd(i,k)の値で複数の物を纏められる。 gcd(a,b)=1の時、lcm(a,b) = a * b / gcd(a,b) より bと互いに素であるiの合計 * b / となり、iの合計は…

D - ロボット 問題概略 M,+,-からなる命令文が与えられる。Mでは+か-の方に1移動でき、+なら現在地点、-なら-現在地点をポイントに加算する。 最終的に原点に戻っている必要がある場合、最高得点はなにか。解法 される時変化する幸福量について考えてみる。 …

D - 大ジャンプ 問題概略 x軸、Y軸に平行に、Dだけ+かー動ける。N回移動した時、ある地点にたどり着く確率を求めよ解法 パスカルの三角形を用いればn個の内r個がoである確率が求められる。 今回の場合状態が4つあり、全体Nの内a,b,c,dを選ぶ確率は(N,a+b)*(a…

D - 25個の整数 問題概略 25マスがあり、そこに1~25の数を入れたい。連続する３つの数が単調変化しないような置き方は何通りあるか。 また、すでに5マス以上は埋まっている。解法 2^25が出来るので、状態を纏め上げてbitDPを使いたくなる。 しかし、何でまと…