2017-05-11

【AOJ ALDS1_13】A: Heuristic Search - 8 Queens Problem

問題

方針

バックトラック法を用いて探索を行おう.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

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

using namespace std;

bool isLocated[N][N];
int row[N];     // 行方向の襲撃
int col[N];     // 列方向の襲撃
int dl[2*N-1];  // 左下への襲撃
int dr[2*N-1];  // 右下への襲撃

void print(){
  rep(i, N){
    rep(j, N){
      if(isLocated[i][j] && row[i] != j) return;
    }
  }

  rep(i, N){
    rep(j, N){
      cout << (row[i] == j?"Q":".");
    }
    cout << "\n";
  }
}

void solve(int i){

  // すべての行置き終わった
  if(i == N){
    print();
    return;
  }

  // すべての列試す
  rep(j, N){
    // すでに襲撃されている場合
    if(col[j] == 1 || dl[j + i] == 1 || dr[i - j + N - 1] == 1){
      continue;
    }
    
    // i行目のj列にコマを置く(i列目はj列目のコマに襲撃されている)
    row[i] = j;
    // j行目, 左下方向, 右下方向にフラグを立てる.
    col[j] = dl[j+i] = dr[i-j+N-1] = 1;
    // i+1行目を探索
    solve(i+1);
    // フラグを解除する
    col[j] = dl[j+i] = dr[i-j+N-1] = -1;
  }
  
}

void init(){
  rep(i, N){
    row[i] = col[i] = -1;    
  }

  rep(i, 2*N-1){
    dl[i] = dr[i] = -1;
  }

  rep(i, N){
    rep(j, N){
      isLocated[i][j] = false;
    }
  }
}

signed main(){
  int n;
  int r, c;

  init();
  cin >> n;
  rep(i, n){
    cin >> r >> c;
    isLocated[r][c] = true;
  }
  solve(0);  
}

なんかバグらせまくって辛かった.

2017-05-10

【AOJ ALDS1_7】D: Tree - Reconstruction of a Tree

プログラミング AOJ

問題

木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

inorderを先頭から見ていったとき, その値をcとする.
そのcの位置をpreorderの中から探し, その値をmとする.
prem[m]より左側の値はcを根とする木の左部分木, 右側は右部分木となる.
それを再帰的に定義していく.

例

n = 5
pre = {1, 2, 3, 4, 5}
in = {3, 2, 4, 1, 5}
最初の根は1(pre[0])となり, 左部分木は[3, 2, 4], 右部分木は[5]となる.
左部分木の[3, 2, 4]のうち根は2(pre[1])となり, 左部分木は[3], 右部分木は[4]である.
左部分木が終わったので根が1の木の右部分木となるが, 要素数が1なのでそのまま終了となり木が完成する.

コード

#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;
 
vector<int> pre, in, ans;
int n;
int pos;
 
 
void solve(int l, int r){
  if(l - r >= 0) return;
  int root = pre[pos];
  pos++;
  int d = distance(in.begin(), find(in.begin(), in.end(), root));
  solve(l, d);
  solve(d+1, r);
  ans.pb(root);
}
 
signed main(){
 
  cin >> n;
   
  int m;
  rep(i,n){
    cin >> m;
    pre.pb(m);
  }
  rep(i,n){
    cin >> m;
    in.pb(m);    
  }
 
  solve(0, pre.size());
 
  cout << ans[0];
  REP(i,1, n){
    cout << " " << ans[i];
  }
  cout << "\n";
   
}

全く問題とは関係ないことだが, 初めてdistanceとfindを使った. distanceに至っては存在すら知らなかった. 猛省.

2017-05-10

【AOJ ALDS1_7】C: Tree - Tree Walk

AOJ プログラミング

問題

Tree Walk | Aizu Online Judge

方針

二分木を実装する.
行きかけ順(Preorder Tree Walk), 通りかけ順(Inorder Tree Walk), 帰りがけ順(Postorder Tree Walk)を実装する.
行きかけ順は, 根（接点）→左部分木→右部分木の順で出力を行う.
通りかけ順は左部分木→根（節点）→右部分木の順で出力を行う.
帰りがけ順は, 左部分木→右部分木→根（節点）の順で出力を行う.

コード

#include<iostream>
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define NIL -1
#define MAX 30
 
using namespace std;
 
struct Node{
  int parent, left, right;
};
 
