問題概略 ()からなる文字列が与えられる。 空文字列 ある括弧の対応が取れている文字列 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を使いたくなる。 しかし、何でまと…

C - 高橋君とカード / Tak and Cards 問題概略 N枚のカードがあり数字が書かれている。これらの中から1枚以上を選び、数の平均をAにしたい。選び方は何通りあるか。制約 1 1 1解法 まず普通にナップザックとして解いてみる。 つまり、boolean[i][j]:=i枚目ま…

問題概略 高々2000個の点が与えられる、3点を選んだ時、鈍角三角形、直角三角形、鋭角三角形の数を数えよ。制約 任意の三点は同一直線上にない。解法 ある点について、偏角でソートすればいい。 角度が2周するように配列を追加してやって、自分＋180度以内に…

問題概略 A~Bの中で4か9が含まれる物の個数を答えよ。制約 A,B 解法 4か9が一つでも含まれてればいいなら包除原理使うか！と思ったけど、大変そうなので桁DPで解いた。 まとめ上げるのに必要な条件は 何桁目を見ているか 数が上限ギリギリかどうか すでに4,9…

問題概略 H*Wのマス目がある。好きなマスから好きなだけ自分より大きいマスへ隣に動ける。 移動経路の個数の余りを求めよ。制約 HW 解法 自分より大きいところへしか進めないため、閉路はない。 よって経路の数をマスごとにメモできる。 dpに-1を入れておき…

問題概略 風船がN個H[i]にあり、秒速S[i]で高さが上昇していく。 1秒に一回風船を割れるとして、割った時の最大の高さの最小値を求めよ。解法 2分法で解きたくなる。 それぞれの風船について、今まで使っていない秒数の内ぎりぎりセーフの秒数を選んでいく貪…

問題概略 ２つの整数u,v 制約 N 解法 aとbを適当に選んで、出てきたu,vを数えていきたくなる。しかし、これでは重複してしまうし、メモできるような数ではない。 ある桁のビットが1,0の時に0,1にしてもu,vが等しいと気づく。 よって1,0 は許すが0,1は許さな…

D: Median of Medians - AtCoder Regular Contest 101 | AtCoder 問題概略 長さMの数列の任意の区間[lr]の中央値でなる数列の中央値を求めよ。 10^5 N 10^9 A解法 xが中央値が満たす条件について考えてみる。 x以上の要素がs/2以上ある。 そのような物の内最…

http://www.igaris.com/math/c.pdfr個の物をN個の箱に分配するhttps://drive.google.com/file/d/1WC7Y2Ni-8elttUgorfbix9tO1fvYN3g3/view数え上げテクニック 整数問題もこれで攻略！生徒に"鳩の巣原理"を教えよう！【知っていると必ず得】｜塾講師ステーショ…

問題概略 長さKの数列A,Cが与えられる。 n >= 1で An+k = (c1 & An+k-1) xor (c2 & An+k-2) xor .....(ck & An)である時、 Amを求めよ制約 M N A &とxorが*,+なら行列のべき乗の形にして高速に解ける。 実は今回も同様に出来る。 32ビットの非負の数は&,xor…

問題概略長さ2^Nの数列がある。 (i | j) 制約 N Ai 解法 i or j が K以下ということについて考える時、i or j が0の時、1の時、...Kの時という風に分けて考えたくなる。（使い回せるし） i or j が K となるものを列挙するのは難しいが、今回知りたいのはK以…

問題概略盤面に金塊が並べてある。 また、回収装置がいくつか置いてあり上下左右の自分から連続した金塊を回収することが出来る。 好きな順番で回収装置を作動させる時、最大の金塊回収数を求めよ。制約 W,H 回収装置N 解法 回収装置を使うと4つの小さい盤面…

問題概略 括弧の対応を取る時の最小操作回数 移動回数＋変更回数制約解法 dpは状態の纏め上げだということを忘れていた。 愚直に考えると、2^100になってしまうが、現在見終わった場所、最後に変更した場所、(が開いている数が同じなら一つの状態に纏められ…

A - YahooYahooYahoo問題概略 文字列Sのyahoo....yahooへのレーヴェンシュタイン距離を求めよ。制約 10^5解法 [i]までをy,a,h,o,oにする場合で遷移していく（レーヴェンシュタイン距離を求める時と似た感じで） yahooは循環しているのでo->yへの遷移も出来る…