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に復帰しましたが、まだまだです。
次は青コーダーですね。