Internet Protocol Address [ AIZU ONLINE JUDGE 2889 ]
問題
省略（リンク先参照）
考察
与えられる文字列の長さは最大でも 12 なので、ピリオドの挿入位置の全探索が可能です。
挿入位置が決まると、文字列は 4 つに分割されることになります。
分割後の 4 つの文字列について、それぞれ以下の 2 つの条件を満たしているかどうか検証します。
・0 は「0」のみ認める。00 や 000 などは認められない。
・0 でないなら、先頭が 0 でない（001 のように 0 埋めされているものは認めない）。
このことを検証するには、分割後の実際の文字列と、数値型を経由させた文字列、この 2 つの長さを比べるのが手っ取り早いでしょう。
もし長さが異なるなら、その文字列は 00 や 002 といった構造になっています。
分割後の 4 つの文字列が以上の条件を満たすなら、次に、4 つがそれぞれ 255 以下であるかどうかを検証します。
もし全て 255 以下なら、有効な区切り方として数えます。
コード
static void solve (FastScanner in, PrintWriter out, Methods ms) { String s = in.next(); int length = s.length(); int ans = 0; for (int i=1; i<length-2; i++) { for (int j=i+1; j<length-1; j++) { loop : for (int k=j+1; k<length; k++) { String[] a = {s.substring(0,i), s.substring(i,j), s.substring(j,k), s.substring(k,length)}; for (int x=0; x<4; x++) { if (a[x].length() != String.valueOf(Integer.parseInt(a[x])).length()) { continue loop; } } if (Integer.parseInt(a[0]) <= 255 && Integer.parseInt(a[1]) <= 255 && Integer.parseInt(a[2]) <= 255 && Integer.parseInt(a[3]) <= 255) { ans++; } } } } out.println(ans); }
breakでループ階層の指定ができることは知っていましたが、continueでも同様のことができるとは知りませんでした。
Right triangle [ AIZU ONLINE JUDGE 2897 ]
問題
省略（リンク先参照）
考察
操作1をおこなった後の図形は、半径b・高さaの「円錐」です。「二等辺三角形」ではありません。
円錐には奥行きがあります。また、制約には a＜b とあります。
よって、操作2でこの円錐をy軸周りに回転させると、半径bの球になります。
コード
static void solve (FastScanner in, PrintWriter out, Methods ms) { double a = in.nextDouble(), b = in.nextDouble(); out.println(4.0/3.0*Math.PI*b*b*b); }
Bombs Chain [ AIZU ONLINE JUDGE 0071 ]
問題
省略（リンク先参照）
考察
幅優先探索で解きます。
詳しい実装方法は以下のコードをご覧ください。
コード
void solve (FastScanner in, PrintWriter out, Methods ms) { int n = in.nextInt(); for (int i=0; i<n; i++) { //平面を入力 int[][] map = new int[8][8]; for (int j=0; j<8; j++) { String s = in.next(); for (int k=0; k<8; k++) { map[j][k] = s.charAt(k) - '0'; } } //最初に爆発する爆弾の座標を登録 ArrayDeque<Point> dq = new ArrayDeque<>(); int x = in.nextInt()-1, y = in.nextInt()-1; dq.addLast(new Point(y, x)); //幅優先探索 while (dq.size() > 0) { //先頭の座標を一時変数に格納 Point p = dq.removeFirst(); //爆心地に0を代入 map[p.y][p.x] = 0; //爆風を受ける座標（平面外を除いたもの）をリストとして取得する ArrayList<Point> temp = p.getAround(8, 8); //そのような座標のうち、爆弾が置かれている座標だけをキューに入れる for (int j=0; j<temp.size(); j++) { if (map[temp.get(j).y][temp.get(j).x] == 1) { dq.addLast(new Point(temp.get(j).y, temp.get(j).x)); } } } //連鎖が終了した後の座標を出力する out.println("Data " + (i+1) + ":"); printIntMap(out, map); } } static void printIntMap (PrintWriter out, int[][] map) { for (int i=0; i<map.length; i++) { for (int j=0; j<map[0].length; j++) { out.print(map[i][j]); } out.println(); } } static class Point{ int y, x; Point (int a, int b) {y=a; x=b;} int getY() {return y;} int getX() {return x;} ArrayList<Point> getAround (int limitY, int limitX) { ArrayList<Point> list = new ArrayList<>(); list.add(new Point(y+1, x)); list.add(new Point(y+2, x)); list.add(new Point(y+3, x)); list.add(new Point(y-1, x)); list.add(new Point(y-2, x)); list.add(new Point(y-3, x)); list.add(new Point(y, x+1)); list.add(new Point(y, x+2)); list.add(new Point(y, x+3)); list.add(new Point(y, x-1)); list.add(new Point(y, x-2)); list.add(new Point(y, x-3)); for (int i=list.size()-1; i>=0; i--) { int y = list.get(i).y, x = list.get(i).x; if (x<0 || y<0 || x>=limitX || y>=limitY) { list.remove(i); } } return list; } }
Debt Hell [AIZU ONLINE JUDGE 0007]
問題
100000 に以下の操作を n 回おこなった後の値を求めよ。
・1.05倍し、1000未満を切り上げる
考察
まず 1.05倍する 操作についてですが、「v * 1.05」とするよりも「v * 105 / 100」としたほうが誤差が少なくなります。
次に 1000 未満を切り上げる 操作について。
値が 1000 で割り切れる場合は、1000 で切り上げる必要はなく、そのままの値にすればよいです。
そうでない場合は、1000 未満を切り捨ててから 1000 を足します。1000 未満を切り捨てるには、値から値を 1000 で割った余りを引けばよいです。
コード
void solve (FastScanner in, PrintWriter out, Methods ms) { int n = in.nextInt(); double init = 100000; for (int i=0; i<n; i++) { init = init * 105 / 100; init = init%1000==0? init : init - (init%1000) + 1000; } out.println((int)init); }
Dice I, II, III, IV [ AIZU ONLINE JUDGE ITP1_11 ]
AIZU ONLINE JUDGE の Introduction to Programming I の最後に構えている問題、Dice I, II, III, IV を全部まとめて解いてしまいたいと思います。一見すると何やらややこしそうですが、実際にはオブジェクト指向・全探索と、プログラミングの基本が詰まっている良問だと思います。
Dice I
問題文に書かれているように、サイコロ（とサイコロをそれぞれの方向に転がすメソッド）を実装して解答します。
以降の3問では、スペース節約のためにコードから Dice クラスを省略しています。
void solve (FastScanner in, PrintWriter out, Methods ms) { Dice d = new Dice(in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt()); char[] a = in.next().toCharArray(); for (int i=0; i<a.length; i++) { if (a[i] == 'N') d.turnN(); else if (a[i] == 'E') d.turnE(); else if (a[i] == 'S') d.turnS(); else if (a[i] == 'W') d.turnW(); } out.println(d.U); } static class Dice { int U, D, N, E, S, W, temp; Dice (int u, int s, int e, int w, int n, int d) { U = u; S = s; E = e; W = w; N = n; D = d; } void turnN () { temp = D; D = N; N = U; U = S; S = temp; } void turnE () { temp = W; W = D; D = E; E = U; U = temp; } void turnS () { temp = D; D = S; S = U; U = N; N = temp; } void turnW () { temp = W; W = U; U = E; E = D; D = temp; } void turnRight () { temp = W; W = S; S = E; E = N; N = temp; } void turnLeft () { temp = W; W = N; N = E; E = S; S = temp; } }
Dice II
求めたいのは「上面が u 、前面が s のときの右面の数字」です。
よって、サイコロの向きのパターンを全て列挙することを考えます。
さまざまなやり方があるかと思いますが、以下のコードでおこなっているのは、上面を固定し、サイコロを右に回すことを繰り返す方法です。
上面のパターンはいうまでもなく 6通り です。ある上面について、側面のパターンは 4通り、下面のパターンは 1通り です。すなわち、サイコロの向きのパターンは高々 24通り であることが分かります。Q は 1<=Q<=24 なので、十分間に合います。
この方法でサイコロの向きのパターンを順に列挙していき、もし上面が u 、下面が s になるようなパターンがあれば、そのときの右面を出力することでこの問題を解くことができます。
void solve (FastScanner in, PrintWriter out, Methods ms) { Dice d = new Dice(in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt()); int n = in.nextInt(); for (int i=0; i<n; i++) { int u = in.nextInt(), s = in.nextInt(); Dice temp = new Dice(d.U, d.S, d.E, d.W, d.N, d.D); loop : for (int j=0; j<6; j++) { //各面を上面に固定してから for (int k=0; k<pattern[j].length(); k++) { if (pattern[j].charAt(k) == 'N') temp.turnN(); else if (pattern[j].charAt(k) == 'E') temp.turnE(); } //右に回転させる for (int k=0; k<4; k++) { temp.turnRight(); if (temp.U == u && temp.S == s) { out.println(temp.E); break loop; } } } } } //U, S, D, N, W, E をこの順番で上面にするための回転パターン static String[] pattern = {"", "N", "N", "N", "E", "EE"};
Dice III
2つのサイコロが同一のものであるかを判定する問題です。
1つ目のサイコロを d1 、2つ目のサイコロを d2 とします。
Dice II と同じ方法で d2 の向きのパターンを全て列挙しつつ、いずれかのパターンが d1 と一致すれば Yes 、どのパターンも一致しなければ No を出力することでこの問題を解くことができます。
なお、Dice IV では複数のサイコロの一致を判定する必要があるため、上記の処理はこの問題の時点でメソッド化しています。
void solve (FastScanner in, PrintWriter out, Methods ms) { Dice d1 = new Dice(in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt()); Dice d2 = new Dice(in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt()); out.println(isSameDice(d1, d2)==true? "Yes" : "No"); } static boolean isSameDice (Dice d1, Dice d2) { for (int i=0; i<6; i++) { for (int k=0; k<pattern[i].length(); k++) { if (pattern[i].charAt(k) == 'N') d2.turnN(); else if (pattern[i].charAt(k) == 'E') d2.turnE(); } for (int j=0; j<4; j++) { d2.turnRight(); if (d1.U==d2.U && d1.S==d2.S && d1.E==d2.E && d1.W==d2.W && d1.N==d2.N && d1.D==d2.D) { return true; } } } return false; } static String[] pattern = {"", "N", "N", "N", "E", "EE"};
Dice IV
与えられた n 個のサイコロが全て異なるかどうかを判定する問題です。
上記の関数を使って、nC2 個の全てのサイコロの組み合わせについて異なるかどうかを調べればよいです。
計算量は n が最大（n = 100）のとき 100C2 * 24 = 約120,000 となり、十分間に合います。
void solve (FastScanner in, PrintWriter out, Methods ms) { int n = in.nextInt(); Dice[] d = new Dice[n]; for (int i=0; i<n; i++) { d[i] = new Dice(in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt()); } for (int i=0; i<n-1; i++) { for (int j=i+1; j<n; j++) { if (isSameDice(d[i], d[j]) == true) { out.println("No"); return; } } } out.println("Yes"); } static boolean isSameDice (Dice d1, Dice d2) { for (int i=0; i<6; i++) { for (int k=0; k<pattern[i].length(); k++) { if (pattern[i].charAt(k) == 'N') d2.turnN(); else if (pattern[i].charAt(k) == 'E') d2.turnE(); } for (int j=0; j<4; j++) { d2.turnRight(); if (d1.U==d2.U && d1.S==d2.S && d1.E==d2.E && d1.W==d2.W && d1.N==d2.N && d1.D==d2.D) { return true; } } } return false; } static String[] pattern = {"", "N", "N", "N", "E", "EE"};
The Number of Windows [ AIZU ONLINE JUDGE DSL_3_C ]
問題
長さ N の数列と整数 X（※Long型）が与えられる。
数列の部分列のうち、和が X 以下であるようなものの個数を求めよ。
考察
しゃくとり法の問題です。例によって詳細は省略します。
今回は自分で一から実装するのではなく、以下のページの尺取法テンプレを使って解いてみました。
最初、
・res (以下のコードでは count） += R - L
の部分の意味が分からなかったのですが、
・あるLについて、そのLを起点とした最長区間が求まった
・その最長区間の中に、Lを起点とした部分列は何個あるか？
・（最長区間の長さ）個ある
ということだったんですね。
例えば、和が 10 以下という条件のもとで、L = 1 のとき
・1, 2, 3, 4
という最長区間が求まったとします。このとき、L = 1 を起点とした部分列がこの中に何個あるかというと、
・1
・1, 2
・1, 2, 3
・1, 2, 3, 4
の4つです。したがって、count に 4（区間の長さ） を加算して、次の L へ移る、という処理だったんですね～。
コード
void solve (FastScanner in, PrintWriter out, Methods ms) { int n = in.nextInt(), q = in.nextInt(); int[] a = in.nextIntArray(n); for (int i=0; i<q; i++) { long x = in.nextLong(); int R = 0; long sum = 0; long count = 0; for (int L=0; L<n; L++) { while (R < n && sum + a[R] <= x) { sum += a[R]; R++; } //あるLについて、Rの最大値が求まった。このとき、Lを起点とした区間は何個存在するか？ //当然、区間の長さぶんだけ存在する。その意味での count += R-L らしい。 count += R - L; if (R == L) R++; else sum -= a[L]; } out.println(count); } } ||<
列 [ AtCoder Beginner Contest 032 C ]
問題
長さ N の数列と整数 K が与えられる。
積が K 以下であるような数列の部分列のうち、最も長いものの長さを出力せよ。
考察
しゃくとり法の典型問題……ということで何とか自力で考察・実装しました。
・積が K より大きい → 左端を伸ばす
・積が K 以下？ → 右端を伸ばす
という手順で区間を更新していきますが、実際にはもっと細かく条件設定しなければなりません。
ループの条件
・左端が「区間の右端」に到達するまで回す
左端を伸ばす条件
・左端と右端が同じ位置にない場合、かつ
・積が K より大きい、もしくは右端が「区間の右端」にある場合
右端を伸ばす条件
・左端と右端が同じ位置にある場合、あるいは
・積が K 以下、かつ右端が「区間の右端」にない場合
他の人の提出コードを見たら、while ループではなく for ループを使っている人がほとんどだったので驚きました。while ループのほうは「左端と右端を同時並行的に伸ばしていく」、for ループのほうは「左端毎に、右端を可能な限り伸ばす」というイメージでしょうか。
コード
void solve (FastScanner in, PrintWriter out, Methods ms) { //入力 int n = in.nextInt(), k = in.nextInt(); int[] a = new int[n]; //配列に格納しつつ、例外処理をする for (int i=0; i<n; i++) { a[i] = in.nextInt(); if (a[i] == 0) { out.println(n); return; } } int L = 0, R = 1; long sum = a[0]; int max = sum<=k? 1 : 0; //しゃくとり法 while (L < n) { if (L != R && (sum > k || R == n)) { sum /= a[L]; L++; } else if (L == R || (sum <= k && R != n)) { sum *= a[R]; R++; } if (sum <= k) max = Math.max(max, R - L); } out.println(max); }
