「第19回オフラインリアルタイムどう書く」のへなちょこ解答(Java)
7日の金曜日、どう書くへ行ってきました。
- オフラインリアルタイムどう書くとは
- 鍋谷さんが出してくださるお題を、参加者が好きなプログラミング言語で解いて楽しむ会です。
今回は、「不良セクタの隣」です!
デスクを模した画像がインパクトありますね。広場の円形タイルみたいです。
不良セクタの番号が、入力として与えられます。このとき、2つ以上の不良セクタに隣接するセクタ(保留セクタ)を出力せよ、というのがお題です。問題の詳細は、上のページでご確認ください。
当日はいつも通りJavaで挑んだのですが、残念ながら回答途中で時間切れになってしまいました。週末に最後まで解いたので、解答を載せておきます。
自分の解答
import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashSet; import java.util.List; import java.util.Set; public class Nebasec { public String solve(String input) { List<Integer> defects = parse(input); Set<Integer> reservedSet = new HashSet<>(); List<Integer> result = new ArrayList<>(); for (Integer defect : defects) { List<Integer> tmp = getReserved(defect); for (Integer reserved : tmp) { if (reservedSet.add(reserved) == false && result.contains(reserved) == false) { result.add(reserved); } } } for (Integer defect : defects) { if (result.contains(defect)) { result.remove(defect); } } Collections.sort(result); return format(result); } List<Integer> parse(String input) { String[] split = input.split(","); List<String> tmp = Arrays.asList(split); List<Integer> result = new ArrayList<>(); for (String string : tmp) { result.add(Integer.valueOf(string)); } return result; } List<Integer> getReserved(Integer sec) { List<Integer> result = new ArrayList<>(); result.add(getNext(sec)); result.add(getPrev(sec)); int n = sec / 100; if (n == 1) { int mod = sec % 100 * 2; result.add(200 + mod); result.add(getPrev(200 + mod)); result.add(getNext(200 + mod)); } else if (n == 2) { if (sec % 2 == 0) { // 200台の偶数 int mod = sec % 200 / 2; result.add(100 + mod); result.add(300 + mod * 3); result.add(getPrev(300 + mod * 3)); result.add(getNext(300 + mod * 3)); } else { int div = (sec - 200) / 2; result.add(100 + div); result.add(getNext(100 + div)); result.add(300 + div * 3 + 1); result.add(getNext(300 + div * 3 + 1)); } } else if (n == 3) { if (sec % 3 == 0) { // 300台の3の倍数 int div = (sec - 300) / 3; result.add(200 + div * 2); result.add(400 + div * 4); result.add(getPrev(400 + div * 4)); result.add(getNext(400 + div * 4)); } else { int div = (sec - 300) / 3; int mod = (sec - 300) % 3; result.add(200 + div * 2 + mod - 1); result.add(getNext(200 + div * 2 + mod - 1)); result.add(400 + div * 4 + mod); result.add(getNext(400 + div * 4 + mod)); } } else if (n == 4) { if (sec % 4 == 0) { // 400台の4の倍数 int div = (sec - 400) / 4; result.add(300 + div * 3); } else { int div = (sec - 400) / 4; int mod = (sec - 400) % 4; result.add(300 + div * 3 + mod - 1); result.add(getNext(300 + div * 3 + mod - 1)); } } return result; } int getNext(int n) { if (n == 107) { return 100; } if (n == 215) { return 200; } if (n == 323) { return 300; } if (n == 431) { return 400; } return n + 1; } int getPrev(int n) { if (n == 100) { return 107; } if (n == 200) { return 215; } if (n == 300) { return 323; } if (n == 400) { return 431; } return n - 1; } String format(List<Integer> result) { if (result.isEmpty()) { return "none"; } StringBuilder sb = new StringBuilder(); for (Integer integer : result) { sb.append(String.valueOf(integer)); sb.append(","); } return sb.toString().substring(0, sb.length() - 1); } }
- 上のコードと、テストコード https://gist.github.com/torazuka/9463450
考え方
処理の概要はsolveメソッドで、こんなかんじです。
- 入力文字列をカンマで分けて、IntegerのListにする。これが、不良セクタのリスト。
- 不良セクタのリストを1つずつ調べる。
- getReservedメソッドで、隣接するセクタ群をIntegerのListに取る。これが、保留セクタの候補リスト。
- 保留セクタの候補リストを1つずつ調べる。
- HashSetへの追加を試みる。同じ値がすでに登録されている場合、falseが返ってくるので、不良セクタの隣接セクタとして2度以上検出されたとみなし、解答のリストに加える。
- ただし、解答のリストにすでに追加されている場合は、無視。
- 不良セクタのリストにある値を、解答のリストから除去する。
- 問題に明記されていませんでしたが、保留セクタとして検出されたセクタが不良セクタでもある場合は、保留セクタとして扱わないという制約があるため。(この制約を確認するために、gistのコードにはテストデータを1つ足しました)
Setについて
Setに追加できないことをもって重複を検出するのは、Setの便利な使い方ですよね。
しかし、重複が検出されたものを集めるCollectionにもまた、重複を許してはいけないという制約があるのに、Listを使ってしまっています。そのため、最後にフィルタリングが必要になりました。
改善するならこの部分だと思います。TreeSetとか使えばよいのかもしれません。
戦略
隣接するパターンを式で表わす戦略にしました。
不良セクタが100台のとき、隣接するセクタは1パターンです。
次の図は、101が不良セクタの場合の例です。
不良セクタが200台のとき、2の倍数とそうでないときで、隣接するセクタは2パターンあります。
次の図は、202(2の倍数)と207(2の倍数でない数)が不良セクタの場合の例です。
不良セクタが300台のとき、3の倍数とそうでないときで、隣接するセクタは2パターンあります。
次の図は、303(3の倍数)と310(3の倍数でない数)が不良セクタの場合の例です。
不良セクタが400台のとき、4の倍数とそうでないときで、隣接するセクタは2パターンあります。
次の図は、404(4の倍数)と413(4の倍数でない数)が不良セクタの場合の例です。
このパターンを式にしたのが、getReservedメソッドの中身です。もうちょっとパターン化して書ける気がしますが、こういうの苦手で……(ゴニョゴニョ)。当日は、400台を書いているあたりで時間切れになりました。悔しい!
数字のリングについて
リング状になった数列を辿るイディオムが知りたいです。
問題では、107の次が100に、215の次が200に、323の次が300に、431の次が400になっています。これを上手く前に辿ったり後ろに辿ったりする書き方のことです。
今回は4箇所だったので、getNextメソッドとgetPrevメソッドの中に、値を直書きしてしまいました。
追記(2014/03/12) 教えていただきました。 リング状の数列を辿る
というわけで
しばらく広場のタイルを見たくない気分ですが、今回も楽しかったです。ありがとうございました。