2017-07-05

POJ1065

POJ DP 蟻本

POJ1065

http://poj.org/problem?id=1065

DP問題の練習です。ソートして順次大きい方からつなげていけば終わりです。

久しぶりだったのでc++のいろいろな書き方忘れちゃって時間かかりました。

あと、終わってから気づいたのですが、subsetはvectorである必要ないですね。

解答時間は1時間です。

以下コードです。

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

typedef pair<int,int> s;
vector<s> stick;
vector<s> subset;
int t, n;
int w,l;
bool flag = false;

void init(){
  vector<s> empty1;
  vector<s> empty2;
  swap(stick, empty1);
  swap(subset, empty2);
}

bool comp(const s &a, const s &b){
  return a.second > b.second;
}

int solve(){
  for(int i = 0; i < n; i++){
    flag = false;
    sort(subset.begin(), subset.end(), comp);
    for(int j = 0; j < subset.size(); j++){
      if(subset[j].second <= stick[i].second){
        subset[j].second = stick[i].second;
        flag = true;
        break;
      }
    }
    if(!flag){
      subset.push_back(stick[i]);
    }
  }
  return subset.size();
}

int main(){
  scanf("%d",&t);
  for(int i = 0; i < t; i++){
    scanf("%d", &n);
    for(int j = 0; j < n; j++){
      scanf("%d %d", &l, &w);
      stick.push_back(s(l,w));
    }
    sort(stick.begin(), stick.end());
    printf("%d\n", solve());
    init();
  }
  return 0;
}

2017-06-22

POJ1742

DP POJ 蟻本

POJ1742

1742 -- Coins

今回もDPの練習です。最初は入れ子ループを何重にも張り巡らしてしまい、タイムアウトしてしまいました。

あとコインが何枚残っているかをメモすれば効率化を計れるんですね。蟻本で読んだ覚えがあってもいざ自分で実装するとなると難しいです。

解答時間は1時間20分です。以下コードです

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

int n, m;
int a[100], c[100];
int dp[100001];
int sum = 0;

int solve(){
  sum = 0;
  memset(dp, -1, sizeof(dp));
  for(int i = 1; i <= m/a[0] && c[0] > 0; i++){
    dp[i*a[0]] = 0;
    c[0]--;
  }
  for(int i = 1; i < n; i++){
    dp[0] = c[i];
    for(int j = 1; j <= m; j++){
      if(dp[j] != -1){
        dp[j] = c[i];
      }else if(a[i] <= j && dp[j - a[i]] > 0){
        dp[j] = dp[j - a[i]] - 1;
      }
    }
  }
  for(int i = 1; i <= m; i++){
    if(dp[i] != -1){
      sum++;
    }
  }
  return sum;
}


int main(){
  while(1){
    scanf("%d %d", &n, &m);
    if(n == 0 && m == 0)
      break;
    for(int i = 0; i < n; i++){
      scanf("%d", &a[i]);
    }
    for(int i = 0; i < n; i++){
      scanf("%d", &c[i]);
    }
    printf("%d\n", solve());
  }
  return 0;
}

2017-06-21

POJ2385

POJ 蟻本 DP

POJ2385

2385 -- Apple Catching

DPの練習問題です最初問題を読み間違えて、Wを移動してからW分待つと再び移動できるようになると解釈して、一時間くらい悩みました。英語力の欠如です。

問題の正しい理解ができてからは比較的すぐに実装することができました。ただ、コードは汚いですが。。。

解答時間は1時間半

以下コードです

#include <stdio.h>
#include <algorithm>
using namespace std;

int t, w;
int apple[1000];
int dp[32][1000][2];

int solve(){
  dp[0][0][apple[0]]++;
  for(int i = 1; i < t; i++){
    dp[0][i][0] = dp[0][i-1][0];
    dp[0][i][1] = dp[0][i-1][1];
    dp[0][i][apple[i]]++;
  }
  for(int i = 1; i < w + 1; i++){
    dp[i][0][0] = dp[0][0][0];
    dp[i][0][1] = dp[0][0][1];
    for(int j = 1; j < t; j++){
      dp[i][j][0] = max(dp[i][j-1][0], dp[i-1][j-1][1]);
      dp[i][j][1] = max(dp[i][j-1][1], dp[i-1][j-1][0]);
      dp[i][j][apple[j]]++;
    }
  }
  return max(dp[w][t-1][0], dp[w][t-1][1]);
}

int main(){
  scanf("%d %d", &t, &w);
  for(int i = 0; i < t; i++){
    scanf("%d", &apple[i]);
    apple[i]--;
  }
  printf("%d\n", solve());
  return 0;
}

2017-06-21

POJ2393

POJ 蟻本貪欲法

POJ2393

2393 -- Yogurt factory

一週間ぶりくらいですね今回は貪欲法の練習として解きました

ヒントに32bitより大きい整数になるかもしれないぞって書いてあるのにそれに気づかず悩んでました。

考え方としては、その週で買ったコストと保存しておくコストの和と、出荷する週で買ったコストのどちらが小さいかを選択していきました。直感的な数学力のなさから最初は何個か保存しておいて足りない分を出荷する週で買う場合も存在するのかなって思ったので、微分して確かめたりしました。

あと、最初英語がよくわからなくて英語頑張らないとなあと思いました

解答時間は50分です。以下コードです

#include <stdio.h>

int n, s, store = 0;
int y[10000], c[10000];
long long cost = 0;

long long solve(){
  for(int i = 0; i < n; i++){
    cost += store * s;
    if(y[i] > store){
      cost += (y[i] - store) * c[i];
      store = 0;
    }else{
      store -= y[i];
    }
    for(int j = i+1; j < n; j++){
      if(c[j] - c[i] - s * (j - i) > 0){
        cost += y[j] * c[i];
        store += y[j];
      }else{
        break;
      }
    }
  }
  return cost;
}

