蟻本の動的計画法の練習問題として解いた。

考えてもわからなかったので、以下のサイトを参考にさせてもらった。最後の手段にしようと思う。

hfuji.hatenablog.jp

「漸化式を作る」という作業がまだ馴染んでない。Sample Inputだったり自分で具体例を確かめてみたり、まずは例を探って、規則性を見つけそれを式に落とし込む、という作業ができるようにしたい。

あと三項演算子の書き方を忘れていた。条件分岐が簡単に書けるので覚えておきたい。

三項演算子 (条件) ? (条件が真のとき) : (条件が偽のとき);

#include <cstdio>
#include <vector>

using namespace std;

const int M=1000000000;

int main(){
  int N;

  scanf("%d",&N);

  vector<long long int> dp(N+1);
  dp[1]=1;

  for(int i=2;i<=N;i++){
    dp[i]=(((i%2)==0) ? dp[i-1]+dp[i/2] : dp[i-1])%M;
  }

  printf("%lld\n",dp[N]);

  return 0;
}

2016-11-03

POJ_3176: Cow Bowling

3176 -- Cow Bowling

蟻本の動的計画法の練習問題として解いた。

挙げられる課題として、

・サンプルの読み違え　⇒読んだ

これに尽きる。簡単な問題なので瞬殺したい。

あとPOJで”#include <bits/stdc++.h>”は使えないみたい。ヘッダーもちゃんと意識しなきゃいけないな。

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[350][350],N,ma;

int main(){
  scanf("%d",&N);

  for(int i=0;i<N;i++)
    for(int j=0;j<i+1;j++) scanf("%d",&dp[i][j]);

    for(int i=1;i<N;i++){
      for(int j=0;j<i+1;j++){
        if(j==0) dp[i][j]+=dp[i-1][j];
        else if(j==i) dp[i][j]+=dp[i-1][j-1];
        else dp[i][j]+=max(dp[i-1][j-1],dp[i-1][j]);
      }
    }

    for(int i=0;i<N;i++) ma=max(ma,dp[N-1][i]);

    printf("%d\n",ma);

    return 0;

}

2016-09-22

AOJ_0558: Cheese

Cheese | Aizu Online Judge

蟻本の幅優先探索の練習問題として解いた。

蟻本のbfsのサンプルコードを見ながらのコーディング。

書き上げるのに一時間、デバッグに三十分といったところである。まだまだ遅い。

今回手間取った要因は、
・幅優先探索の書き方が身についていなかった
（⇒蟻本で勉強）
・bfs関数の全体構造を考える前にコーディングを始めてしまった
（⇒次から考える）
・if文での条件の設定ミスによるバグ
（⇒printfでテストしてデバッグ）
・チーズの硬さでループするときに、キューが空の状態で無かったことによるバグ
（⇒デバッグ）
などが挙げられる。

キューを空にする書き方はこのサイトに学んだ。感謝。

ryo021021.hatenablog.com

とりあえず以下のように対処。 while (!m_Queue.empty()) m_Queue.pop();
std::queueの全要素削除 - 涼の成長記録

昨日よりは早く解けたので進歩としたい。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> P;
const int INF=100000000;

int ans=0,H,W,N,sx,sy,ssx,ssy;
char cheese[]={'0','1','2','3','4','5','6','7','8','9'},town[1000][1000];
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int d[1000][1000];

void bfs(){
  queue<P> que;
  sx=ssx; sy=ssy;
  for(int c=1;c<=N;c++){
    //硬さ1のcheeseから順に探索
    for(int i=0;i<H;i++)
      for(int j=0;j<W;j++) d[i][j]=INF;

    que.push(P(sx,sy));
    d[sx][sy]=0;

    while(que.size()){
      P p=que.front(); que.pop();
      if(town[p.first][p.second]==cheese[c]) {
        sx=p.first; sy=p.second;
        ans+=d[p.first][p.second];
        break;
      }
      for(int i=0;i<4;i++){
        int nx=p.first+dx[i],ny=p.second+dy[i];
        if(0<=nx && nx<H && 0<=ny && ny<W && town[nx][ny]!='X' && d[nx][ny]==INF){
          que.push(P(nx,ny));
          d[nx][ny]=d[p.first][p.second]+1;
        }
      }
    }
    while(!que.empty()) que.pop();

  }

  return ;
}

int main(){
  scanf("%d %d %d",&H,&W,&N);
  for(int i=0;i<H;i++) scanf("%s",&town[i]);

  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(town[i][j]=='S'){
        ssx=i; ssy=j;
        goto OUT;
      }
    }
  }
  OUT:

  bfs();

  printf("%d\n",ans);

  return 0;
}

2016-09-21

AOJ_0118: Property Distribution

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0118

蟻本の深さ優先探索の練習問題として取り組んだ。

今日は解くのに二時間かかった。

時間がかかった要因として、

・scanfでmapの読み込みがうまくいかなかった

　⇒cinでstring的に読み込むことで改善

・cnt変数をグローバルにしてしまったせいで初期化ミス

　⇒毎回初期化しなおした

・問題の読み込みが浅かった

　⇒読んだ（それはそう）

などが挙げられる。

AOJ上に上がっていたほかの人のコードを読んで気づきを得られた。

本番ではこんなことできないので自分の中に蓄積しなければならない。

#include <bits/stdc++.h>

using namespace std;

int H,M,cnt=0;
char farm[100][100];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};


void dfs(int x, int y, char z){
 farm[x][y]='.';
 for(int i=0;i<4;i++){
 if(x+dx[i]>=0 && x+dx[i]<H && y+dy[i]>=0 && y+dy[i]<M && farm[x+dx[i]][y+dy[i]]==z) dfs(x+dx[i],y+dy[i],z);
 }
 return ;
}

int main(){
 while(1){
 scanf("%d %d",&H,&M);
 if(H==0 && M==0) break;

for(int i=0;i<H;i++){
 cin >> farm[i];
 }

 
 cnt=0;

for(int i=0;i<H;i++){
 for(int j=0;j<M;j++){
 if(farm[i][j]!='.'){
 cnt++; dfs(i,j,farm[i][j]);
 }
 }
 }


 printf("%d\n",cnt);
}
 return 0;
}

競プロ今日の備忘録

問題を解いた上での気づき、反省を

POJ_2229: Sumsets

POJ_3176: Cow Bowling

AOJ_0558: Cheese

AOJ_0118: Property Distribution