takatm @ ウィキ
takatm @ ウィキ

トップページ

topcoder srmのコツ


基本方針

  • 全探索をまず考える
  • 計算量を調べる
  • 問題文をきちんと理解する。サンプルまでフローを並べる。
  • 条件から法則を導き出せないか？(SRM564,569,578)

問題別

  • 全探索の考え方
5.0*10^7あたりが計算時間ギリギリ(SRM428)
ひとつのパラメータを固定することで、全探索できないか？(SRM551)
ある状態を配列に保存することで、全探索できないか？(SRM556)
  • 全探索可能な場合
すべての状態をdpする(SRM575)
  • 全探索ではすべてのポイントを調べられない場合
→調べるポイントを減らすことができないか？(SRM580,586)
→適当な数までサンプル出力し、法則をながめる(SRM571,572,575)
   (入力、出力すべてについて法則がないかながめる)(SRM543)
→例外条件があり全探索できない場合、例外条件がない初期状態にしたうえで全探索(SRM568)
→探索の範囲のグループ化(SRM567,572)
→同じシミュレーションを削減することができないか？(SRM562,570) 
→処理を逆にすることで解けないか？(最終→最初の状態)(SRM533) 
   (分割統治法は動的計画法と組み合わせる)
→全ての値を保存するのでは間に合わない場合、範囲の保存で計算量削減できないか？(SRM539)
  • 座標の問題
ｘ軸とｙ軸を分けて処理できないか(SRM546)
図を書いて法則を導けないか？(SRM546)
２つの比較では区別する必要は本当にあるのか？最小と最大だけで処理できないか？(SRM546)
  • ある状態を求める問題
そのうち、ひとつひとつの状態を順に決めていく処理ができないか(SRM545)
  • グラフの最短距離を求める問題　
→ワーシャルフロイド SRM583
  • 状態が簡単にtrue/falseと表わすことができる　
→２分探索(SRM548,582)
  • 最小と最大、辞書順が関係する問題
→ソートする(SRM536,571,573)
→グラフに各値をプロットしてみる(SRM536)
  • 場合の数を求める問題
Cの順列のとき、今の状態と残りの状態をＤＦＳで解くことができないか？(SRM531)
パターンごとに条件分岐で表わせないか(SRM554)
状態遷移図で条件分岐に落とせないか(SRM546)

  • シミュレーション問題
いかにコーディングを単純にするか？
判定条件を導き出す(SRM581)
制約になりそうで無視できる条件はないか？(SRM534)
エラー状態がある場合：判定のループを２つに分けると単純化できないか(SRM550,557)
データ構造：割り当てごとの平均値を求める(SRM577)
座標単位のシミュレーション：選んだシミュレーション単位であっているか？0.5単位でなくてもよいか？(SRM541)
  • ２人のゲーム
「勝ちとなるパターン」を見つける(SRM574,575)

Challenge

  • "<"と"<="の調べる点が重複していないか？ SRM586
  • 答えの状態はひとつしかないか？複数ある場合は全て比較して最小／最大を求める(SRM579)
  • 配列のサイズ：10^6を超えていないか？ SRM585
  • 0,1等の初期条件の値は問題文に定義が書いていないか？ SRM585
  • 答えの文字数が１つ、２つの条件を同時に満たす場合も調べる(SRM574)
  • ワーシャルフロイド、(i,i)は答えに含めてもよいか？ SRM584
  • 定義した方向だけでよいか？逆方向は存在しないか？SRM583
  • long long で数字を扱うときは 1234LL のように「LL」をつける SRM582
  • 計算の方は一致させる (int)/(double)等
  • 自分の値を二重カウントしていないか(SRM573)
  • 走査する配列がひとつのとき、または他の配列と重複するときがないか(SRM532)

使える実装

  • 降順のソート
  sort(x.rbegin(),x.rend())
  • 全体の場合の数を割るとき、x*y=all のallで割るのではなくx,yそれぞれ割る(SRM547)
return ans/x/y;
  • 文字列の一致にsubstrを利用(SRM579)
if(lines[i].substr(0,lines[i-1].size())==lines[i-1])
  • 相対位置の比較の時、乗算の＋－で判定(SRM572)
