kurarrr's memooo

主に競プロ備忘録

CODE FESTIVAL qual C - D Yet Another Palindrome Partitioning (700)

AtCoder 競プロ DP DPのkeyの変換 文字列

問題概要

文字列Sが与えられる。
Sを各々が並び替えれば回文にできるような部分文字列に分割するときその最小数を求めよ。
1 <= |S| <= 2*105

解法

回文条件を言い換えると、「文字列の中に奇数回出てくるようなアルファベットはたかだか1種類である」となる。
文字列sに対して以下を満たすようにh(s)を定める。

'a' の出現回数 % 2 -> h(s)の1ビット目
'b' の出現回数 % 2 -> h(s)の2ビット目
....
'z' の出現回数 % 2 -> h(s)の26ビット目
ここで、h(s) = (0 または 1<<k) (0<=k<26)であればsは回文条件を満たす。

Sに対して、a[i] = h(S[0,i))と定める。
すると、h(S[l,r)) = a[l] ^ a[r] である。

以下のようなDPが組める。以下0<=k<26とする。
opt(i) = min(S[0,i)の分割回数),opt(0)=0として、
opt(i) = min_(0<=j<=i かつ a[j]^a[i]=0 or 1<<k )(opt(j)+1)
ただこれはO(N2)なので間に合わない。

ここで,
a[j] ^ a[i] = 0 <-> a[i] = a[j]
a[j] ^ a[i] = (1 << k) <-> a[i] = a[j] ^ (1<<k)
cf. (a ^ b) ^ c = a ^ (b ^ c), a ^ a=0
であることに注目すれば,(すなわち同じか1bitしか変わらない)
h(s)を引数とすれば遷移式には26個のminを取れば良いことがわかる。

すなわちdp[x]=min(h(s[0,x))なるsの交換回数)として、
初期状態 dp[0] = 0,
遷移式 dp[x] = min(dp[x],dp[x ^ (1<<k)])
dp[a[N]]が答えとなる。
ただし、a[N]=0の時dp[a[N]]=1となるので、max(dp[a[N]],1)とする。

メモ

O(N2)っぽい解法は思いついたが書けなかった。 回文条件の言い換えは応用が多そうなので押さえておきたい。 それとxorをスマートに書けるように。 a[0]=a[1<<k]=1として初期化したら通らなかったのだがなぜだろう。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 200005;
const ll lmod = 1e9+7;

int dp[1<<26];
int a[MAX_N]; //[0,i)のハッシュ値
int C = 26;
string S;

int main(){
  cin >> S ;
  int N = S.size();
  rep(i,N){
    int b = S[i] - 'a';
    a[i+1] = a[i] ^ (1<<b);
  }
  fill(dp,dp+(1<<26),INF);
  dp[0] = 0;
  REP(i,1,N+1){
    rep(j,C){
      int bit = 1<<j;
      dp[a[i]] = min(dp[a[i]],dp[a[i]^bit]+1);
    }
  }
  cout << max(1,dp[a[N]]) << endl;
  return 0;
}

CODE FESTIVAL qual B - D 101 to 010

AtCoder 競プロ

問題概要

ビット列Sが与えられる。
"101" -> "010" の変換ができる。最大何回できるか。

解法

dp[i] = (i番目までの文字で最大何回変換できるか) とおく。
変換には二種類あり、もともとある101を変換するか、変換によってできた101を変換するかである。
後者は、101の前または後ろに1が並んでいるケースに限られる。
ex1. 10111 -> 01011 -> 00101 -> 00000
ex2. 11101 -> 11010 -> ...
よって101を見つけて、前後に1の列があればその変換から広がるdp[i]の値の変化を追っていけばいいことがわかる。
またSの前後に番兵の'0'を置いておくと末端の処理を書かなくていいので楽。

メモ

DPっぽいというのはわかったが、書けなかった...
やるだけとか言えるようになりたい

コード

#include<stdio.h>
#include<iostream>
#include<string>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 500005;
const ll lmod = 1e9+7;

int dp[MAX_N];

int main(){
  int N;
  string S;
  cin >> N >> S;
  fill(dp,dp+N,0);
  S = "0" + S + "0";
  REP(i,1,N+1){
    dp[i+1] = max(dp[i],dp[i+1]);
    if(S[i-1]=='1'&&S[i]=='0'&&S[i+1]=='1'){
      int a,b;
      a = i-1;
      b = i+1;
      while(1){
        if(S[a]=='0') break;
        dp[i+1] = max(dp[i+1],dp[a-1]+i-a);
        a--;
      }
      while(1){
        if(S[b]=='0') break;
        dp[b] = max(dp[b],dp[i-2]+b-i);
        b++;
      }
    }
  }
  // rep(i,N+2) cout << dp[i] << ",";
  // cout << "" << endl;
  // rep(i,N+2) cout << S[i] << ",";
  // cout << "" << endl;
  cout << dp[N+1] << endl;
  return 0;
}

