Passed System Test
クッキーがの入った袋がいくつか並んでいる。
一つを取って、残った袋に入っているクッキーの数が偶数になるような取り方は何通りあるか。
解答
完全にやるだけ。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #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)なのでもう少し余裕がある。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | #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ビット目にビットがセットされていれば、そのターンそこに居るとゲームオーバーになるとして枝刈りを行っている。
ちなみに、像は１ターンにつき、自分の存在するマスと、自分が落下する対象のマスとの合計２マスを制限している。
提出コード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #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に復帰しましたが、まだまだです。
次は青コーダーですね。