AtCoder Beginner Contest #60

問題はこちら. 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

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

• 
• 
• 

という制約がついている. この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)になった. かなり低いけど地道に頑張っていこう.