日々精進

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

【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

【AOJ 2727】M and A

AOJ プログラミング

問題

M and A | Aizu Online Judge

方針

  • SとTの部分文字列を交互に繋げてSを作ることができるか調べる.
  • Sの部分文字列は自明にSに含まれているので, Tの部分文字列を考える.
  • Tの先頭から順に探索し, 部分文字列であるかを試す. （Sの偶数番目と奇数番目をとった場合の2通り）

コード

#include<iostream>

using namespace std;

string S, T, s, t;

bool check(){
  int i;
  int pos = 0;

  if(s == "") return true;
  
  for(i = 0 ; i < (int)T.size() ; i++){
    while(T[i]!=s[pos] && i < (int)T.size()) i++;
    if(i >= (int)T.size()) break;
    pos++;
    if(pos == (int)s.size()){
      return true;
    }
  }

  return false;
}

signed main(){
  bool flag = false;
  cin >> S >> T;
  
  s = "";
  for(int i = 0 ; i < (int)S.size() ; i+=2) s += S[i];
  flag |= check();

  s = "";
  for(int i = 1 ;  i < (int)S.size() ; i+=2) s += S[i];
  flag |= check();

  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;
}

【AOJ 1232】Calling Extraterrestrial Intelligence Again

AOJ プログラミング

問題

Calling Extraterrestrial Intelligence Again | Aizu Online Judge

方針

  • {pq \leq m}と {\frac{m}{q} \leq \frac{p}{q} \leq 1}を満たすp, qを求める. (p, qは素数)
  • エラトステネスの篩を使って素数を生成する.
  • それらを使ってpとqの組を試す.
  • qを求めるループの条件式は, {pq \leq m}という不等式から, {q \leq \frac{m}{p}}とした.

コード

#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;

#define MAX_M 100000

bool prime[MAX_M+1];

signed main(){
  int m, a, b;
  
  rep(i, MAX_M+2){
    prime[i] = true;
  }

  prime[0] = prime[1] = false;
  REP(i, 2, sqrt(MAX_M+2)){
    if(prime[i]){
      for(int j = i * 2 ; j <= MAX_M ; j+=i){
    prime[j] = false;
      }
    }
  }
  
  while(cin >> m >> a >> b, m || a || b){
    int ans_p, ans_q, ans_pq = -1;
    for(int p = 2 ; p <= m ; p++){
      if(!prime[p]) continue;
      for(int q = 2 ; q <= m/p ; q++){
    if(!prime[q]) continue;
    if(ans_pq < p * q && p * q <= m && (double)a/b <= (double)p/q && (double)p/q <= 1.0){
      ans_pq = p*q;
      ans_p = p;
      ans_q = q;
    }
      }
    }
    cout << ans_p << " " << ans_q << endl;
  }
}

【AOJ 1241】Lagrange's Four-Square Theorem

AOJ プログラミング

問題

Lagrange's Four-Square Theorem | Aizu Online Judge

方針

  • 全部探索する.

コード

#include <iostream>

using namespace std;

signed main(){
  int n;

  while(cin >> n, n){
    int cnt = 0;
    for(int i = 1 ; i * i <= n ; i++){
      if(i*i == n) cnt++;
      for(int j = i ; j * j <= n ; j++){
        if(i*i + j*j == n) cnt++;
        for(int k = j ; k * k <= n ; k++){
          if(i*i + j*j + k*k == n) cnt++;
          for(int l = k ; l * l <= n ; l++){
            if(i*i + j*j + k*k + l*l == n) cnt++;
          }
        }
      }      
    }

    cout << cnt << endl;
  }
   
}

【AOJ 2300】Calendar Colors

AOJ プログラミング

問題

Calender Colors | Aizu Online Judge

方針

  • N個のLABカラーが与えられる.
  • そこからM個取り出し, 要素それぞれの差の二乗の和を求める.
  • その和の最大値が答え.
  • {0 \leq M \leq N \leq 20}であることから全探索しても良さそう.
  • M個取り出すときにbitを使うと便利っぽい.

コード

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
#define rep(i,n) REP(i,0,n)
#define REP(i,a,n) for(int i = a ; i < (int)n ; i++)
 
struct LAB{
  double l, a, b;
  LAB(double ln, double an, double bn){
    l = ln; a = an; b = bn;
  }
};
 
int main(){
  int n, m;
  double l, a, b;
  vector<LAB> v;
  
  scanf("%d %d", &n, &m);
  rep(i, n){
    scanf("%lf %lf %lf", &l, &a, &b);
    v.push_back(LAB(l,a,b));
  }
   
  double ans = -1;
  rep(i, (1<<n)){
    vector<LAB> elem;
    rep(j, n){
      if(i & (1 << j)){
        elem.push_back(v[j]);
      }
    }
 
    if((int)elem.size() != m) continue; 
     
    double tmp = 0;
    rep(i, m-1){
      REP(j, i+1, m){
        tmp += (pow(elem[i].l-elem[j].l, 2) + pow(elem[i].a-elem[j].a, 2) + pow(elem[i].b-elem[j].b, 2));
      }
    }
    ans = max(ans, tmp);
  }

  printf("%.8f\n", ans);
}

参考

AOJ 2300 - Calendar Colors - プログラミングコンテストの記録