Node node[MAX];
 
void preorder(int u){
  if(u == NIL) return;
 
  cout << " " << u;
  preorder(node[u].left);
  preorder(node[u].right);  
}
 
void inorder(int u){
  if(u == NIL) return;
  inorder(node[u].left);
  cout << " " << u;
  inorder(node[u].right);
}
 
void postorder(int u){
  if(u == NIL) return;
  postorder(node[u].left);
  postorder(node[u].right);
  cout << " " << u;
}
 
void init(){
  rep(i, MAX){
    node[i].left = node[i].right = node[i].parent = NIL;
  }
}
 
signed main(){
  int n;
  int id, l, r;
  cin >> n;
  init();
  rep(i, n){
    cin >> id >> l >> r;
    node[id].left = l;
    node[id].right = r;
     
    if(l != NIL) node[l].parent = id;
    if(r != NIL) node[r].parent = id;
  }
   
  int root = 0;
  rep(i, n){
    if(node[i].parent == NIL){
      root = i; 
      break;
    }
  }
  cout << "Preorder" << endl;
  preorder(root);
  cout << "\n";
  cout << "Inorder" << endl;
  inorder(root);
  cout << "\n";
  cout << "Postorder" << endl;
  postorder(root);
  cout << "\n";
 
}
``

2017-05-09

【AOJ ALDS1_7】A: Tree - Rooted Trees

AOJ プログラミング

問題

Rooted Trees | Aizu Online Judge

方針

根付き木を実装する.
Nodeという構造体を定義しておき, ノード番号(id), 親ノード(parent), 子ノード(child), 深さ(depth)というメンバを定義する.
入力にそって親子関係を構築していく.
すべて終わったあと, rootノード(parentがNIL)を探す.
そのノードをキューに挿入し, 子ノードとその時の深さをqueueにいれ空になるまで繰り返す.

コード

#include <iostream>
#include <queue>
#include <vector>
#include <utility>

#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
#define NIL -1
#define MAX 100001

using namespace std;

struct Node{
  int id;
  int parent;
  vector<int> child;
  int depth;
  
  void addChild(int c){
    child.pb(c);
  }
    
 void print(){
    cout << "node " << id << ": ";
    cout << "parent = " << parent << ", ";
    cout << "depth = " << depth << ", ";
    cout << (parent == -1?"root":child.size()==0?"leaf":"internal node") << ", ";
    cout << "[";
    if(child.size() != 0){
      rep(i, child.size()-1){
    cout << child[i] << ", ";
      }
      cout << child[child.size()-1];
    }
      cout << "]" << endl;
 }
};

Node node[MAX];

void init(int n){
  rep(i, n){
    node[i].depth = NIL;
    node[i].parent = NIL;
    node[i].child.clear();    
  }
}

signed main(){
  int n;
  int id, k, c, root;
  cin >> n;
  init(n);
  
  root = NIL;

  rep(i, n){
    cin >> id >> k;
    node[id].id = id;
    rep(j, k){
      cin >> c;
      node[id].addChild(c);
      node[c].parent = id;
      node[c].depth = node[id].depth + 1;
    }
  }

  rep(i, n){
    if(node[i].parent == NIL){
      root = i;
      break;
    }
  }
  
  queue<pair<Node, int> > q;
  q.push(make_pair(node[root], -1));
  while(!(q.empty())){
    pair<Node, int> p = q.front(); q.pop();
    node[p.first.id].depth = p.second + 1;
    rep(i, p.first.child.size()){
      q.push(make_pair(node[p.first.child[i]], p.second + 1));
    }
  }
  
  rep(i, n){
    node[i].print();
  }
}

2017-05-08

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

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

2017-05-07

【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が全部埋まりましたー, やったー！

2017-05-06

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

日々精進

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

【AOJ ALDS1_13】A: Heuristic Search - 8 Queens Problem

問題

方針

コード

【AOJ ALDS1_7】D: Tree - Reconstruction of a Tree

問題

方針

例

コード

【AOJ ALDS1_7】C: Tree - Tree Walk

問題

方針

コード

【AOJ ALDS1_7】A: Tree - Rooted Trees

問題

方針

コード

【AOJ 1167】Pollock's conjecture

問題

方針

コード

【AOJ 1346】Miscalculation

問題

方針

コード

参考

【AOJ 2340】Carpenters' Language

問題

方針

コード