CodeForces #94 Div2 Only

Problem A Cookies

Passed System Test

クッキーがの入った袋がいくつか並んでいる。

一つを取って、残った袋に入っているクッキーの数が偶数になるような取り方は何通りあるか。

解答

完全にやるだけ。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <deque>
#include <queue>
#include <functional>

using namespace std;

#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) ((c).begin(), (c).end())
#define ll long long
#define VI vector<int>

int main() {
 int n;
 int cookie[100];
 cin >> n;
 rep(i,n) cin>>cookie[i];
 int even = 0,odd = 0;
 rep(i,n) if(cookie[i]&1) odd++; else even++;
 if(odd&1){
  cout << odd << endl;
  return 0;
 }
 cout << even << endl;
 return 0;
}

Problem B Students and Shoelaces
Wrong Answer on pretest 8


n人の生徒がおり、m個の生徒の対が紐で結ばれている。
ちょうど一人のみと紐で結ばれているような生徒が居た場合、それらの生徒を排除する。
再び残った生徒を見て、１人のみと紐で結ばれている生徒を排除する。
この操作を繰り返し、何回排除が行われたかを数える。

解法
シミュレートすればよい。
生徒の数は高々１００人なので、O(n^3)のループまで間に合う。
このコードの場合0(2n^2)なのでもう少し余裕がある。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <deque>
#include <queue>
#include <functional>

using namespace std;

#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) ((c).begin(), (c).end())
#define ll long long
#define VI vector<int>

bool tied[100][100];
int num[100];
int n,m;
void check(){
 int count;
 rep(i,n){
  count = 0;
  rep(j,n) if(tied[i][j]){
   count++;
  }
  num[i] = count;
 }
}

int main(){
 int repri,ans = -1;
 memset(tied,false,sizeof(tied));
 int kid1,kid2;
 cin>>n>>m;
 rep(i,m){
  cin>>kid1>>kid2;
  tied[kid1-1][kid2-1] = true;
  tied[kid2-1][kid1-1] = true;
 }
 do{
  check();
  //rep(i,n) cout << num[i] << endl;
  ans++;
  repri = 0;
  rep(i,n) if(num[i] == 1){
   rep(j,n){
    tied[j][i] = false;
    tied[i][j] = false;
   }
   //cout << i << "th student kicked" << endl;
   repri++;
  }
 }while(repri > 0);
 //rep(i,n) cout << i << "th student tied" << num[i] << " student" << endl;
 cout << ans << endl;
 return 0;
}

Problem C Statues
Passed System Test
8*8マスのチェスボードの対角線にMariaとAnnnaの駒が配置されている。
Mariaは左下隅。Annnaは右上隅。
Mariaはターンごとに将棋の王の駒と同じ動き方が可能である。同じマスに留まることも可能。
マス目にはStatueが配置されている場合があり、MariaはStatueの存在するマスには移動出来ない。
また、１ターンごとにStatueは１マス落下し、潰されるとゲームオーバーになる。
Statueは一番最後のマスを超えると消え去る。
MariaがAnnnaのマスに到達することは可能か。

解法
8*8マスなので、Statueは最悪でも７ターン経過すれば害が無くなり、８ターン目で全て消え去る。
DPを行い、7ターン後に生き延びていれば勝利とした。
実装はStatues[8][8]として、各マス目に対応する二次元配列を作成。
該当するメモリのnビット目にビットがセットされていれば、そのターンそこに居るとゲームオーバーになるとして枝刈りを行っている。
ちなみに、像は１ターンにつき、自分の存在するマスと、自分が落下する対象のマスとの合計２マスを制限している。

提出コード

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <deque>
#include <queue>
#include <functional>

using namespace std;

#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) ((c).begin(), (c).end())
#define ll long long
#define VI vector<int>


int statue[8][8];

typedef struct pos{
 int x;
 int y;
 int turn;

 bool is_valid(int _x, int _y,int turn){
  if(x+_x < 0 || y+_y < 0) return false;
  if(x+_x > 7 || y + _y > 7) return false;
  if(statue[x+_x][y+_y] & 1<<turn) return false;
  return true;
 }

} pos;

int main(){
 string map[8];
 memset(statue,false,sizeof(statue));
 rep(i,8) cin >> map[i];
 rep(i,8) rep(j,8) if(map[i][j] == 'S'){
  for(int k = 0;i+k < 8;k++){
   statue[i+k][j] |= 1<<k;
   statue[i+k][j] |= 1<<(k+1);
  }
 }
 queue<pos> dp;
 pos init = {7,0,0};
 dp.push(init);
 while(!dp.empty()){
  pos tmp = dp.front(); dp.pop();

  tmp.turn++;
  if(tmp.turn == 8){
   cout << "WIN" << endl;
   return 0;
  }
  REP(i,-1,2) REP(j,-1,2){
   if(tmp.is_valid(i,j,tmp.turn)){
    pos next = {tmp.x+i, tmp.y+j, tmp.turn};
    dp.push(next);
   }
  }
 }
 cout << "LOSE" << endl;
 return 0;
}

レート　1329　→　1416 (+87)

レートは少し上がり、Specialistに復帰しましたが、まだまだです。
次は青コーダーですね。