蟻本練習問題(反転)

競プロ

反転

問題訳
20個のビット列が与えられる。1つを反転させると両隣のビットも反転される。
全てを0にするのに必要な反転の最小回数は？

解法
最初のビットを反転するかを決めると、全部決まるので2通り

メモ
配列を初期化するのと最初の反転をカウントするのを忘れていた。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N=100005;

int a[22],c[22];

int main(){
  rep(i,20) cin >> a[i] ;
  rep(i,20) c[i]=a[i];
  int ans=INF;
  rep(j,2){
    int cnt=0;
    rep(i,20) a[i]=c[i];
    if(j){
      a[0]^=1; a[1]^=1; cnt++;
    }
    rep(i,19){
      if(a[i]==1){
        a[i]^=1; a[i+1]^=1; a[i+2]^=1;
        cnt++;
      }
    }
    if(a[19]==0) ans=min(ans,cnt);
  }
  cout << ans << endl;
  return 0;
}

問題訳
5x6のマスがあり、1マスを反転させると隣接4マスも反転するようなパズルがある。
パズルの答えを示せ。(最小回数でなくとも良い)

解法
1行目を決めるとパタパタ決まる。

メモ
またも配列の初期化ミスってしんどいことに…

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N=1002,MAX_K=102;

int a[5][7],c[5][7],ans[5][7];
int dx[5]={0,-1,0,1,0};
int dy[5]={0,0,1,0,-1};

void rev(int i,int j){
  rep(k,5){
    if((i+dy[k]>=0 &&i+dy[k]<5)&&(j+dx[k]>=0 && j+dx[k]<6)){
      c[i+dy[k]][j+dx[k]]^=1;
    }
  }
}

void calc(){
  rep(i,5) rep(j,6) scanf("%d",&a[i][j]);
  bool ok=false;
  rep(i,1<<6){
    rep(j,5) rep(k,6) c[j][k]=a[j][k];
    rep(j,5) rep(k,6) ans[j][k]=0;
    rep(j,6){
      ans[0][j]=(i>>j)&1;
      if(ans[0][j]){
        rev(0,j);
      }
    }
    REP(j,1,5){
      rep(k,6){
        if(c[j-1][k]){
          rev(j,k);
          ans[j][k]=1;
        }
      }
    }
    ok=true;
    rep(k,6){
      if(c[4][k]) ok=false;
    }
    if(DEBUG){
      cout << "cnt" << i << endl;
      rep(k,5){
      rep(j,5) cout << ans[k][j] << " " ;
        cout << ans[k][5] << endl;
      }
      cout << "--------" << endl;
      rep(k,5){
        rep(j,5) cout << c[k][j] << " " ;
        cout << c[k][5] << endl;
      }
      cout  << endl;
    }
    if(ok) break;
  }
  if(ok){
    rep(i,5){
      rep(j,5) cout << ans[i][j] << " " ;
      cout << ans[i][5] << endl;
    }
  }
}

int main(){
  int n;
  cin >> n ;
  rep(i,n){
    cout << "PUZZLE #" << i+1 << endl;
    calc();
  }
  return 0;
}

蟻本練習問題(DP)

競プロ

基本的な動的計画法

問題訳(かなり意訳)

N(1\leq N \leq 350) 列に1,2,...,N個ずつ三角形でボーリングのピンが並んでいる。
ボーリングのピンには点数 K(0 \leq K \leq 99) がついていて、ボールは三角形の一番上から下の二つの隣接するピンを倒すことができ、一番下に向けて動く。
得られる最大の点数は何点か。

ex.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

この場合だと 7 -> 3 -> 8 -> 7 -> 5 で30点が最高点。

解法
かなりわかりやすいDP。

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N=351;

int dp[MAX_N][MAX_N],a[MAX_N][MAX_N];

int main(){
  int N;
  cin >> N ;
  rep(i,N){
    rep(j,i+1) scanf("%d",&a[i][j]);
  }
  fill(dp[0],dp[MAX_N-1],-1);
  dp[0][0]=a[0][0];
  rep(i,N-1){
    rep(j,i+1){
      dp[i+1][j]=max(dp[i+1][j],dp[i][j]+a[i+1][j]);
      dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+a[i+1][j+1]);
    }
  }
  int ans=-1;
  rep(i,N) ans=max(ans,dp[N-1][i]);
  cout << ans << endl;
  return 0;
}

