Codeforces #94 Div.2
結果
ooo-- 2302pts 269th(Div.2)
1622->1583(-39)
A
accumulateしてその偶奇で場合分けしてカウントするだけ
B
問題文が読みにくい。
1人と結んでる奴を排除していき、何stepで終わるか。
隣接行列と結ばれている回数の配列を作って、
結ばれている回数が1なら排除して、その際に隣接行列を見てつながっている人の回数を減らせば良い。
はじめsampleがまったく意味不明だった。
C
左下から右上まで向かう。x,yともに±1の9マスに移動できる(stayもokということ)。
初め右上から左下かと思って、1WA
その後も一定のパターンが出現したら無理なのかとか考えたけどダメっぽい。
BFSっぽいけど9方向に移動できるので8^nだと何手までいけるか怪しいのでパス。
結局DPで、
dp[sec][x][y] := sec秒後に(x,y)にいる動き方の数
として
dp[i+1][p][q] = sum(dp[i][p-1からp+1][q-1からq+1])
とした。ただし、i秒目に石像がいる || i+1秒目に石像がいる ところは0にする。
そのために石像の位置を保持しておいた。
iの上限はすべてのstatueは8秒で下に落ちるので、8+8+8=24秒ぐらい取れば充分だろうと思ったので
一応大事を取って50にしてみた。
計算量はo(|S|*sec*x*y*dir) -> maxで62*50*8*8*9 なので間に合う。
ここから凡ミスで3WA。もったいない。
D
見た、わからん
E
みてない
以下Cのソース
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> using namespace std; #define dump(x) cerr << #x << " = " << (x) << endl; #define PB push_back #define MP make_pair #define ll long long #define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value)) template <typename T> void FILL_(void * ptr, size_t size, T value){ std::fill((T*)ptr, (T*)ptr+size, value); } inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;} template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();} int dx[9] = {1,0,-1,1,0,-1,1,0,-1}; int dy[9] = {1,1,1,0,0,0,-1,-1,-1}; ll dp[50][8][8]; int main(){ string board[8]; //FILL(dp,0); dp[0][7][0] = 1; vector<pair<int,int> > statues; for(int i=0;i<8;i++){ cin >> board[i]; } for(int i=0;i<8;i++){ for(int j=0;j<8;j++){ if(board[i][j] == 'S'){ statues.PB(MP(i,j)); } } } for(int i=0;i<49;i++){ for(int p=0;p<8;p++){ for(int q=0;q<8;q++){ for(int d=0;d<9;d++){ bool isok = true; if(0 <= p+dx[d] && p+dx[d] < 8 && 0 <= q+dy[d] && q+dy[d] < 8){ for(int s=0;s<statues.size();s++){ if((p == statues[s].first+i && q == statues[s].second) || (p == statues[s].first+i+1 && q == statues[s].second)){ isok = false; } } }else{ isok = false; } if(isok){ dp[i+1][p][q] += dp[i][p+dx[d]][q+dy[d]]; } } } } if(dp[i+1][0][7] > 0){ cout << "WIN" << endl; return 0; } } cout << "LOSE" << endl; }