No.240 ナイト散歩
方針
・問題文にある8座標にそれぞれ分岐していくような再帰関数を書く
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); static int gx = sc.nextInt(); static int gy = sc.nextInt(); public static void main(String[] args) { out.println(dfs(0,0,0)?"YES":"NO"); } static boolean dfs(int x, int y, int n) { if (n>3) return false; if (x==gx && y==gy) return true; return ( dfs(x-2,y-1,n+1) || dfs(x-2,y+1,n+1) || dfs(x-1,y-2,n+1) || dfs(x-1,y+2,n+1) || dfs(x+1,y-2,n+1) || dfs(x+1,y+2,n+1) || dfs(x+2,y-1,n+1) || dfs(x+2,y+1,n+1) ); } }
ごく普通の再帰関数（深さ優先探索）ですが、戻り値の部分が少し変わっています。
・return （条件式1 || 条件式2 || 条件式3……）
・return （関数1 || 関数2 || 関数3……）
と書いた場合、これはif文にある条件式の形になるので、
これらの条件式（あるいは関数の戻り値）のうち一つでもtrueならばtrueを戻すことになります。
今回の問題では、n>3になるか目標地点に到達するまで再帰関数を伸ばし続け、前者の終了条件ではfalse、後者ではtrueが返ります。すると、3番目のreturnの中身は最終的に
・return （false || false || false || true || false || false || false......）
となります。したがって、一度でも目標地点に到達していればtrue、一度も目標地点に到達できなかったならfalseが返ることになり、戻り値の書き方が少し特殊だったこの再帰関数も、正しく動作していることになります。
AtCoder Regular Contest 031 B - 埋め立て
方針
・地図は10*10なので全探索可能
・埋め立てたときに複数の島を連結させられる海マスとは、少なくとも上下左右に二つの隣接した島マスを持っている必要がある
・地図を二次元配列に読み込む（このとき、島の総マス数を記録しておく。areaとする）
・上の条件を満たす海マスそれぞれについて、埋め立てて、深さ優先なり幅優先探索をし、探索できた島のマス数がarea+1であればYes。area+1を満たせなければNo。
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); static char[][] map = new char[10][10]; static int area; public static void main(String[] args) { //マップを作成。それと同時に、陸マスも数える for (int i=0; i<10; i++) { map[i] = sc.next().toCharArray(); for (int j=0; j<10; j++) { if (map[i][j]=='o') area++; } } //変数とか int[] dx = {0,1,0,-1}; int[] dy = {-1,0,1,0}; boolean F = false; //メイン処理 loop : for (int i=0; i<10; i++) { for (int j=0; j<10; j++) { //すべての海マスで全探索してもよいのだが、ここでは計算量を減らすため、 //上下左右に合計で2個以上の陸マスと隣接している海マスを検出する int landNum = 0; if (map[i][j]=='x') { for (int k=0; k<4; k++) { int y = i + dy[k]; int x = j + dx[k]; if (y<0 || x<0 || y>9 || x>9) continue; if (map[y][x]=='o') landNum++; } //条件を満たす海マスであれば、再帰関数で陸地を探索 if (landNum >= 2) { boolean[][] memo = new boolean[10][10]; dfs(i,j,0,memo); int areaNum = 0; for (int k=0; k<10; k++) { for (int l=0; l<10; l++) { if (memo[k][l]) areaNum++; } } //埋め立てた海マスからすべての陸マスに行けるなら、trueにしてbreak if (areaNum == area+1) { F = true; break loop; } } } } } //出力 out.println(F?"YES":"NO"); } //陸地探索用の再帰関数。 static void dfs(int sy, int sx, int n, boolean[][] memo) { if (sy<0 || sx<0 || sy>9 || sx>9 || memo[sy][sx]) return; //海マスから探索を始めるので、何もしないと呼び出し1回目で再帰関数が終了してしまう。 //そのため以下の条件で、呼び出し1回目はたとえ海マスであっても処理を続行するようにした。 if (n!=0 && map[sy][sx]=='x') return; memo[sy][sx] = true; dfs(sy-1,sx,n+1,memo); dfs(sy,sx+1,n+1,memo); dfs(sy+1,sx,n+1,memo); dfs(sy,sx-1,n+1,memo); } }
提出してACがついてから気がついたのですが、このコードだと「陸地が1マスだけのとき」「陸地が最初から1つの島で、なおかつ直線状のとき」などが検出できません。島同士を繋ぐという問題ですし、陸地が必ず2つ以上の島に分かれていることを前提とするなら、このコードでも問題ないのかなとは思います。
もし上記の状態まで検出するなら、海マス検出の条件を削除し、素直に海マスを全探索すればよいと思います。
ダンジョンを自動生成するアルゴリズム
ローグライクゲームに出てくるようなダンジョンを自動で生成するアルゴリズムを作ってみました。
生成例
ソースコード
package Blog; import java.util.*; import static java.lang.System.*; public class Blog { //ダンジョンの大きさ static int h = 20; static int w = 40; //部屋の幅の最小値（実際はこの値から2を引いたもの） static int roomSize = 5; //その他、変数など static char[][] map = new char[h][w]; static int[] dx = {0,1,0,-1}; static int[] dy = {-1,0,1,0}; public static void main(String[] args) { //最初に、マップを壁で埋める for (int i=0; i<h; i++) { for (int j=0; j<w; j++) { map[i][j] = '#'; } } //マップを複数のエリアに分割する //具体的にどういう処理をしているかというと、 // //①エリアAを、BとCに2分割する（splitVorHが偶数なら縦分割） //②新しくできたBとCのうち、片方を二度と分割できないようにする（Bとする） //③エリアCを、DとEに2分割する…… // //というような具合。 //エリアBとCを次で両方とも分割する仕様だと、部屋数が増えすぎるのでこのようにした。 //分割方向については、縦分割と横分割を交互にやらないと密室が発生してしまうのでこのようにした。 Deque<Area> areas = new ArrayDeque<>(); areas.addLast(new Area(new Point(0,0),new Point(w-1,h-1),false)); Random rnd = new Random(); int splitVorH = rnd.nextInt(2); while (true) { Area temp = null; for (Area area : areas) { if (area.canSplitVorH('V') || area.canSplitVorH('H')) { if (!area.splitEnd) temp = area; } } if (temp == null) break; areas.remove(temp); return2Area ra; if (splitVorH%2 == 0) { if (temp.canSplitVorH('V') && !temp.splitEnd) { //エリアを縦に分割 ra = temp.splitArea('V'); areas.addLast(ra.a); areas.addLast(ra.b); } else { //縦と横交互にと書いたが、実際はこの部分で横分割の判定も行うようになっている。 if (temp.canSplitVorH('H') && !temp.splitEnd) { ra = temp.splitArea('H'); areas.addLast(ra.a); areas.addLast(ra.b); } } } else { if (temp.canSplitVorH('H') && !temp.splitEnd) { //エリアを横に分割 ra = temp.splitArea('H'); areas.add(ra.a); areas.add(ra.b); } else { //こちらは縦分割の判定（横分割できなかった場合はここを実行） if (temp.canSplitVorH('V') && !temp.splitEnd) { ra = temp.splitArea('V'); areas.add(ra.a); areas.add(ra.b); } } } splitVorH++; } //各エリアごとに部屋の大きさを決め、部屋中央の座標を特定してリストに格納 List<Point> roomCenter = new ArrayList<>(); for (Area area : areas) { int h = rnd.nextInt(area.Height-(roomSize-1)) + (roomSize-2); int w = rnd.nextInt(area.Width-(roomSize-1)) + (roomSize-2); int sx = rnd.nextInt(area.botR.x-area.topL.x-w) + (area.topL.x + 1); int sy = rnd.nextInt(area.botR.y-area.topL.y-h) + (area.topL.y + 1); for (int i=0; i<h; i++) { for (int j=0; j<w; j++) { map[i+sy][j+sx] = '.'; if (i==h/2 && j==w/2) { roomCenter.add(new Point(j+sx,i+sy)); } } } } //部屋中央から通路へ道を伸ばす（ランダム） for (int i=0; i<roomCenter.size(); i++) { //上下左右どれから伸ばすかは、Collection.shuffle()で実装 ArrayList<Integer> list = new ArrayList<Integer>() {{ add(0); add(1); add(2); add(3); }}; Collections.shuffle(list); loop : for (int k=0; k<4; k++) { int y = roomCenter.get(i).y; int x = roomCenter.get(i).x; while (true) { y += dy[list.get(k)]; x += dx[list.get(k)]; //通路に行き当たらず、配列外に出てしまった場合はまた違う方向に伸ばす if (y<0 || y>h-1 || x<0 || x>w-1) { break; } else { if (map[y][x] == 'x') { map[y][x] = 'e'; x = roomCenter.get(i).x; y = roomCenter.get(i).y; while (true) { y += dy[list.get(k)]; x += dx[list.get(k)]; if (map[y][x]=='e') { break loop; } map[y][x] = '.'; } } } } } } //配列の範囲外へと繋がっている通路を塗りつぶしていく //移動先の座標が分かれ道か、あるいはeになるまで、#で埋めていく for (int i=0; i<w; i++) { if (map[0][i]=='x') { rec(0,i); } if (map[h-1][i]=='x') { rec(h-1,i); } } for (int i=0; i<h; i++) { if (map[i][0]=='x') { rec(i,0); } if (map[i][w-1]=='x') { rec(i,w-1); } } //最後に残ったeとxを道に変換しつつ、出力して終了 out.println(); out.println(); for (int i=0; i<h; i++) { out.print(" "); for (int j=0; j<w; j++) { if (map[i][j] != '#') map[i][j] = '.'; out.print(map[i][j]); } out.println(); } } //eもしくは分かれ道に行き当たるまで通路を壁で埋める再帰関数 static void rec(int y, int x) { if (y<0 || x<0 || h<=y || w<=x) {return;} if (map[y][x]=='e' || map[y][x]=='#') {return;} int n = 0; for (int i=0; i<4; i++) { int ty = y + dy[i]; int tx = x + dx[i]; if (ty<0 || tx<0 || h<=ty || w<=tx) {continue;} if (map[ty][tx]=='x' || map[ty][tx]=='e' || map[ty][tx]=='.') n++; } if (n >= 2) return; map[y][x] = '#'; rec(y,x+1); rec(y,x-1); rec(y+1,x); rec(y-1,x); } } //Areaクラス。 //メンバは、左上の座標・右下の座標・横幅・縦幅。 //メソッドは、縦あるいは横で分割可能かを判定するcanSplitVorHと、 //自らを2分割してその結果得られる2つのエリアを他クラスに格納するsplitArea。 class Area { Point topL; Point botR; int Width; int Height; boolean splitEnd; public Area(Point tl, Point br, boolean a) { this.topL = tl; this.botR = br; this.Width = br.x - tl.x + 1; this.Height = br.y - tl.y + 1; this.splitEnd = a; } public boolean canSplitVorH(char VorH) { if (VorH=='V') {if (Width>=Blog.roomSize*2+1) return true;} else {if (Height>=Blog.roomSize*2+1) return true;} return false; } public return2Area splitArea(char VorH) { Random rnd = new Random(); Area a; Area b; int temp = rnd.nextInt(2); if (VorH == 'V') { int x = rnd.nextInt(Width-Blog.roomSize*2) + Blog.roomSize; for (int i=topL.y; i<=botR.y; i++) { Blog.map[i][topL.x+x] = 'x'; } a = new Area(topL,new Point(x-1+topL.x,botR.y),temp==0?true:false); b = new Area(new Point(x+1+topL.x,topL.y),botR,temp==0?false:true); } else { int y = rnd.nextInt(this.Height-Blog.roomSize*2) + Blog.roomSize; for (int i=topL.x; i<=botR.x; i++) { Blog.map[topL.y+y][i] = 'x'; } a = new Area(topL,new Point(botR.x,topL.y+y-1),temp==0?true:false); b = new Area(new Point(topL.x,topL.y+y+1),botR,temp==0?false:true); } return2Area ra = new return2Area(a,b); return ra; } } //エリアを分割すると戻り値が2つになるので、それを受け取るクラスを作った。 class return2Area { Area a; Area b; return2Area(Area a, Area b) { this.a = a; this.b = b; } } //座標クラス。 class Point { int x; int y; Point(int a, int b) { this.x = a; this.y = b; } }
このアルゴリズムで生成されるダンジョンの特徴
・すべての部屋が連結している（密室がない）
・すべての部屋が長方形（ランダムな形、あるいは円形にできないこともないがめんどくさい）
・必ず通路＋部屋という構造になる（大部屋一つだけ、部屋同士が通路を介さずに繋がっている、通路だけ、などは生成されない）
AtCoder Beginner Contest 092
A - Traveling Budget
ans = Math.min(a,b) + Math.min(c,d);
B - Chocolate
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); int day = sc.nextInt(); int x = sc.nextInt(); int total = 0; for (int i=0; i<n; i++) { int a = sc.nextInt(); if (day%a==0) { total += day/a; } else { total += day/a + 1; } } out.println(total+x); } }
AをそれぞれDで割っていって、割り切れるならtotalにA/Dを足し、割り切れないならtotalに(A/D)+1を足します。N個のAを処理し終わったあと、totalにXを足したものが答えです。
C - Traveling Plan
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); int[] ar = new int[n+2]; ar[0] = 0; ar[n+1] = 0; int total = 0; for (int i=1; i<n+1; i++) { ar[i] = sc.nextInt(); total += Math.abs(ar[i-1]-ar[i]); } total += Math.abs(ar[n]-ar[n+1]); for (int i=1; i<n+1; i++) { int a = Math.abs(ar[i-1]-ar[i+1]); int b = Math.abs(ar[i]-ar[i-1])+Math.abs(ar[i]-ar[i+1]); out.println(total+(a-b)); } } }
長さN+2の配列arを用意して、ar[1]~ar[N]に入力を詰め込んだあと、ar[0]とar[N+1]に0を入れます。その後、ループでar[0]からar[N]まで回しながら、ar[i]とar[i+1]の絶対値を計算し、totalに加算していきます（この処理は入力を受け取るのを同時にできますね、いま気づきました）。
その後、ar[1]からar[N]まで順番に見ていって、
ar[i]に立ち寄らない場合（|ar[i-1]+ar[i+1|）から立ち寄る場合（|ar[i-1]-ar[i]| + |ar[i+1]-ar[i]|）を引いたものを、すべての地点に立ち寄る場合（total）に足し、出力すればよいです。
D - Grid Components
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { //100*100の二次元配列を用意し、上半分を白、下半分を黒で塗りつぶす。 char[][] map = new char[100][100]; for (int i=0; i<100; i++) { for (int j=0; j<100; j++) { if (i<50) map[i][j] = '.'; else map[i][j] = '#'; } } //初期状態がすでにA=1,B=1なので、入力から1を引いてやり、余計なループを回さないようにする int a = sc.nextInt() - 1; int b = sc.nextInt() - 1; //下半分の黒の海のなかに、孤立した白い点を置いていくイメージ loop : for (int i=99; i>=0; i-=2) { for (int j=0; j<100; j+=2) { if (a==0) break loop; map[i][j] = '.'; a--; if (a==0) break loop; } } //上半分の白の海のなかに、孤立した黒い点を置いていくイメージ loop : for (int i=0; i<100; i+=2) { for (int j=0; j<100; j+=2) { if (b==0) break loop; map[i][j] = '#'; b--; if (b==0) break loop; } } //出力 out.println(100+" "+100); for (int i=0; i<100; i++) { for (int j=0; j<100; j++) { out.print(map[i][j]); } out.println(); } } }
500点問題ですし、見た瞬間はキツそうだなと思いましたが、考え始めて5分くらいで上記の解法が思い浮かびました。
コード中のコメントにもある通り、グリッドの大きさは指定されていないので、最初から最大のもの（100*100）を使います。
最初に、上半分を白、下半分を黒で塗ります。
この時点で、白の連結成分が1、黒の連結成分が1です。
指定された白の連結成分がa、黒がbのとき、
まず下半分の黒エリアの左下から、合計a-1マス、1マスおきに白く塗っていきます。
こんな感じです。端までいったら、白マスが隣り合わないよう、次は2つ上のマスから始めます。
上半分も黒で同じようにb-1マス塗ります。
この塗りかただと、上半分の白エリアに到達するまでに、大体1000マスくらい塗れます。
制約は白黒ともに500なので、この塗りかたでOKです。
もし1000とか1500だった場合は、白黒交互に市松模様っぽく塗れば大丈夫だと思います。
まとめ
今週の順位はなんと21位。そして全完。それもこれも、D問題が特殊だったからの一言に尽きます。
グラフやら数学やらが出題されていたら確実に死んでいただろうし……。
高校数学を復習したい、アルゴリズムを勉強したい……と以前に書いた気がしますが、最近は忙しすぎて、どちらもまともにできていません。これからさらに忙しくなるので、競プロの本格的な勉強は（キリもいいので）この辺でしばらく休止しようかと思います（そもそも始めてすらいない）。
スタックを用いた深さ優先探索
深さ優先探索は再帰関数を用いることでも実現できますが、今回はスタックを使って実装してみようと思います。ちなみに、深さ優先探索ではスタックというデータ構造（後入れ先出し）を使うのに対して、幅優先探索ではキューというデータ構造（先入れ先出し）を使います。
それでは、さっそく実装していきたいと思います。今回は以下の問題を使います。
A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder
import static java.lang.System.*; import java.util.*; //Pointクラス class Point { int x; int y; Point(int a, int b) { this.x = a; this.y = b; } } //Mainクラス public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { //変数宣言 int h = sc.nextInt(); int w = sc.nextInt(); char[][] map = new char[h][w]; boolean[][] memo = new boolean[h][w]; int sx=0,sy=0,gx=0,gy=0; //二次元配列に迷路を格納、スタート・ゴール地点を設定 for (int i=0; i<h; i++) { map[i] = sc.next().toCharArray(); for (int j=0; j<w; j++) { if (map[i][j]=='s') { sx = j; sy = i; } else if (map[i][j]=='g') { gx = j; gy = i; } } } //上下左右（分岐先）の座標を配列に入れておくと、forループで回して処理できるので便利 int[] dx = {0,1,0,-1}; int[] dy = {-1,0,1,0}; //スタックを作成、スタート地点を先頭に追加し、スタート地点を探索済みにする Deque<Point> stack = new ArrayDeque<Point>(); stack.addFirst(new Point(sx,sy)); memo[sy][sx] = true; //ここからスタックを用いた深さ優先探索 while (!stack.isEmpty()) { Point p = stack.removeFirst(); //先頭の座標を取得後、削除 for (int i=0; i<4; i++) { //forループで、上下左右に分岐させる int x = p.x + dx[i]; int y = p.y + dy[i]; //分岐先の座標が、2つのif文の条件を満たすなら先頭に追加 if (x>=0 && x<w && y>=0 && y<h) { if (map[y][x]!='#' && !memo[y][x]) { stack.addFirst(new Point(x,y)); memo[y][x] = true; //追加した座標を探索済みにする } } } } //ゴール地点が探索済みであれば到達可能 out.println(memo[gy][gx]?"Yes":"No"); } }
Pointクラスについて
座標を格納できるPointクラスを作成して利用すれば、コードを短く簡潔に記述できるのでオススメです。自作する以外にも、Javaにはjava.awt.Pointというクラスが標準クラスとして備わっていますので、そちらを使うのもアリだと思います。Pointクラスのような構造体を使用しない場合は、スタックをx座標用とy座標用の2本用意することでも実現できます。
ラムダ式の使いかたメモ
ラムダ式の使いかたを雑然とメモしていく記事です。
リスト、マップを出力する
list.forEach(e -> out.println(e)); //リストを回して出力 map.forEach((key,value) -> out.println(key+" "+value); //マップを回して出力
とくにマップを出力するときには便利。以前の僕は
for (Map.Entry<String,Integer> e : map.entrySet()) {out.println(e.getKey()+" "+e.getValue());}
と書いてマップを回していたけれど、forEach+ラムダ式のほうが断然ラク。
ラムダ式のなかで変数や式を使うこともできる
//mapを回し、キーに"aaa"を加えて値を10倍したものを出力 map.forEach((k,v) -> { k += "aaa"; v *= 10; out.println(k+" "+v); });
ラムダ式で書くときには一行しか記述できないものと思い込んでいたので、変数や式が通常のメソッドと同じように使えると知って驚いた。上級者の方がもしこの記事を見ていたら、何をそんな当たり前のことを、と思われるかもしれないが……。
streamと併用する
list.stream().filter(s -> s.length()>10).forEach(System.out::println);
とすることで、文字列の長さが10以上の要素のみ出力することができる。
『スッキリわかるJava入門』を読んだ
- 作者: 中山清喬,国本大悟
- 出版社/メーカー: インプレス
- 発売日: 2014/08/07
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (19件) を見る
経緯と動機
実をいうと僕はJava学習を一度挫折している。Javaを勉強するためにこの本を買ったはいいが、半分ほど読んだところで放り出してしまい、一年近く経ってから、競プロをはじめると同時にJava学習も再開した。この本を選んだ理由は、なんとなく分かりやすそうだったから。
雑感
自力でRPGゲームを作ることを夢見ている新入社員を主人公に据え、ほぼすべての解説がRPG仕立てになっている。たとえば、クラスを説明するときに用いられるサンプルが「ヒーロークラス」「モンスタークラス」であったり、メソッドを説明するときに用いられるサンプルが「攻撃メソッド」「逃走メソッド」であったり、といった具合だ。僕もRPG（とりわけローグライク）を作りたいと思っていた人間なので、RPG仕立ての解説にはすんなりと入っていけた。
この本から学んだこと
クラス・メソッド・インスタンスの使いかたを学べたのが一番大きな収穫。競プロを再開してしばらくの間は、メソッドの作りかたすら知らない状態でひたすらA問題やB問題を解いていたような状況だったので、この本でそれらをまとめて学ぶことができて本当によかったと思う。上記三つを使えるようになれば競プロの問題も解きやすくなるし、いざアプリを作ってみようとなったときにはもちろん必須の知識であることは言うまでもない。オブジェクト指向も、完全ではないにしろ、ぼんやりとは理解できた。それと、オブジェクト指向について思ったのは、「オブジェクト指向」というより「現実世界をシミュレーションしようとするプログラミング方法」といったほうが分かりやすいのではないか、ということ。あるいは、現実模倣指向とか。
