問題 問題概要 ビット列Sが与えられる。K以上の範囲を選んでその区間のSを反転させることができる時、最大のKを求めよ。 1<= |S| <= 105 解法 k文字目のみを変えようとした時、[0,k-1]->[0,k]を反転させることで変えることができる。 同様に[k+1,N]->[k,N]で…

問題 問題概要 ある路線には駅 1 から駅 N までの N 個の駅がある。 準急は、駅 1 に止まり、{駅 2, ..., 駅 N-1} の部分集合に止まり、駅 N に止まる。 連続する K個以上の駅に止まらないような組み合わせは何通り考えられるか、mod 109+7で求めよ。 2≤K≤N≤…

問題 問題概要 N以下の正整数であって、十進法表記したときの各桁の数の和がDの倍数であるものの個数をmod 1e9+7で求めよ。 1<=D<=102,1<=N<=10104 解法 dp[0][i][j] := (下からi桁までの数で、modがjであるものの数) dp[1][i][j] := (下からi桁までの数で、…

問題 問題概要 N,X,t[N]が与えられる。 スタミナXを持っていて、単位時間に1回復する。 t[i]にログインできるとして、j(1<=j<=N)回プレイした時に使える最大のスタミナはいくつか、全て出力せよ。 なおゲームをプレイするとその度に使い切るものとする。 1<=N…

問題 問題概要 自然数A,Bが与えられる。 A <= m <= Bなる自然数を選んだ全てが互いに素でなければならないという制約のもと非負整数個選ぶとき、選び方は何通りか。 1 <= A <= B <= 1018 B - A <= 35 解法 全探索して間に合う。その理由は解説参照。 特に6の…

E - MUL 問題概要 整数a1,a2,..,aNが与えられる。 ある自然数kを選び、N以下の全てのkの倍数ik(i>=1)についてa_ik = 0にするという操作が可能な時、 a1,a2,...,aNの総和の最大値を求めよ。 1<=N<=100, |ai| <= 109 解法 MinCutする。 1〜Nの整数をノードとし…

B - GCDロボット 問題概要 N,Z,aiが与えられる。 全てのiについて、gcd(X,a[i])=gcd(Z,a[i])なる最小のXを求めよ。 1<=N<=105,1<=Z,a[i]<=1018 解法 答えから書くと、lcm_(0<=i

問題 問題概要 Kの正の倍数の10進数での各桁の和として最小のものを求めよ。 2<=K<=105 解法 1を以下の2種類の操作でKの倍数にすることを考える。 1. 1増やす 2. 10倍する この2種類の操作で全ての自然数が作れる。 また、1の位の数が9の時には1を使わないと…

問題 問題概要 文字列Sが与えられる。 Sを各々が並び替えれば回文にできるような部分文字列に分割するときその最小数を求めよ。 1 <= |S| <= 2*105 解法 回文条件を言い換えると、「文字列の中に奇数回出てくるようなアルファベットはたかだか1種類である」…

問題 問題概要 ビット列Sが与えられる。 "101" -> "010" の変換ができる。最大何回できるか。 解法 dp[i] = (i番目までの文字で最大何回変換できるか) とおく。 変換には二種類あり、もともとある101を変換するか、変換によってできた101を変換するかである…

反転 POJ3185 – The Water Bowls 問題訳 20個のビット列が与えられる。1つを反転させると両隣のビットも反転される。 全てを0にするのに必要な反転の最小回数は？ 解法 最初のビットを反転するかを決めると、全部決まるので2通り メモ 配列を初期化するのと…

基本的な動的計画法 POJ3176 – Cow Bowling 問題訳(かなり意訳) 列に1,2,...,N個ずつ三角形でボーリングのピンが並んでいる。 ボーリングのピンには点数 がついていて、ボールは三角形の一番上から下の二つの隣接するピンを倒すことができ、一番下に向けて動…

4章 数学的問題 mod POJ1150 – The Last Non-zero Digit POJ1284 – Primitive Roots POJ2115 – C Looooops POJ3708 – Recurrent Function POJ2720 – Last Digits GCJ Japan 2011 決勝B – バクテリアの増殖 行列 POJ2345 – Central heating POJ3532 – Resista…

3章 二分探索 最小値の最大化 POJ3258 – River Hopscotch POJ3273 – Monthly Expense POJ3104 – Drying POJ3045 – Cow Acrobats 平均最大化 POJ2976 – Dropping tests POJ3111 – K Best k番目の値を探索 POJ3579 – Median POJ3685 – Matrix k番目を最小化 PO…

2章 全探索 DFS POJ1979 – Red and Black POJ3009 – Curling 2.0 AOJ0118 – Property Distribution AOJ0033 – Ball WFS AOJ0558 – Cheese POJ3669 – Meteor Shower AOJ0121 – Seven Puzzle 全列挙 POJ2718 – Smallest Difference POJ3187 – Backward Digit S…