問題訳
自然数 N(1\leq N \leq 10^{6}) が与えられる。
Nを 2^{k} (k \geq 0) の和だけで表す方法は何通りあるか。

解法 まず書き出してみる。
1=1 ...1
2=2=1+1 ...2
3=1+2,1+1+1 ...2
4=4=2+2=1+1+2=1+1+1+1 ...4
5=1+(4の表し方) ...4
Nの組み合わせ数をdp[N]とすれば、N=奇数の時 dp[N]=dp[N-1]は容易に得られる。
なぜならNは奇数であるため、和で表した時少なくとも1つ、1が入るためである。
一方、Nが偶数であれば1を一つも使わずに表すことができるため、これは成り立たない。
しかし、その時は分解した和が全て偶数だからN/2を和で表したものを2倍したものと考えることができる。 よって、

$$ dp[n]=\begin{cases} dp[n-1] & (n=odd) \\ dp[n-1] + dp[n/2] & (n=even) \end{cases} $$

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N=1e7;

ll dp[MAX_N];

int main(){
  int N;
  cin >> N ;
  dp[1]=1;
  REP(i,2,N+1){
    if(i%2) dp[i]=dp[i-1]%int(mod);
    else dp[i]=(dp[i/2]+dp[i-1])%int(mod);
  }
  cout << dp[N] << endl;
  return 0;
}

問題訳
毎秒、木1と木2のどちらかからりんごが落ちてくる。牛のベシーは木の真下にいればりんごをキャッチすることができる。
最大移動回数W(1\leq W \leq 30)回の元で、T(1\leq T \leq 1000)秒間の間に最大何個のりんごを得られるか。

解法
i秒後、j回移動して得られる最大のりんごの数をdp[i][j]とする。
今どちらかにいるかは j%2 +1 で得られる。 dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])と、
今いる場所に落ちてくるなら dp[i][j]++ を繰り返せば答えが得られる。
木をN本に拡張してもできそう。その場合はjは今いる木の場所になるのかな。

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_T=1002,MAX_W=31;

int dp[MAX_T][MAX_W];

int main(){
  int T,W;
  cin >> T >> W ;
  fill(dp[0],dp[T+1],0);
  REP(i,1,T+1){
    int fall;
    cin >> fall ;
    rep(j,W+1){ 
      if(j>0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);
      else dp[i][j]=dp[i-1][j];
      int now = j%2+1;
      if(now==fall) dp[i][j]++;
    }
  }
  int ans=-1;
  rep(j,W+1) ans=max(ans,dp[T][j]);
  cout << ans << endl;
  return 0;
}

問題訳 次のN時間で最大の牛乳を得られるようにしたい。
搾乳することができる時間はM区間あり、それぞれでs_iからe_iまで時間がかかり、effi_iだけ牛乳が得られる。
また、牛は一回搾乳をするごとにR時間休ませる必要がある。(つまりi個目の区間で搾乳をするとe_i+Rから搾乳を再開できる)

入力
N M R
s_1 e_1 effi_1
. .
s_M e_M effi_M

$$ 1\leq R \leq N \leq 10^{6}
1 \leq M \leq 10^{3}
1 \leq s_i \leq e_i \leq N
1 \leq effi_i \leq 10^{6}
$$

解法 各区間を開始時間でソートする。
区間に関するDPを立てて解く。
dp[i] := (i番目以降の区間を用いた場合の最大搾乳量)とする。
i番目の区間で搾乳をしないとすると、dp[i+1]だけ搾乳できる。
搾乳をするならば、開始時間がe_i+R以上になるような最小の数をj\leq iとすれば、
dp[j]+effi_i だけ搾乳することができる。そのようなjは二分探索で発見できる。
よって dp[i]=max(dp[i+1],dp[j]+effi_i)
求める答えはdp[0]
計算時間は検索で二分探索を用いているのでO(MlogM)。 M〜103なので二分探索を用いなくても間に合う。

メモ
何に関するDPを立てるのかパッと思いつかなかった。Nでやるとちょっと怖そうだしなーと。
Nに関するDPでもできるっぽい
POJ-3616 : Milking Time
後ろからやるの、思いつかない。

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_M=1002;

vector<pair<P,ll>> term;
ll dp[MAX_M];

