Room Numbers of a Hospital [AOJ0208]
Room Numbers of a Hospital | Aizu Online Judge
いかにも競プロで出題されそうな問題だなと思いました。
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { while(true) { int n = sc.nextInt(); if (n == 0) break; String s = Integer.toOctalString(n); s = s.replace("7","9").replace("6","8").replace("5","7").replace("4","5"); out.println(s); } } }
この問題のキモは、新部屋番号が｛0,1,2,3,5,7,8,9｝のみで構成される8進数（に類するもの）になっているということです。したがって、旧部屋番号を8進数に変換し、結果を上記の8つの数字に対応させていけばよいです。
・4 -> 5
・5 -> 7
・6 -> 8
・7 -> 9
ここで気をつけなければならないことが一つ。
結果を数字の小さい順に変換していった場合、4が5に変換され、5が6に変換され……といったように重複して変換されてしまう可能性があるので、大きい順に変換する必要があります。
一般的なUIデザインにおいて「はい」が左側、「いいえ」が右側の理由
仮説１
人口の大多数を占める右利きの人の場合、「はい」を押すときにはマウスを持った手は内側に移動し、「いいえ」を押すときには外側に移動する。言うまでもなく、内向きとは受け入れることであり、外向きとは拒否することである。そのイメージが設計者の意識に発現している……という説。
仮説２
「はい」か「いいえ」で答えろ、「はい」と「いいえ」どっち、のように、日本語の自然な流れとして「はい→いいえ」の順序が存在している。この通りに配置すると、日本語は左から読む言語なので、「はい」が左にきて、「いいえ」が右にくる……という説。
仮説３
マウスを右手で持って操作するとき、カーソルは画面の右側にあることが多い（と思われる）。アプリ内、ウィンドウ内でも同様。このとき、「はい」「いいえ」付きの確認ウィンドウが表示されたとすると、左側にある「はい」よりも右側にある「いいえ」のほうが押しやすい位置にある。「はい」ボタンの役割とは、決定であり、それはしばしば金銭や権利の移動を伴う重大な決断となる。逆に「いいえ」の役割は、拒否することであり、基本的には再度当該ウィンドウを出現させることができ、やり直しが効くものである。よく説明文を読まずに、あるいは誤ってクリックされてしまったとき、被害が少ないのはどちらだろうか。言うまでもなく後者の「いいえ」である……という説。
Magical Tiles [AOJ0104]
某国民的ゲームに出てくる仕掛けを彷彿とさせる問題です。解いていて楽しかったです。
package Blog; import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); static char[] d = {'>','<','^','v'}; static int[] dx = {1,-1,0,0}; static int[] dy = {0,0,-1,1}; public static void main(String[] args) { while(sc.hasNext()) { int h = sc.nextInt(); int w = sc.nextInt(); if (h==0 && w==0) break; char[][] map = new char[h][w]; for (int i=0; i<h; i++) { String s = sc.next(); for (int j=0; j<w; j++) { map[i][j] = s.charAt(j); } } boolean[][] memo = new boolean[h][w]; int x = 0; int y = 0; boolean loop = false; memo[y][x] = true; loop1: while (map[y][x] != '.') { for (int i=0; i<4; i++) { if (map[y][x]==d[i]) { x += dx[i]; y += dy[i]; if (memo[y][x]) { loop = true; break loop1; } else memo[y][x] = true; } } } out.println(loop?"LOOP":x+" "+y); } } }
記述量を減らすため、方向タイルとそれに対応する移動量を三つの配列（d,dx,dy）で管理しています。
この問題で難しいのはループしているかどうかの判定だと思います。
ループしているかどうかを判定するには、一度通った場所を記録しておく二次元配列を別途用意する必要があります。
上記のソースコードではboolean型の二次元配列を用意し、通った場所を順次trueにしています。
ループの終了条件は「一度通った場所を再び訪れる、あるいは.（ピリオド）に到達する」です。
Joseph's Potato [AOJ0085]
package Blog; import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { while(sc.hasNext()) { int n = sc.nextInt(); int m = sc.nextInt(); if (n==0 && m==0) break; LinkedList<Integer> list = new LinkedList<>(); for (int i=1; i<=n-1; i++) list.add(i); list.addFirst(n); list.addLast(list.removeFirst()); while (list.size() != 1) { for (int i=0; i<m-1; i++) list.addLast(list.removeFirst()); list.removeFirst(); } out.println(list.getFirst()); } } }
この問題では、配列ではなくリング構造を使ったほうが分かりやすそうだったので、LinkedListを使って解いてみました。
・list.addLast(list.removeFirst());
の部分が、「先頭の要素を末尾に追加する」操作、いわば「リングを回す」操作になっています。問題においては「イモを右の人に渡す」操作ですね。
m回目に渡された人を除外する、という操作は、
・list.removeFirst();
の部分です。
除外するという操作の関係上、初回のイモ渡しのみループの外で行っています。
今回の問題では制約がm,n<1000と小さかったのでシミュレーションしましたが、これがもっと大きい場合は何か法則性を見つけて数学的に解く必要がありそうです。
リング構造が必要とされる問題はいままでほとんど解いたことがなかったのですが、今回のようにLinkedListを使うと簡単に解けそうなので、覚えておきたいです。
計数ソート [ALDS1_6_A : Counting Sort]
計数ソート | アルゴリズムとデータ構造 | Aizu Online Judge
AIZU ONLINE JUDGEの問題です。
package Blog; 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+1]; int[] count = new int[10001]; for (int i=1; i<n+1; i++) { int temp = sc.nextInt(); ar[i] = temp; count[temp]++; } for (int i=1; i<10001; i++) { count[i] = count[i] + count[i-1]; } int[] ans = new int[n+1]; for (int i=n; i>=1; i--) { ans[count[ar[i]]] = ar[i]; count[ar[i]]--; } StringBuilder sb = new StringBuilder(); sb.append(ans[1]); for (int i=2; i<n+1; i++) sb.append(" "+ans[i]); out.println(sb); } }
面白いソート方法だなと思いました。
流れとしては、
①ソート対象となる配列（A）を用意
②Aの各要素について、それぞれ何回登場するか数え、別の配列（B）に記録する
③Bを累積和にかける
④Bを参考にして、Aの要素をさらに別の配列（C）に配置していく
といった感じでしょうか。配列を三本も使っていて、一見すると効率は悪そうです。
競プロでよく使う書き方、
・カウント用配列[要素]++;
というのが出てきました。
1オリジン配列を扱うので、添え字やループカウンタの書き間違いには注意したいところです。
AtCoder Beginner Contest 099
今回は惨敗に終わりました。ですのでその原因を徹底的に考察していこうと思います。
A - ABD
1~999と1000~1998に場合分けすれば終わり、のはずなのだが……。
ABCかABD、このどちらかを出力すればいいはずなのに、その後ろの数字まで出力するプログラムを書いてしまっていた。途中で気がつき、慌てて変更した。
問題文だけでなく入力と出力までよく目を通すこと。
B - Stone Monument
入力において与えられるのは「まだ完全には雪に埋もれていない二つの塔の、埋もれていない部分の高さ」である。よって、aとbの高さの差を求めることができる。
さて、999本の塔のうち、1本目と2本目の高さの差は2である。同様に、2本目と3本目の高さの差は3。つまり、n本目とn+1本目の高さの差はn+1ということになる。
入力例1でいくと、aは8であり、bは13である。二本の塔の高さの差は5であるから、aが4本目、bが5本目である。n本目の塔の高さは1~nまでの累積和で求められるので、aの本来の高さは10m。よって10-8=2を出力すればよい。
C - Strange Bank
解説読んでも分からない
D - Good Grid
またこんど
まとめ
勉強不足
マージソート [ALDS1_5_B : Merge Sort]
マージソート | アルゴリズムとデータ構造 | Aizu Online Judge
AIZU ONLINE JUDGEの問題です。
一概にマージソートといっても、さまざまな実装方法があるようで、それで迷ってしまって実装するのにやたらと時間がかかってしまった。
僕が今回用いた実装方法は再帰で、実装するにあたっては以下のページをおおいに参考にしました。
マージソート - やさしいデスマーチ
package Blog; import static java.lang.System.*; import java.util.*; public class Blog { static Scanner sc = new Scanner(System.in); static List<Integer> list = new ArrayList<>(); static int num = 0; public static void main(String[] args) { int n = sc.nextInt(); for (int i=0; i<n; i++) list.add(sc.nextInt()); mergeSort(list); for (int i=0; i<list.size(); i++) out.print((i==0?"":" ")+list.get(i)); out.println(); out.println(num); } static void mergeSort(List<Integer> list) { int size = list.size(); //listの大きさが1なら再帰終了 if (size == 1) return; //1でないなら分割 ArrayList<Integer> L = new ArrayList<>(), R = new ArrayList<>(); int M = size/2; //分割処理、左側を作成 for (int i=0; i<M; i++) L.add(list.get(i)); //分割処理、右側を作成 for (int i=M; i<size; i++) R.add(list.get(i)); //再帰 mergeSort(L); mergeSort(R); //マージ処理 list.clear(); int indexL = 0, indexR = 0; while (indexL<L.size() || indexR<R.size()) { if (indexL == L.size()) { list.add(R.get(indexR)); indexR++; num++; } else if (indexR == R.size()) { list.add(L.get(indexL)); indexL++; num++; } else { int tempL = L.get(indexL); int tempR = R.get(indexR); if (tempL <= tempR) { list.add(tempL); indexL++; } else { list.add(tempR); indexR++; } num++; } } } }
「//再帰」の部分を通過した時点で、リストLとリストRはそれぞれ少なくとも1つ以上の要素を持っていることになる。
次にこの二つのリストをマージ（結合）していくことになるのだが、この結合の処理が少し難しい。
二つのリストのそれぞれ先頭の要素を比較して、小さいほうから結合結果用リストに詰めていく。やることはこれだけなのだが、今回扱っているリストは連結リストではないので、それぞれ添え字を用意してやる必要がある。
参考にしたページではループを三回使っていたが、劣化コピーにはなりたくなかったので、何とか工夫して1ループに抑えてみた。
ループの処理の流れとしては、
＜継続条件：LもしくはRに要素が残っている＞
①Lに要素が残っていないなら、Rの先頭の要素を詰める
②Rに要素が残っていないなら、Lの先頭の要素を詰める
③上のどちらでもない（LにもRにも要素が残っている）なら、それぞれの先頭の要素を比較して、小さいほうを詰める
といった具合。
連結リストなら添え字を使う必要がなく、実装が多少は楽になると思う。その代わり、分割処理のほうが大変になると思われる。マージソートについて調べていて、マージソートは連結リストでこそ活躍する、とか何とか書いてある記事も見かけたので、今度時間があればマージソートと連結リストの関係について調べてみたい。
追記：番兵を使えばループ内処理をもっとスマートに書けた可能性アリ
ところで、このソースコードをそのままAIZU ONLINE JUDGEのページで提出するとTLEになる。これは、以前yukicoderの問題を解いていたときにも発生したのだが、Javaはどうもコンソール出力処理が遅いようで、要素数何十万という配列を順にコンソール出力していくと大抵TLEになってしまう。これを解決するには、StringBuilderで出力を文字列1つにまとめてから、出力する必要がある。
