日々精進

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

【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;
  }
 
}

【AOJ 2619】Thread Tree

AOJ プログラミング

問題

Thread Tree | Aizu Online Judge

方針

  • 木を作って順に辿って出力する.
  • 英語つらいなって思ったけどそんなに難しくなかった.（これは方針ではない）

コード

#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 pb push_back
 
using namespace std;
 
struct TREE {
 
  int _d;
  string _name;
  vector<TREE*> _v;
 
  TREE(string name, int d){
    _name = name;
    _d = d;
  }
 
  void add(TREE* t){
    _v.pb(t);
  }
   
  void print(){
    rep(i,_d) cout << ".";
    cout << _name << endl;
 
    rep(i, _v.size()){
      _v[i]->print();
    }
  }
 
};
 
signed main(){
  int n;
  int k1, k;
  string m1, m;
  TREE* v[1001];
  TREE *t, *root;
   
  cin >> n;
  cin >> k1;
  cin >> m1;
   
  root = t = new TREE(m1, k1);  
  v[1] = t;
   
  REP(i, 2, n+1){
    cin >> k >> m;
    t = new TREE(m, v[k]->_d+1);
    v[k]->add(t);
    v[i] = t;
  }
 
  root->print();
}

木を作るのに苦労するなど. まだまだですね.

AtCoder Beginner Contest #60

プログラミング AtCoder

問題はこちら. abc060.contest.atcoder.jp

問題A：Shiritori

文字列A, B, Cが3つ与えられた時, それらがしりとりになっているか判定せよ.

#include <iostream>

using namespace std;

signed main(){
  string a, b, c;
  
  cin >> a >> b >> c;
  if(a[a.size()-1] == b[0] && b[b.size()-1] == c[0]) cout << "YES" << endl;
  else cout << "NO" << endl;
}

問題B：Choose Integers

正の整数A, B, Cが与えられる. 正の整数を幾つか選び, をれをBで割った時, 余りがCとなるように整数を選ぶ事ができるか出力せよ. ただし, 正の整数はAの倍数でなければならない.

#include<iostream>

using namespace std;

signed main(){
  int a, b, c;
  cin >> a >> b >> c;
  int tmp = a;
  int mod = 0;
  bool flag[101];
  
  fill(flag, flag+100, false);
  
  mod = tmp % b;
  do{
    flag[mod] = true;
    if(mod == c){
      cout << "YES" << endl;
      exit(0);
    }
    tmp += a;
    mod = tmp % b;
  }while(!flag[mod]);
  
  cout << "NO" << endl;
}

問題C：Sentou

スイッチを押すと, T秒お湯が出る. スイッチを押すタイミングが与えられるので, 合計何秒間お湯が出たかを出力せよ. お湯が出ている状態でスイッチを押すと, T秒延長されるのではなく押した瞬間からT秒間お湯が出力されるという点に注意.

#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 n, t;
int data[200001];

signed main(){
  cin >> n >> t;
  
  fill(data, data+200000, 0);
  rep(i, n){
    cin >> data[i];
  }
  
  int end = 0;
  int start = 0;
  int ans = 0;

  rep(i, n){
    if(data[i] < end){ 
      end = data[i] + t;
    }else{
      ans += (end - start);
      start = data[i];
      end = data[i]+t;
    }
  }

  ans += (end - start);
  
  cout << ans << endl;
}

問題D：Simple Knapsack

ナップサック問題. ただし,

  • {1 \leq w_i \leq 10^{9}}
  • {w_1 \leq w_i \leq w_1+3 (i = 1, 2, 3, \cdots N)}
  • {1 \leq v_i \leq 10^{7}}

という制約がついている. このwの制約を利用することで全探索をすることができる. 各重さごとにvectorにpushしておき, それらをどれだけ使うかを4重ループにして試す.

#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 ALL(v) v.begin(), v.end()
#define pb push_back
 
using namespace std;
 
typedef long long ll;
 
ll N, W;
 
signed main(){
  ll w1, v1, _w, _v;
  cin >> N >> W;
  
  cin >> w1 >> v1;
  
  vector<ll> v[4];
  
  v[0].pb(v1);
 
  REP(i, 1, N){
    cin >> _w >> _v;
    v[(_w - w1)].pb(_v);
  }
  
  rep(i, 4){
    sort(ALL(v[i]));
    reverse(ALL(v[i]));
  }
  
  ll ans = 0;
  rep(i, v[0].size()+1){
    rep(j, v[1].size()+1){
      rep(k, v[2].size()+1){
    rep(l, v[3].size()+1){
      _w = 0; _v = 0;
      rep(ii, i){
        _w += w1; _v += v[0][ii];
      }
      rep(ii, j){
        _w += (w1+1); _v += v[1][ii];
      }
      rep(ii, k){
        _w += (w1+2); _v += v[2][ii];
      }
      rep(ii, l){
        _w += (w1+3); _v += v[3][ii];
      }
      if(_w <= W){
        ans = max(ans, _v);
      }
    }
      }
    }
  }
  cout << ans << endl;
}

rateが868(highest)になった. かなり低いけど地道に頑張っていこう.

【AOJ 2565】Broken Audio Signal

AOJ プログラミング

問題

Broken Audio Signal | Aizu Online Judge

方針

  • 区間を狭めていって, その区間によって結果を出力する.
  • xが偶数番目のときに上界, 奇数番目のときに下界を決めることができる.
  • xが連続した時はnone, 上界がないなど様々な場合分けがあってとてもつらい.

コード

#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 MAX_V 1000000000

using namespace std;

typedef long long ll;

int n;
string data[10000];

ll toNum(string s){
  return (int)atoi(s.c_str());
}

string solve(){
  ll upper, lower;
  string prev;
  upper = MAX_V * 2; lower = -MAX_V * 2;
  prev = to_string(upper);

  rep(i, n){
    if(data[i] == "x"){
      if(prev == "x") return "none"; // xが連続
      if((i+1) % 2 == 1){ // odd
    upper = min(upper, toNum(prev));
    if(i < n-1) upper = min(upper, toNum(data[i+1]));
      }else{ // even
    lower = max(lower, toNum(prev));
    if(i < n-1) lower = max(lower, toNum(data[i+1]));
      }
    }else{ // 数字のときに正しいか判別
      if((i+1)%2 == 1 && prev != "x"){
    if((toNum(prev)) <= toNum(data[i])) return "none";
      }else if(prev != "x"){
    if((toNum(prev)) >= toNum(data[i])) return "none";
      }
    }
    
    prev = data[i];
    if(upper - lower < 2) return "none"; 
  }
  if(upper - lower > 2) return "ambiguous";
  return to_string((upper + lower) / 2);
}

signed main(){

  while(cin >> n, n){
    rep(i, n){
      cin >> data[i];
    }
    cout << solve() << endl;
  }
}

参考

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2013%2FPractice%2F模擬地区予選%2F講評&openfile=A.pdf:image=http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2013%2FPractice%2F模擬地区予選%2F講評&openfile=A.pdf