FORE(i,0,n)FORE(j,i+1,n)if((start[i]-start[j])*(goal[i]-goal[j])<=0)return -1;
  • 判定ごとに配列を用意(SRM563)
 while(accumulate(num,num+26,0)>0){
  pair<char,int> best=make_pair('z'+1,-1);
  FORE(i,0,S.size()){
   if(num[S[i]-'a']==0)continue;
   int count[26]={},invalid=0;
   FORE(j,i,S.size())count[S[j]-'a']++;
   FORE(j,0,26)if(num[j]>count[j])invalid=1;
   if(invalid)continue;
   best=min(best,make_pair(S[i],i));
  }
  ans+=best.first;
  num[best.first-'a']--;
  S=S.substr(best.second+1);
 }
  • 文字列：単なるif文の判定に、FORを組み合わせられないか(SRM532)
  if(c[i][0]=='.'&&c[i][1]!='.'&&c[i][2]=='.')single=max(single,c[i][1]-'0');
  for(int j=0;j<3&&c[i][j]!='.';j++)a[i]+=c[i][j]-'0';
  for(int j=2;j>=0&&c[i][j]!='.';j--)b[i]+=c[i][j]-'0';
  • 向きを変えての移動、配列宣言とFORの組み合わせ
 int x[]={0,1,0,-1},y[]={1,0,-1,0};
 int d=0,curx=0,cury=0;
 FORE(n,1,5){
  FORE(i,0,a.size()){
   curx+=a[i]*x[d];
   cury+=a[i]*y[d];
   d=(d+a[i])%4;
  }
  move[n%4]=abs(curx)+abs(cury);
 }
  • sprintf
  string変換してもうまくいかないのでchar型を使う
  • 条件分岐後に同じ記述が重複する場合は、最初に代入を書く方法もある
 FORE(num,0,min(50,n)){
  stringstream out;
  out<<cur<<".mp3";
  ans[num]=out.str();
  if(cur*10<=n)cur*=10;
  else{
   while(cur%10==9 || cur==n)cur/=10;
   cur++;
  }
 }
  • 右と左の位置を定義して走査(SRM573)
 while(l<r){
  if(v[l]+v[r]>my){
   rank++;
   l+=2;
   r--;
  }
  else{
   l+=3;
  }
 }
  • 最小の値をお互い引く時
  long long battle=min(girlnum,enemynum);
  girlnum-=battle;
  enemynum-=battle;
  • BFS
 int DFS(int i,int j){
 int ans=1;
 queue<pair<int,int> > q;
 q.push(make_pair(i,j));
 cell[i][j]=1;
 while(!q.empty()){
  int x=q.front().first;
  int y=q.front().second;
  q.pop();
  FORE(i,0,H)FORE(j,0,W)if(cell[i][j]==0&&abs(x-i)+abs(y-j)<=D){
   cell[i][j]=1;
   q.push(make_pair(i,j));
   ans++;
  }
 }
 return ans;
}

dp

  • どの値をパラメータ、どの値を返り値にするか決める
パラメータに状態数を入れられないか（SRM565)
  • DFSよりメモ化(計算量が少ない＆明確)(SRM517)
string CompositeSmash::thePossible(int N, int target) {
 int i, j, ok, can;
 for (i=1;i<=N;i++) {
   if (i == target) {
     f[i] = 1;
     continue;
   }
   ok = 1; can = 0;
   for (j=2;j*j<=i;j++)
     if (i % j == 0) {
       can = 1;
       if (!(f[j] || f[i/j])) ok = 0;
     }
   if (can && ok) f[i] = 1;
   else f[i] = 0;
 }
 if (f[N]) return "Yes";
 else return "No";
}
  • 現在の状態から次の状態を求める(SRM547)
FORE(i,0,n-1){
  FORE(j,0,height[i+1]){
   FORE(k,0,height[i]){
    double length=sqrt(w*w+(j-k)*(j-k));
    dp[i+1][j]=max(dp[i+1][j],dp[i][k]+length);
   }
  }
 }
  • DFSとの組み合わせ
long long f(int idx,int XS, int YS){
 if(idx==P)return YS==0 ? 1 : 0;
 if(dp[idx][XS][YS]!=-1)return dp[idx][XS][YS];
 long long ans=0;
 if(YS>0)ans+=YS*f(idx+1,XS+1,YS-1)%MOD;
 if(XS-M>0)ans+=(XS-M)*f(idx+1,XS,YS)%MOD;
 return dp[idx][XS][YS]=ans%MOD;
}
  • 分割統治法(SRM533)
int solve(int l,int r){
 if(dp[l][r]!=-1)return dp[l][r];
 if(l+1==r)return 0;
 FORE(i,l+1,r)dp[l][r]=max(dp[l][r],solve(l,i)+solve(i,r)+w[l]*w[r]);
 return dp[l][r];
}

数学的考え方

  • 二項定理(SRM578)
  奇数の集合については、ｎＣ０×ｎＣ２ｘ・・・ｎＣｎ－１となる。
  二項定理により(1+x)^n=(n,0)*x^0+(n,1)*x^1...+(n,n)*x^n
  x=1,-1のとき、
  2^n=(n,0)+(n,1)+...+(n,n)
  0=(n,0)-(n,1)+(n,2)...-(n,n)
  2^n=2(n,0)+2(n,2)...+2(n,n-1)
  2^(n-1)=(n,0)+(n,2)...+(n,n-1)
  よって奇数の集合は2^(n-1)となるので、2^(n-1+N)が答えになる。
最終更新：2013年10月16日 20:49