「第23回オフラインリアルタイムどう書く」のへなちょこ解答（Java）
今夜はオフラインリアルタイムどう書くへ行ってきました。開催から丸2年だそうです。
- オフラインリアルタイムどう書くとは
- 皆で共通のお題を好きなプログラミング言語で解いて、結果を見せ合う会です。
今回は、「くねくね増加列」です！
マス目に書かれた数字を四方に辿って、できるだけ長い狭義単調増加列を作成せよ、という内容です。詳細は問題ページをご覧ください。
1時間＋ロスタイムで解けたので、今回は簡単だったと思います。
自分の解答
いつも通りJavaで書きました。
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Snakemonic { public String solve(final String input) { int[][] tmpTable = parse(input); int[][] table = pad(tmpTable); List<Integer> results = new ArrayList<>(); for (int i = 1; i < table.length - 1; i++) { int[] line = table[i]; for (int j = 1; j < line.length - 1; j++) { results = search(table, i, j, results, 1); } } return String.valueOf(Collections.max(results)); } List<Integer> search(final int[][] table, final int row, final int collumn, final List<Integer> list, final int cnt) { List<Integer> result = new ArrayList<>(list); if (table[row][collumn] < table[row - 1][collumn]) { result = search(table, row - 1, collumn, result, cnt + 1); } if (table[row][collumn] < table[row][collumn + 1]) { result = search(table, row, collumn + 1, result, cnt + 1); } if (table[row][collumn] < table[row + 1][collumn]) { result = search(table, row + 1, collumn, result, cnt + 1); } if (table[row][collumn] < table[row][collumn - 1]) { result = search(table, row, collumn - 1, result, cnt + 1); } result.add(cnt); return result; } int[][] pad(final int[][] table) { int[][] result = new int[7][7]; for (int i = 1; i < result.length - 1; i++) { int[] line = result[i]; for (int j = 1; j < line.length - 1; j++) { result[i][j] = table[i - 1][j - 1]; } } return result; } int[][] parse(final String input) { String[] split = input.split("/"); int[][] result = new int[5][5]; for (int i = 0; i < split.length; i++) { String str = split[i]; for (int j = 0; j < str.length(); j++) { char charAt = str.charAt(j); result[i][j] = charAt - '0'; } } return result; } }
再帰を使った単純な全探索です。
- 上のコードと、テストコード: https://gist.github.com/torazuka/c14064e80a17592487ea
発表時からの修正点
いろいろ指摘をもらったので、帰りの電車で手直ししました。
- searchメソッドの引数のListに副作用を持たせるのをやめました
- その上、（副作用を使うのであれば不要な）値を戻す処理が混じっていたので、副作用を除去する方向で統一しました
- 一度辿ったマスを再び辿らないように、使用済みチェックをするテーブルを書いていましたが、消しました
- 昇順の数列を作る必要があるため、一度辿ったマスを再びカウントすることはありえません
- searchメソッドで着目するマスが番兵のとき、その後の処理をやめる処理を書いていましたが、消しました
- searchメソッドの呼び出し元で番兵を避けているので、不要でした
あと、メソッドの引数にいくつかfinalをつけていたら褒められたので、ひさしぶりにfinal厨に変身しました。
別解
鍋谷さんの解説を参考にして、入力値をパースしないバージョンも書いてみました。随分短くなりますね。
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class SnakemonicNotParse { private static final String PADDING = "//////"; public String solve(final String input) { String line = PADDING + input + PADDING; List<Integer> result = new ArrayList<>(); for (int i = PADDING.length(); i < line.length() - PADDING.length(); i++) { result = find(line, i, 1, result); } return String.valueOf(Collections.max(result)); } List<Integer> find(final String line, final int index, final int cnt, final List<Integer> list) { List<Integer> result = new ArrayList<>(list); if (Character.isDigit(line.charAt(index)) == false) { result.add(cnt); return result; } if (isTarget(line, index, PADDING.length() * -1)) { result = find(line, index - PADDING.length(), cnt + 1, result); } if (isTarget(line, index, 1)) { result = find(line, index + 1, cnt + 1, result); } if (isTarget(line, index, PADDING.length())) { result = find(line, index + PADDING.length(), cnt + 1, result); } if (isTarget(line, index, -1)) { result = find(line, index - 1, cnt + 1, result); } result.add(cnt); return result; } boolean isTarget(final String line, final int index, final int adj) { return Character.isDigit(line.charAt(index + adj)) && line.charAt(index) < line.charAt(index + adj); } }
- 上のコードと、テストコード: https://gist.github.com/torazuka/71a7d36073d5fdfe4371
