日々精進

aikoと旅行とプログラミング

【AOJ 1167】Pollock's conjecture

AOJ プログラミング 競プロ

問題

Pollock's conjecture | Aizu Online Judge

方針

  • 動的計画法を使う.
  • { dp[n]:=} nを表現するのに必要な正四面体の数の最小値 としたとき, {dp[n]}は {dp[n] = min(dp[n-1], dp[n-4], dp[n-1-], \cdots , dp[n-n以下最大の正四面体数]) + 1}として求めることができる.
  • 1から順番にもとめておき, 入力したnを添え字にしてテーブルを出力する.

コード

#include<iostream>
#include<vector>
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define INF 1e9
#define pb push_back
 
using namespace std;
 
typedef long long ll;
 
#define MAX 1000001
 
signed main(){
  int n;
  int ans_odd[MAX], ans[MAX];
  vector<int> v1, v2;
 
  rep(i, 301){
    int hoge = i * (i+1) * (i+2) / 6;
    v1.pb(hoge);
    if(hoge%2 == 1) v2.pb(hoge);
  }
 
  rep(i, 1000001){
    ans[i] = ans_odd[i] = INF;
  }
   
  ans[0] = ans_odd[0] = 0;
   
  REP(i, 1, MAX){
    REP(j, 1, v1.size()){
      if(v1[j] > i) break;      
      ans[i] = min(ans[i], ans[i - v1[j]]+1);
    }
  }
 
  REP(i, 1, MAX){
    ans_odd[i] = i;
    REP(j, 1, v2.size()){
      if(v2[j] > i) break;
      ans_odd[i] = min(ans_odd[i], ans_odd[i - v2[j]]+1);
    }
  }
  
  while(cin >> n, n){
    cout << ans[n] << " " << ans_odd[n] << endl;    
  }
}

頭悪すぎて書くのにすごい時間がかかった…

【AOJ 1346】Miscalculation

AOJ プログラミング 競プロ

問題

Miscalculation | Aizu Online Judge

方針

  • ルール1は通常の優先順位（乗算→加算）で演算する.
  • ルール2は左から順番に計算する.
  • ルール1とルール2の結果が等しく, 入力した数字とも等しければU
  • ルール1が入力した数字と等しければM, ルール2と等しければL, それ以外はIを出力する.

コード

#include<cctype>
#include<iostream>

using namespace std;

typedef string::const_iterator State;

int number(State &begin){
  int ret = *begin - '0';
  begin++;
  return ret;
}

int term(State &begin){
  int ret = number(begin);
  
  while(true){
    if(*begin == '*'){
      begin++;
      ret *= number(begin);
    }else{
      break;
    }
  }

  return ret;
}

int expression(State &begin){
  int ret = term(begin);

  while(true){
    if(*begin == '+'){
      begin++;
      ret += term(begin);
    }else{
      break;
    }
  }

  return ret;
}

int rule2(string s){
  State begin = s.begin();
  int ret = *begin - '0';
  begin++;
  
  while(begin != s.end()){
    if(*begin == '+'){
      begin++;
      ret += *begin - '0';
    }else{
      begin++;
      ret *= *begin - '0';      
    }
    begin++;
  }

  return ret;
}

signed main(){
  string s;
  int n;
  int ans1, ans2;

  cin >> s;
  cin >> n;
  
  State begin = s.begin();
  ans1 = expression(begin);
  ans2 = rule2(s);
  
  if(ans1 == ans2 && ans1 == n){
    cout << "U" << endl;
  }else if(ans1 == n){
    cout << "M" << endl;
  }else if(ans2 == n){
    cout << "L" << endl;
  }else{
    cout << "I" << endl;
  }
  
}

参考

構文解析の部分は以下の記事を参考にしました.
構文解析 Howto · GitHub
これでAOJ-ICPCの200が全部埋まりましたー, やったー！

【AOJ 2340】Carpenters' Language

AOJ プログラミング