int main(){
  int N,M,R;
  cin >> N >> M >> R ;
  term.resize(M);
  rep(i,M){
    int s,e;
    ll ef;
    scanf("%d%d%lld",&s,&e,&ef);
    term[i].first.first = s;
    term[i].first.second = e;
    term[i].second = ef;
  }
  sort(ALL(term));
  dp[M-1] = term[M-1].second;
  for(int i=M-2;i>=0;i--){
    pair<P,ll> temp;
    temp.first.first = term[i].first.second+R;
    temp.first.second = -1;
    int _m = lower_bound(term.begin(),term.end(),temp) - term.begin();
    if(_m==M) dp[i] = max(dp[i+1],term[i].second);
    else dp[i] = max(dp[i+1],dp[_m]+term[i].second);
  }
  cout << dp[0] << endl;

  return 0;
}
  • POJ3280 – Cheapest Palindrome
    N種類のアルファベットからなるM字の文字列が与えられる。
    各アルファベットの追加と削除のコストが与えられた時、文字列を回文にするためのコストを求めよ。
    input
    N M
    S(M文字の文字列)
    a (aを追加するコスト) (aを削除するコスト)
    ...
    (M番目のアルファベット) (追加するコスト) (削除するコスト)
    1 \leq N \leq 26 , 1 \leq M \leq 2*10^{3}, 1\leq cost \leq 10^{4}

解法
区間DP。
dp[i][j] := [i,j)を回文にするコストとする。
すると
S[i] = S[j-1] のとき S[i][j] = min(dp[i][j-1] + cost[S[j-1]] , dp[i+1][j] + cost[S[i]] , dp[i+1][j-1])
そうでないとき S[i][j] = min(dp[i][j-1] + cost[S[j-1]] , dp[i+1][j] + cost[S[i]] )
である。これを(i,j) = (0,2),(1,3),..,(M-2,M), (0,3),...,(M-3,M),...,(0,M)と回していけば良い。
dp[i][i+1] = 0 (1文字でもともと回文のため)
求める答えは dp[0][M]。計算量はO(M2)

メモ
区間DPの書き方が慣れない。あとうまい書き方が知りたい。

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60,lmod=1e9+7;
const int MAX_N=2003;

ll dp[MAX_N][MAX_N];
map<char,ll> cost;

int main(){
  int N,M;
  cin >> N >> M ;
  string S;
  cin >> S ;
  rep(i,N){
    char c;
    ll a,b;
    cin >> c >> a >> b ;
    cost[c] = min(a,b);
  }
  fill(dp[0],dp[MAX_N-1],0);
  REP(j,2,M+2) REP(i,0,M-j+2) {
    ll temp = min(dp[i][i+j-1]+cost[S[i+j-1]],dp[i+1][i+j]+cost[S[i]]);
    if(S[i]==S[i+j-1]) dp[i][i+j] = min(temp,dp[i+1][i+j-1]);
    else dp[i][i+j] = temp;
    //cout << i << ","<< i+j << ":" << dp[i][i+j] << endl;
  }
  cout << dp[0][M] << endl;
  return 0;
}

参考
基本的な動的計画法(5題)
大いに参考にさせていただきました...

蟻本練習問題まとめ3

競プロ

4章

数学的問題

mod

行列

数え上げ

ゲーム

考察、DP

Nim、Grundy数

グラフ

強連結成分分解

2-SAT

LCA

頻出テクニック

スタック

デック

賢く探索

枝刈り

A,IDA

分割統治法

列の分割統治

平面の分割統治

ツリーの重心分解

文字列

DP

文字列検索

接尾辞配列

蟻本練習問題まとめ2

競プロ

3章

二分探索

最小値の最大化

  • POJ3258 – River Hopscotch
  • POJ3273 – Monthly Expense
  • POJ3104 – Drying
  • POJ3045 – Cow Acrobats

平均最大化

  • POJ2976 – Dropping tests
  • POJ3111 – K Best

k番目の値を探索

  • POJ3579 – Median
  • POJ3685 – Matrix

k番目を最小化

  • POJ2010 – Moo University – Financial Aid
  • POJ3662 – Telephone Lines

その他

  • POJ1759 – Garland
  • POJ3484 – Showstopper

その他テクニック

しゃくとり法

  • POJ2566 – Bound Found
  • POJ2739 – Sum of Consecutive Prime Numbers
  • POJ2100 – Graveyard Design

反転

  • POJ3185 – The Water Bowls
  • POJ1222 – Extended Lights Out

弾性衝突

  • POJ2674 – Linear world

半分全列挙

  • POJ3977 – Subset
  • POJ2549 – Sumsets

座標圧縮

  • AOJ0531 – Paint Color

データ構造

BIT

  • POJ1990 – MooFest
  • POJ3109 – Inner Vertices
  • POJ2155 – Matrix
  • POJ2886 – Who Gets the Most Candies?

