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問題を解いていたような状況だったので、この本でそれらをまとめて学ぶことができて本当によかったと思う。上記三つを使えるようになれば競プロの問題も解きやすくなるし、いざアプリを作ってみようとなったときにはもちろん必須の知識であることは言うまでもない。オブジェクト指向も、完全ではないにしろ、ぼんやりとは理解できた。それと、オブジェクト指向について思ったのは、「オブジェクト指向」というより「現実世界をシミュレーションしようとするプログラミング方法」といったほうが分かりやすいのではないか、ということ。あるいは、現実模倣指向とか。
AtCoder Beginners Selection
AtCoder Beginners Selectionの問題を解いてみました。全十問。
AtCoder Beginners Selection - AtCoder Beginners Selection | AtCoder
PracticeA - はじめてのあっとこーだー(Welcome to AtCoder)
import java.util.*; import static java.lang.System.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); String s = sc.next(); out.println((a+b+c)+" "+s); } }
特になし。
ABC086A - Product
import java.util.*; import static java.lang.System.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int a = sc.nextInt(); int b = sc.nextInt(); out.println(a*b%2==0?"Even":"Odd"); } }
三項演算子を使った。
ABC081A - Placing Marbles
import java.util.*; import static java.lang.System.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { String s = sc.next(); int num = 0; for (int i=0; i<s.length(); i++) { if (s.charAt(i)=='1') num++; } out.println(num); } }
sを先頭から1文字ずつ調べて、1であればカウントを増やす。
ABC081B - Shift only
import java.util.*; import static java.lang.System.*; 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]; boolean F = false; for (int i=0; i<n; i++) { ar[i] = sc.nextInt(); if (ar[i]%2==1) {F = true;} } if (F == true) {out.println(0);} else { int min = Integer.MAX_VALUE; for (int i=0; i<n; i++) { int times = 0; while (ar[i]%2==0) { ar[i] /= 2; times++; } min = Math.min(min,times); } out.println(min); } } }
奇数が1つでも含まれていれば0回なので、まずは奇数が含まれているかどうかを判定した。そのあと、実際にすべての値を2で割ってみて、割れた回数のうち一番少ないものが答え。
ABC087B - Coins
import java.util.*; import static java.lang.System.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); int x = sc.nextInt(); int num = 0; for (int i=0; i<=a; i++) { for (int j=0; j<=b; j++) { for (int k=0; k<=c; k++) { if (500*i+100*j+50*k == x) num++; } } } out.println(num); } }
素直に三重ループを使った。
ABC083B - Some Sums
import java.util.*; import static java.lang.System.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); int a = sc.nextInt(); int b = sc.nextInt(); long total = 0; for (int i=1; i<=n; i++) { String s = String.valueOf(i); int sum = 0; for (int j=0; j<s.length(); j++) { sum += Character.getNumericValue(s.charAt(j)); } if (sum<=b && a<=sum) total += i; } out.println(total); } }
たとえば1000の位の数字を求めるには1000で割ってやればよいのだが、めんどくさいので文字列に変換してから各桁の数字を足し合わせる方針をとった。
ABC088B - Card Game for Two
import java.util.*; import static java.lang.System.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); Integer[] ar = new Integer[n]; for (int i=0; i<n; i++) ar[i] = sc.nextInt(); Arrays.sort(ar,Comparator.reverseOrder()); int alice = 0; int bob = 0; for (int i=0; i<n; i++) { if (i%2 == 0) alice += ar[i]; else bob += ar[i]; } out.println(alice-bob); } }
Integer型を使ったのは、降順ソートが使えるから。Int型配列に入れて昇順にソートしてもいいのだが、それをすると配列の最後の要素の添字を奇数と偶数で場合分けする必要が生じてしまう。
ABC085B - Kagami Mochi
import java.util.*; import static java.lang.System.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); Set<Integer> set = new HashSet<>(); for (int i=0; i<n; i++) set.add(sc.nextInt()); out.println(set.size()); } }
問題文を読むと、求めたいのは「大きさの重複がないようにモチを選んだときの総数」であることが分かるので、モチをSetに片っ端からぶち込んでいき、Setの要素数を出力すればよい。
ABC085C - Otoshidama
import java.util.*; import static java.lang.System.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); int total = sc.nextInt(); int a = -1; int b = -1; int c = -1; for (int i=0; i<=total/10000; i++) { for (int j=0; j<=(total-10000*i)/5000; j++) { int k = n - (i+j); if (10000*i+5000*j+1000*k == total) { a=i; b=j; c=k; break; } } } out.println(a+" "+b+" "+c); } }
すっと書けてすっと通ったので、自分の成長ぶりに自分でも驚いた(以前に一度解いていることもあるだろうけど)。上で解いた「ABC087B - Coins」に比べてnの値が大きいので、愚直にループを回していてはおそらく正解できない。そこで、i(一万円の枚数)は必ず「お年玉/10000」以下であることを利用し、ループの回数を減らす。jも同様。千円の枚数については、一万円と五千円の枚数が定まれば「n-(一万円の枚数+五千円の枚数)」で一意に定まるので、ループを回す必要はない。このようにして二重のループを回し、値が見つかったらbreakして出力する。
ABC049C - 白昼夢 / Daydream
import java.util.*; import static java.lang.System.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { String s = sc.next(); s = s.replaceAll("eraser",""); s = s.replaceAll("erase",""); s = s.replaceAll("dreamer",""); s = s.replaceAll("dream",""); out.println(s.equals("")?"YES":"NO"); } }
以前解いたときに読んだ解説には、文字列を逆さまにして判定……といったことが書かれていたような気がするのだが、ひょっとしてそんなことしなくても正規表現で処理できるのではないかと思い、やってみたところWAを生やした。原因は、「eraser,erase」より先に「dreamer,dream」を置換していたせい。そうしてしまうと、たとえば「dreamerase」という文字列、これはYES(可能な)と出力すべき文字列なのだが、dreamerを最初に空文字列に置換してしまうと、「ase」が残り、うまく処理できない。こうなってしまうことを避けるために、まずは「erase,eraser」を置換し、次に「dreamer,dream」を置換する。最後に残ったのが空文字列であれば(すべてが上記の4単語から構成されているなら)YES、そうでなければNOを出力して終わり。
ABC086C - Traveling
import java.util.*; import static java.lang.System.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); int t,x,y,dis; String ans = "Yes"; for (int i=0; i<n; i++) { t = sc.nextInt(); x = sc.nextInt(); y = sc.nextInt(); dis = x+y; if (dis > t) { ans = "No"; break; } else if (dis < t) { if ((t-dis)%2 == 1) { ans = "No"; break; } } } out.println(ans); } }
時刻0に(0,0)にいるとして、予定を処理していく。たとえば入力例1には3,1,2とあるが、これは時刻3までに(1,2)へ行けますか、ということになる。まず、(0,0)と(1,2)のマンハッタン距離を求める。3である。時刻と距離が等しいとき、必ずたどり着ける。時刻より距離が大きいとき、決してたどり着けない。問題は時刻より距離が小さい場合である。言い換えるなら、時間に余裕がある場合。その場にとどまって時間を潰すことはできないので、必然的に、目的の座標とその隣の座標のあいだを、時間がなくなるまで往復し続けることになる。このとき、余った時間(時刻-距離)が偶数の場合は、時刻ちょうどに座標にたどり着ける。逆に奇数の場合はたどり着けない。といった感じで、条件分岐を実装してやれば解ける。実際には、x+yとtの偶奇を調べるだけで解けるようなのだが、解答中はそこまで思いつかなかった。なお、現在座標をいちいち変えながらシミュレーションする必要はない……と思ったが、たとえばn=2,(3,0,3),(4,0,0)のときはどうだろう。時刻3のとき(0,3)にはたどり着けるが、時刻4、つまりその1時刻後に(0,0)に戻ることはできない。これをACしたコードで読み込むとYESとなってしまう……うーん、よく分からないので深く考えないでおこう。
感想
どれもクセのない問題ばかりで、たしかに初心者にはうってつけの問題集かもしれない。僕としては、二次元配列を処理する問題(画像処理とか迷路とか)が好きなので、そういう問題も欲しかったな~とは思った。