yukicoder : No.367 ナイトの転身
問題URL：http://yukicoder.me/problems/no/367
問題レベル：★★★
問題
H行W列のチェス盤上で、ミニビショップとナイトを移動させる。
ミニビショップは斜めに移動できる。
ナイトからスタートでRの場所にくるとナイトはミニビショップになり、ミニビショップはナイトになる。
スタート地点のマスからゴール地点のマスまでの最短手数を出力する。
ゴールできない場合は-１を出力する。
解法
BFSで解ける。
ただし、駒が２種類あるので３次元配列を使ってナイト用、ミニビショップ用の盤の配列を用意する必要がある。
#include <vector> #include <list> #include <map> #include <set> #include <deque> #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> #include <queue> using namespace std; using ull = unsigned long long; using ll = long long; using lli = long long int; using ld = long double; using pa = pair<int,int>; using ppa = pair<pa,int>; #define SORT(v, n) sort(v, v+n); #define ALL(v) v.begin(),v.end() #define VSORT(v) sort(ALL(v)) #define GRESORT(v) sort(ALL(v),greater<ll>()) #define REVERSE(v) reverse(ALL(v)) #define overlap(v) v.erase(unique(ALL(v)),v.end()) #define debug(x) cout << #x << ": " << x << endl #define FOR(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,n) FOR(i,0,n) #define RFOR(i,a,b) for(int i = (b-1); i >= a; i--) #define rrep(i,n) RFOR(i,0,n) #define INF 999999999 #define mins(a,b) a = min(a,b) #define maxs(a,b) a = max(a,b) //4近傍 //int dy[]={0, 1, 0, -1}; //int dx[]={1, 0, -1, 0}; //8近傍 //int dy[]={0,0,1,-1,1,1,-1,-1}; //int dx[]={1,-1,0,0,1,-1,1,-1}; //knight int kdy[] = {-2,-2,-1,-1,1,1,2,2}; int kdx[] = {-1,1,-2,2,-2,2,-1,1}; //bishop int bdy[] = {1,1,-1,-1}; int bdx[] = {1,-1,1,-1}; ll mod = 1000000007; bool check(int x, int y, int h, int w){ return (x < 0 || y < 0 || y >= h || x >= w); } void solve() { int h,w; cin >> h >> w; char c[510][510]; int sx,sy,gx,gy; int d[510][510][2] = {}; rep(i,h){ rep(j,w){ cin >> c[i][j]; if(c[i][j] == 'S'){ sy = i; sx = j; } if(c[i][j] == 'G'){ gy = i; gx = j; } d[i][j][0] = INF; d[i][j][1] = INF; } } d[sy][sx][0] = 0; queue<ppa> q; q.push(ppa(pa(sx,sy),0)); while(!q.empty()) { ppa p = q.front(); q.pop(); pa pp = p.first; int x = pp.first, y = pp.second, r = p.second; if (gx == x && gy == y) break; int val = r == 0 ? 8 : 4; auto dy = r == 0 ? kdy : bdy; auto dx = r == 0 ? kdx : bdx; rep(i, val) { int xx = x + dx[i]; int yy = y + dy[i]; if (check(xx, yy, h, w)) continue; int nr = r; if(c[yy][xx] == 'R') nr ^= 1; if (d[yy][xx][nr] == INF) { d[yy][xx][nr] = d[y][x][r] + 1; q.push(ppa(pa(xx, yy), nr)); } } } cout << (d[gy][gx][0] != INF || d[gy][gx][1] != INF ? min(d[gy][gx][0],d[gy][gx][1]) : -1) << endl; } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); solve(); return 0; }
謎
以下のソースコード書いたが、なぜかWAを食らった。
理由がわからないので誰か教えてください。
Rのマスに到達すると
if(c[yy][xx] == 'R') r = (r+1) % 2;
として駒を切り替えていたが、なぜかうまく動作しなかった。
#include <vector> #include <list> #include <map> #include <set> #include <deque> #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> #include <queue> using namespace std; using ull = unsigned long long; using ll = long long; using lli = long long int; using ld = long double; using pa = pair<int,int>; using ppa = pair<pa,int>; #define SORT(v, n) sort(v, v+n); #define ALL(v) v.begin(),v.end() #define VSORT(v) sort(ALL(v)) #define GRESORT(v) sort(ALL(v),greater<ll>()) #define REVERSE(v) reverse(ALL(v)) #define overlap(v) v.erase(unique(ALL(v)),v.end()) #define debug(x) cout << #x << ": " << x << endl #define FOR(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,n) FOR(i,0,n) #define RFOR(i,a,b) for(int i = (b-1); i >= a; i--) #define rrep(i,n) RFOR(i,0,n) #define INF 999999999 #define mins(a,b) a = min(a,b) #define maxs(a,b) a = max(a,b) //4近傍 //int dy[]={0, 1, 0, -1}; //int dx[]={1, 0, -1, 0}; //8近傍 //int dy[]={0,0,1,-1,1,1,-1,-1}; //int dx[]={1,-1,0,0,1,-1,1,-1}; //knight int kdy[] = {-2,-2,-1,-1,1,1,2,2}; int kdx[] = {-1,1,-2,2,-2,2,-1,1}; //bishop int bdy[] = {1,1,-1,-1}; int bdx[] = {1,-1,1,-1}; ll mod = 1000000007; bool check(int x, int y, int h, int w){ return (x < 0 || y < 0 || y >= h || x >= w); } void solve() { int h,w; cin >> h >> w; char c[510][510]; int sx,sy,gx,gy; int d[510][510][2] = {}; rep(i,h){ rep(j,w){ cin >> c[i][j]; if(c[i][j] == 'S'){ sy = i; sx = j; } if(c[i][j] == 'G'){ gy = i; gx = j; } d[i][j][0] = INF; d[i][j][1] = INF; } } d[sy][sx][0] = 0; queue<ppa> q; q.push(ppa(pa(sx,sy),0)); while(!q.empty()){ ppa p = q.front(); q.pop(); pa pp = p.first; int x = pp.first, y = pp.second, r = p.second; //debug(x); debug(y); debug(r); if(gx == x && gy == y) break; if(r == 0){ rep(i,8){ int xx = x + kdx[i]; int yy = y + kdy[i]; if(check(xx,yy,h,w)) continue; if(c[yy][xx] == 'R') r = (r+1) % 2; if(d[yy][xx][0] == INF){ d[yy][xx][r] = d[y][x][0] + 1; q.push(ppa(pa(xx,yy),r)); } } }else{ rep(i,4){ int xx = x + bdx[i]; int yy = y + bdy[i]; if(check(xx,yy,h,w)) continue; if(c[yy][xx] == 'R') r = (r+1) % 2; if(d[yy][xx][1] == INF){ d[yy][xx][r] = d[y][x][1] + 1; q.push(ppa(pa(xx,yy),r)); } } } } cout << (d[gy][gx][0] != INF || d[gy][gx][1] != INF ? min(d[gy][gx][0],d[gy][gx][1]) : -1) << endl; } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); solve(); return 0; }
謎解決
rをifで分岐した後にrの変数の値が0になったり1になったりして分岐した意味がなくなり配列にちゃんと格納されていなかっただけ。
まとめ
まだまだだね。
yukicoder : No.311 z in FizzBuzzString
問題URL：http://yukicoder.me/problems/848/
問題レベル：★
問題
1〜Nまでの数字について、
・3の倍数かつ5の倍数：FizzBuzz
・3の倍数：Fizz
・5の倍数：Buzz
・それ以外：その数字自体
と変換して、その中の「z」の合計を調べる。
解法
ループでFizzまたはBuzzになったときを数えて出力する方法だとTLEになるので、Nを3で割ったときの個数と5で割ったときの個数をそれぞれ2倍して足してやれば良い。
例えば、N=30のとき
3の倍数は、3,6,9,12,15,18,21,24,27,30
5の倍数は、5,10,15,20,25,30
となる。
したがって、Fizzと表示される個数は10個でBuzzと表示される個数は6個となる。
つまり、表示される「z」の合計は10×2+6×2=32である。
足してから2倍してもok。
#include <iostream> using namespace std; int main(){ long long int n; cin >> n; cout << (n/3*2)+(n/5*2) << endl; return 0; }