Segment Tree、バケット法

  • POJ3264 – Balanced Lineup
  • POJ3368 – Frequent values
  • POJ3470 – Walls
  • POJ1201 – Intervals
  • UVa11990 – Dynamic Inversion

DP

bitDP

  • POJ2441 – Arrange the Bulls
  • POJ3254 – Corn Fields
  • POJ2836 – Rectangular Covering
  • POJ1795 – DNA Laboratory
  • POJ3411 – Paid Roads

行列累乗

  • POJ3420 – Quad Tiling
  • POJ3735 – Training little cats

データ構造を用いて高速化

  • POJ3171 – Cleaning Shifts

ネットワークフロー

最大流・最小カット

  • POJ3713 – Transferring Sylla
  • POJ2987 – Firing
  • POJ2914 – Minimum Cut
  • POJ3155 – Hard Life

二部マッチング

  • POJ1274 – The Perfect Stall
  • POJ2112 – Optimal Milking
  • POJ1486 – Sorting Slides
  • POJ1466 – Girls and Boys
  • POJ3692 – Kindergarten
  • POJ2724 – Purifying Machine
  • POJ2226 – Muddy Fields
  • AOJ2251 – Merry Christmas

最小費用流

  • POJ3068 – “Shortest” pair of paths
  • POJ2195 – Going Home
  • POJ3422 – Kaka’s Matrix Travels
  • AOJ2266 – Cache Strategy
  • AOJ2230 – How to Create a Good Game
  • POJ3068 – “Shortest” pair of paths
  • POJ2195 – Going Home
  • POJ3422 – Kaka’s Matrix Travels
  • AOJ2266 – Cache Strategy
  • AOJ2230 – How to Create a Good Game

計算幾何

ギリギリを考える

  • POJ1981 – Circle and Points
  • POJ1418 – Viva Confetti
  • AOJ2201 – Immortal Jewels

平面走査

  • POJ3168 – Barn Expansion
  • POJ3293 – Rectilinear polygon
  • POJ2482 – Stars in Your Window

凸包

  • POJ1113 – Wall
  • POJ1912 – A highway and the seven dwarfs
  • POJ3608 – Bridge Across Islands
  • POJ2079 – Triangle
  • POJ3246 – Game
  • POJ3689 – Equations

数値積分

  • AOJ2256 – Divide the Cake
  • AOJ2215 – Three Silhouettes

蟻本練習問題まとめ1

競プロ

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 Sums
  • POJ3050 – Hopscotch
  • AOJ0525 – おせんべい

貪欲法

  • POJ2376 – Cleaning Shifts
  • POJ1328 – Radar Installation
  • POJ3190 – Stall Reservations
  • POJ2393 – Yogurt factory
  • POJ1017 – Packet
  • POJ3040 – Allowance
  • POJ1862 – Stripies
  • POJ3262 – Protecting the Flowers

DP

  • POJ3176 – Cow Bowling
  • POJ2229 – Sumsets
  • POJ2385 – Apple Catching
  • POJ3616 – Milking Time
  • POJ3280 – Cheapest Palindrome
  • POJ1742 – Coins
  • POJ3046 – Ant Counting
  • POJ3181 – Dollar Dayz
  • POJ1065 – Wooden Sticks
  • POJ1631 – Bridging signals
  • POJ3666 – Making the Grade
  • POJ2392 – Space Elevetor
  • POJ2184 – Cow Exhibition

データ構造

Priority Queue

  • POJ3614 – Sunscreen
  • POJ2010 – Moo University – Financial Aid

Union-Find Tree

  • POJ2236 – Wireless Network
  • POJ1703 – Find them, Catch them
  • AOJ2170 – Marked Ancestor

グラフ

最短路

  • AOJ0189 – Convenient Location
  • POJ2139 – Six Degrees of Cowvin Bacon
  • POJ3259 – Wormholes
  • POJ3268 – Silver Cow Party
  • AOJ2249 – Road Construction
  • AOJ2200 – Mr. Rito Post Office

最小全域木

  • POJ1258 – Agri-Net
  • POJ2377 – Bad Cowtractors
  • AOJ2224 – Save your cats
  • POJ2395 – Out of Hay

数学的な問題

互除法

  • AOJ0005 – GCD and LCM
  • POJ2429 – GCD & LCM Inverse
  • POJ1930 – Dead Fraction

素数

  • AOJ0009 – Prime Number
  • POJ3126 – Prime Path
  • POJ3421 – X-factor Chains
  • POJ3292 – Semi-prime H-numbers

繰り返し二乗法

  • POJ3641 – Pseudoprime numbers
  • POJ1995 – Raising Modulo Numbers