問題

Carpenters' Language | Aizu Online Judge

方針

  • 文法を見てみると, 実は挿入位置は関係なくてかっこの個数だけで判定できることが分かる.
  • 左括弧, 右括弧それぞれの個数を保持しておき, 同じの時はYes, そうでないときはNoを出力する.

コード

#include<iostream>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;

typedef long long ll;

signed main(){
  int q;
  ll p, n;
  char c;
  ll open, close;
  open = close = 0;
  cin >> q;
  rep(i, q){
    cin >> p >> c >> n;
    
    if(c == '('){
      open += n;
    }else{
      close += n;
    }
    
    if(open == close) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

【AOJ 1249】Make a Sequence

AOJ プログラミング

問題

Make a Sequence | Aizu Online Judge

方針

  • 置くたびにm個以上つながっているかを調べる.
  • 縦横斜めの３方向を探索するので, dx, dy, dzという配列を用意しておき3重ループする.

コード

#include<bits/stdc++.h>
 
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define m0(x) memset(x, 0, sizeof(x))
#define EMPTY -1
 
using namespace std;
 
typedef pair<int, int> pii;
 
int dx[3] = {-1, 0, 1};
int dy[3] = {-1, 0, 1};
int dz[3] = {-1, 0, 1};
 
int n, m, p;
int peg[10][10][10];
pii coordinate[350];
 
int idx;
 
bool check(int x, int y, int z){
 
  rep(i, 3){
    rep(j, 3){
      rep(k, 3){
     
        if(dx[i] == 0 && dy[j] == 0 && dz[k] == 0) continue;
     
        int len = 1;
        int sgn = 1;    
        rep(l, 2){
        int nx = x; int ny = y; int nz = z;
          while(true){      
            nx += (sgn * dx[i]); ny += (sgn * dy[j]); nz += (sgn * dz[k]);         
            if(nx < 0 || n <= nx || ny < 0 || n <= ny || nz < 0 || n <= nz) break;  
            if(peg[x][y][z] == peg[nx][ny][nz]) len++;
            else break;   
          }
          if(len >= m) return true;
          sgn *= (-1);
        }
 
        if(len >= m) return true;    
      }
    }
  }
  return false;
}
 
int getTurn(){
  memset(peg, EMPTY, sizeof(peg));
   
  rep(i, p){
     
    int x = coordinate[i].first; int y = coordinate[i].second; 
    bool ret = false;
    bool flag = false;
    rep(z, n){
      if(peg[x][y][z] == EMPTY){
        peg[x][y][z] = i % 2;
        idx = i;
        ret = check(x, y, z); // 何個連続しているか調べる
        flag = true;
        break;
      }      
    }
    if(!flag) return 0;
    if(ret) return i+1;
  }
 
  return 0;
}
 
signed main(){
   
  while(cin >> n >> m >> p, n || m || p){
    rep(i, p){
      cin >> coordinate[i].first >> coordinate[i].second;     
      coordinate[i].first--;
      coordinate[i].second--;
    }
     
    int ret = getTurn();
    if(ret == 0) cout << "Draw" << endl;
    else if(ret % 2 != 0) cout << "Black " << ret << endl;
    else cout << "White " << ret << endl;        
  }
}

【AOJ 2165】 Strange String Manipulation

AOJ プログラミング

問題

Strange String Manipulation | Aizu Online Judge

方針

  • S,A,Cを総当りして, エントロピーが一番低くなる場合を探す.
  • 誤差を考えて, epsを足さないと死んでしまう.

コード

#include<bits/stdc++.h>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define eps 1e-9
#define INF 1e9
#define m0(x) memset(x, 0, sizeof(x))

using namespace std;

signed main(){
  int n;
  int I[300];
  int r[300];
  int o[300];
  int freq[300];

  while(cin >> n, n){
    REP(i,1,n+1){
      cin >> I[i];
    }

    double minH = INF;
    int minS, minA, minC, idx;
    
    rep(s, 16){
      rep(a, 16){
    rep(c, 16){

      r[0] = s;      
      m0(freq);
      REP(i, 1, n+1){
        r[i] = (a * r[i-1] + c) % 256;
        idx = (I[i] + r[i]) % 256;
        freq[idx]++;
      }
      
      double sum=0;
      rep(i, 256){
        if(freq[i] == 0) continue;  
        sum += ((-1) * (freq[i]/(double)n) * (log(freq[i]/(double)n)));
      }
      if(sum + eps < minH){
        minH = sum; minA = a; minS = s; minC = c;
      }   
    }
      }
    }
    cout << minS << " " << minA << " " << minC << endl;
  }
}

参考

d.hatena.ne.jp

今週中に200を終わらせよう.

【AOJ 1368】Quality of Check Digits

AOJ プログラミング

問題

Quality of Check Digits | Aizu Online Judge

方針

  • 4桁の数字(abcd)をループで作る.
  • eを求め, それをチェック関数に投げる.
  • abcdの各桁を0-9の数字で置き換え, 0になったら-1を返す.
  • また, 連続する2桁を交換し（ただし, それぞれが違う文字のときのみ）0になったら-1を返す
  • -1の数を数え, それが答えとなる.

コード

#include <iostream>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;

int table[10][10];

int check(int a, int b, int c, int d, int e){
  
  rep(i, 10){
    if(table[table[table[table[table[0][i]][b]][c]][d]][e] == 0 && i != a){
      return -1;
    }
  }

  rep(i, 10){
    if(table[table[table[table[table[0][a]][i]][c]][d]][e] == 0 && i != b){
      return -1;
    }
  }

  rep(i, 10){
    if(table[table[table[table[table[0][a]][b]][i]][d]][e] == 0 && i != c){
      return -1;
    }
  }

  rep(i, 10){
    if(table[table[table[table[table[0][a]][b]][c]][i]][e] == 0 && i != d){
      return -1;
    }
  }

  rep(i, 10){
    if(table[table[table[table[table[0][a]][b]][c]][d]][i] == 0 && i != e){
      return -1;
    }
  }
  
  if(table[table[table[table[table[0][b]][a]][c]][d]][e] == 0 && a != b) return -1;
  if(table[table[table[table[table[0][a]][c]][b]][d]][e] == 0 && b != c) return -1;
  if(table[table[table[table[table[0][a]][b]][d]][c]][e] == 0 && c != d) return -1;
  if(table[table[table[table[table[0][a]][b]][c]][e]][d] == 0 && d != e) return -1;
  
  return 1;
}

signed main(){
  
  // input
  rep(i, 10){
    rep(j, 10){
      cin >> table[i][j];
    }
  }
  
  // check
  int ans = 0;
  rep(i, 10){
    rep(j, 10){
      rep(k, 10){
    rep(l, 10){
      int e = table[table[table[table[0][i]][j]][k]][l];
      if(check(i, j, k, l, e) == -1) ans++;
    }
      }
    }
  }

  cout << ans << endl;
}

【AOJ 1367】Rearranging a Sequence

AOJ プログラミング

問題

Rearranging a Sequence | Aizu Online Judge

方針

  • 与えられたM個の値を逆順に出力する.
  • 出力したかどうかを管理しておき, １回も出力していない場合に限って出力を行う.

コード

#include<bits/stdc++.h>
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
 
using namespace std;
 
int change[200001];
bool flag[200001];
 
signed main(){
  int n, m;
  cin >> n >> m;
   
  rep(i, m){
    cin >> change[i];
  }
 
  fill(flag, flag+20000, false);
 
  reverse(change, change+m);
  rep(i, m){
    if(!flag[change[i]]){
      cout << change[i] << endl;
      flag[change[i]] = true;
    }
  }
   
  REP(i, 1, n+1){
    if(!flag[i]) cout << i << endl;
  }
 
}