int main(){
  scanf("%d %d", &n, &s);
  for(int i = 0; i < n; i++){
    scanf("%d %d", &c[i], &y[i]);
  }
  printf("%lld\n", solve());
  return 0;
}

2017-06-13

POJ3187

POJ 全列挙蟻本

POJ3187

3187 -- Backward Digit Sums

今回も全列挙の練習です。こちらの方は前回のようなめんどくさい入力もなく、ただ問題の通りに処理するだけで済みました。

前回覚えたnext_permutationくんにまた頑張ってもらった。 next_permutationくんって辞書順に並べてくれるんですね〜、便利です。

解答時間は20分です。

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, sum, k;
int m[10] = {1,2,3,4,5,6,7,8,9,10};
int tmp[10];

void solve(){
  do{
    k = n;
    for(int i = 0; i < n; i++)
      tmp[i] = m[i];
    while(k>0){
      for(int i = 0; i < k-1; i++){
        tmp[i] += tmp[i+1];
      }
      k--;
    }
    if(tmp[0] == sum)
      break;
  }while(next_permutation(m, m+n));
}

int main(){
  scanf("%d %d", &n, &sum);
  solve();
  for(int i = 0; i < n - 1; i++){
    printf("%d ", m[i]);
  }
  printf("%d\n",m[n-1]);
  return 0;
}

2017-06-13

POJ2718

蟻本 POJ 全列挙

POJ2718

2718 -- Smallest Difference

全列挙の練習です。この問題は各データセット内の入力の回数が与えられていないため、入力のところで無限に時間を食いました。結局、iostreamを使用して、空白を削除しました。

最初は入力されたデータセットをグループに分け、その中で並び替えをして最小差となるようにコードを書いてましたが、友達からnext_permutationの存在を聞いたので使ってみました。（蟻本にも書いてあったような。。。）

stringでデータを取得して、ヌル文字'\0'を区切りにすることで二つのグループを作成して最小の差を求めようとしました。

結果、時間制限オーバーでした。。。

次に各グループの桁数の差を0か1の時のみ処理するようにしました。が、これも時間制限オーバーでした。。。

結局、時間内に処理が終了せず、今回は諦めちゃいました。。。どなたか、改善点を教えていただけると嬉しいです。。。

以下、コードです。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <cstdlib>
#include <string.h>

int n;
int digits[10];
std::string p;
char perm[12];
int tmp;
int j = 0;
size_t c;
int l_int;
int r_int;
int min;
int answer[1000];

void init(){
  for(int i = 0; i < 10; i++){
    perm[i] = '\0';
  }
}

int solve(){
  min = 99999999;
  do{
    if(strlen(&perm[0]) == j / 2){
      l_int = atoi(&perm[0]);
      r_int = atoi(strchr(perm, '\0') + 1);
      if(min > abs(l_int - r_int))
        min = abs(l_int - r_int);
    }
  }while(std::next_permutation(perm, perm + j + 1));
  return min;
}

int main(){
  scanf("%d\n", &n);
  for(int i = 0; i < n; i++){
    init();
    j = 0;
    getline(std::cin, p);
    while((c = p.find_first_of(" ")) != std::string::npos){
      p.erase(c,1);
      j++;
    }
    j++;
    for(int k = 0; k < j; k++){
      perm[k] = p[k];
    }
    answer[i] = solve();
  }
  for(int i = 0; i < n; i++)
    printf("%d\n", answer[i]);
  return 0;
}

2017-06-08

AOJ0525

AOJ 深さ優先探索蟻本

AOJ0525

おせんべい | Aizu Online Judge

深さ優先探索お煎餅を行で裏返すか裏返さないか、$2^R$回探索するだけ。色々考えた結果、裏返さない場合と裏返す場合の煎餅の並びを先に計算しておいて、各行について裏返すか裏返さないかのフラグを入れていった。

深さ優先探索は最深部に辿りついてから処理すればいいのね。

ところで、複数データセットがある場合ってデータセットが入力されるごとに出力してもいいんですかね？

解答時間は50分でした。

以下コードです。

#include <stdio.h>
#include <algorithm>

int field[10][2][10000];
int h,w;
int col_sum;
int sum = 0;
int now_sum = 0;
int ans[5];
int n = 0;
int sel[10];


void all(int k){
  if(k != h){
    sel[k] = 0;
    all(k+1);
    sel[k] = 1;
    all(k+1);
  }
  now_sum = 0;
  for(int j = 0; j < w; j++){
    col_sum = 0;
    for(int i = 0; i < h; i++){
      col_sum += field[i][sel[i]][j];
    }
    now_sum += std::max(col_sum,h-col_sum);
  }
  sum = std::max(now_sum,sum);
}

int solve(){
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      field[i][1][j] = (field[i][0][j] + 1) % 2;
    }
  }
  sum = 0;
  all(0);
  return sum;
}

int main(){
  while(true){
    scanf("%d %d",&h, &w);
    if(h == 0 && w == 0)
      break;
    for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
        scanf("%d", &field[i][0][j]);
      }
    }
    ans[n++] = solve();
  }
  for(int i = 0; i < n; i++){
    printf("%d\n", ans[i]);
  }
  return 0;
}

ただの院生

ただの院生の日記的な

POJ1065

POJ1065

POJ1742

POJ1742

POJ2385

POJ2385

POJ2393

POJ2393

POJ3187

POJ3187

POJ2718

POJ2718

AOJ0525

AOJ0525