SRM 618 Div2 Easy Aを入力するには1タップ、Zは26タップ、文字列が与えられる。全て入力するには何回タップすればいいか 数える Med 文字列が与えられる。同じ文字が連続してなくて、部分列がXYXYとならない文字列は"Likes" 4つ以上ある文字が存在すればダ…

問題 Ghost Buster 解法 BFSで解ける。リンレンの双子の問題はバグ埋め込んでなかなかACでなかったけど、今回は一発AC。全探索の実装なれてきたのかな 心臓に悪いコード int dy[] = {0, -1,0,1,0}, dx[] = {0, 0,-1,0,1}; int gdy[] = {0, 0, 1, 0, 0, 0, 0,…

問題 Ninja Climbing 解法 BFSで通った。もしビルの屋上を超えてしまっても屋上につくことはできる 心臓に悪いコード cpp int n, b[2][128]; int rec1(int x, int y){ if(b[x][y+1] == 1) return rec1(x, y+1); return y; } int rec2(int x, int y){ if(b[x]…

問題 Stray Twins 解法 BFS。入力のところで処理の時とy、x座標を逆にあつかっててwa連発。 心臓に悪いコード int board[51][51], Y, X; int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0}; pii nextp(pii now, int i, int d){ pii next = now; next.Y += dy[i] * d…

問題 Dragon Fantasy 解法 全探索＋枝刈り。BFSでときました。枝刈りをするときはループに入らせる前に走査して枝刈りさせないと無駄な探索が入り込んだりすることを知った。 心臓に悪いコード int n; int hx, hy, dx, dy, cx[21], cy[21]; double dist(doub…

問題 Amazing Mazes 解法 寝落ちして、１時ぐらいに解いた。一発AC。 BFSで解けます。下か上に行く時はin[y*2±1][x]が1なら進めない。左右はin[y*2][x]が1なら進めないってやっていく。 コード int w, h, maze[128][128], dy[] = {0,-1,0,1}, dx[] = {-1,0,1…

問題 Twirling Robot 解法 BFSで解けます。priority_queue使ってコストの低いとこから見ていって、goalについたら答えです。 コード int w, h; int s[32][32], dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1}, c[4], used[32][32][4]; int main(){ while(scanf("%d%d…

問題 Eleven Puzzle。 解法 BFSだと間に合わない。地球は爆発しないよね。 id:nanikakaさんのはてなダイアリーで両側探索というものがあるのを知った、 実装はJavaだったので見ずに勘で実装してみた。 一発AC。 嬉しかったです。 コード vi p, next, now; ve…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2153)。 解法 BFSで解く。今まで通った場所を記憶するのにmapを使うとメモリが足りなくなる。 コード int W, H, used[52][52][52][52]; int dy[] = {0,-1,0,1}, dx[] = {-1,0,1,0}; char le…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1218) 図だけでもなんとか分かるよね。ゴールまで最短で何回動かせばいいか 解法 BFSで動かしていきます。押す方向と逆の方向に人が立てるか、現在いるところからそこにいくことができるか…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1214。 antが自分の巣に帰る最短距離を求める。四方向に一つ進むのに1timeかかる。初期の体力が6で1timeごとに1ずつ減っていく、食べ物のマスを通ると体力が6になる。 解法 食べ物は２回以上…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0156。 解法 天守閣からBFS、複数続いている堀をその度にカウントしてWAを出していた。 コード nt dx[] = {0,-1,0,1}, dy[] = {-1,0,1,0}; int main(){ int n, m, i, j, d, res; while(scanf…