時間があったのでなんとなく競技プログラミングの問題を解いていましたが、
工夫なく愚直にプログラムを作るだけではダメだなと思わされた問題に遭遇したので記事にします。
問題について
問題のスゴロクについて簡単に纏めると
- 最初は右に進む
- 「#」マスに止まったら、「#」マスを「.」マスに変えて、向きを変える
- 両端の「X」マスに止まったら、向きを変える
- 「#」マス全てが「.」マスに変わるまでに何秒かかるか求める
具体例
7 4 ##..#..
上記の入力の場合、こんな感じ。
記載されたルール通りにプログラミング
最初は何も考えず、ただただ書いてある通りのルールで実行されるプログラムを作成して解答を得ようとしました。
（言語はJavaです）
/** * 解く。 * @param n 両端を除いたスゴロクのマス数 * @param a コマの初期位置 * @param s スゴロクのマスの状態（文字列配列、要素は「#」「.」のみ） * @return 解答（「#」マスが全て無くなるまでに要する時間） */ private static int solve(int n, int a, String[] s) { int vec = 1; // コマのベクトル、始めは右方向 int idx = a-1; // コマ位置 int cnt = 0; // 経過時間カウント // sの文字全てが「.」になるまでループ while(!endCheck(s)) { cnt++; idx += vec; if (idx <= -1) { // 左端まで到達したら右方向へ vec = 1; continue; } if (idx >= n) { // 右端まで到達したら左方向へ vec = -1; continue; } if ("#".equals(s[idx])) { // 「#」マスに止まった場合は「.」に変えてベクトル反転 s[idx] = "."; vec *= -1; } } return cnt; } /** * 処理が完了してるかチェック * @param s スゴロクのマスの状態 * @return 処理完了か */ private static boolean endCheck(String[] s) { for (String str : s) { if ("#".equals(str)) return false; } return true; }
サイトの入力例を元にテスト。
解答に問題なさそうだったので、投稿。
TLE（Time Limit Exceeded、制限時間超過）でNGとなりました。
そもそもNが最大で200,000なので、ルール通りにプレイして解答を得るようなことをしていたらループが多く時間が足りなくなる模様。
別の案を検討します。
解答は単純な計算で求められた
よくよく動きを見て考えてみたら、単純に計算できそうだと気づきました。
①基本的に初期地点Aから「#」マスまでの往復
「#」マスに止まったら反転、次の「#」マスに止まったらまた反転・・・
の動きを考えると、基本的には初期地点Ａから「#」マスまでの往復をしています。
よって、各「#」マスから初期地点Aまでの往復距離の合計を求めます。
②両端の「X」マスに止まるケースがある
初期地点Aを境として左右に分けるとき、左右で「#」マスの数に差があると「X」マスに止まるケースがあります。
具体的に、
- 右の方が「#」が2個以上多い場合は、【上回っている数-1】回、左の「X」マスに止まる
- 右の方が「#」が1個多い場合は「X」マスには止まらない
- 右と左で「#」が同じ数の場合は「X」マスには止まらない
- 左の方が「#」が1個以上多い場合は、【上回っている数】回、右の「X」マスに止まる
となります。
この結果を①に足す必要があります。
③最後の「#」マスに限っては往復ではなく往路のみ
最後の「#」マスに限っては「#」マスに止まった時点で「.」マスに変わるため、そこで処理終了となります。
そのため、復路の距離は必要ありません。
①②の結果から、最後の「#」マスまでの片道距離分を引かなければいけません。
初期地点Aから見て、「#」マスの数が【左＜右】の場合は右側で処理終了し、【左≧右】の場合は左側で処理終了します。
プログラムに落とし込む
あとは上記の①②③を踏まえて、プログラムに落とし込みます。
/** * 解く。【改】 * @param n 両端を除いたスゴロクのマス数 * @param a コマの初期位置 * @param s スゴロクのマスの状態（文字列配列、要素は「#」「.」のみ） * @return 解答（「#」マスが全て無くなるまでに要する時間） */ private static long solve2(int n, int a, String[] s) { a -= 1; // 1始まり→0始まりに // ①初期地点Aから「#」マスまでの往復距離合計 long totalDist = 0; // ②初期地点Aから左/右の「X」マスまでの往復距離 long leftXDist = (a + 1) * 2; long rightXDist = (n - a) * 2; // ③左端/右端の「#」マスの番号 long mostLeftSharpIdx = -1; long mostRightSharpIdx = -1; // ②③初期地点Aを境として左側/右側にある「#」マスの数 long leftSharpNum = 0; long rightSharpNum = 0; for (int idx = 0; idx < n; idx++) { // 「#」マスでのみ処理をする if (!"#".equals(s[idx])) continue; // ①初期地点Aから「#」までの往復距離計算 long dist = Math.abs(a - idx) * 2; totalDist += dist; if (idx < a) { // 左側 // ②③初期地点Aより左側の「#」カウント leftSharpNum++; // ③左端の「#」の位置 if (mostLeftSharpIdx == -1) mostLeftSharpIdx = idx; } else { // 右側 // ②③初期地点Aより右側の「#」カウント rightSharpNum++; // ③右端の「#」の位置 mostRightSharpIdx = idx; } } // 左/右での「#」マス数の差 long dif = rightSharpNum - leftSharpNum; // ②の処理 if (dif >= 2) { totalDist += leftXDist * (dif - 1); } else if (dif <= -1) { totalDist += rightXDist * (dif) * (-1); } // ③の処理 if (dif > 0) { totalDist -= Math.abs(a - mostRightSharpIdx); } else { totalDist -= Math.abs(a - mostLeftSharpIdx); } return totalDist; }
改良後の結果
提出し、無事受け入れOKでした。
まとめ
正直なところ、普通にプログラミングで何か作ろうとしたときにこんな極端なことはないと思います。
が、安易に実装してしまう前に、何か計算量を減らす工夫ができないか考えることはプログラミングをする上で大切だと改めて気づかされました。
また暇なときに競技プログラミングを解いて頭柔らかくしていきたいです。
今回の全ソース
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] na = sc.nextLine().split(" "); int n = Integer.parseInt(na[0]); int a = Integer.parseInt(na[1]); String[] s = sc.nextLine().split(""); sc.close(); //int answer = solve(n, a, s); long answer = solve2(n, a, s); System.out.println(answer); } /** * 解く。【改】 * @param n 両端を除いたスゴロクのマス数 * @param a コマの初期位置 * @param s スゴロクのマスの状態（文字列配列、要素は「#」「.」のみ） * @return 解答（「#」マスが全て無くなるまでに要する時間） */ private static long solve2(int n, int a, String[] s) { a -= 1; // 1始まり→0始まりに // ①初期地点Aから「#」マスまでの往復距離合計 long totalDist = 0; // ②初期地点Aから左/右の「X」マスまでの往復距離 long leftXDist = (a + 1) * 2; long rightXDist = (n - a) * 2; // ③左端/右端の「#」マスの番号 long mostLeftSharpIdx = -1; long mostRightSharpIdx = -1; // ②③初期地点Aを境として左側/右側にある「#」マスの数 long leftSharpNum = 0; long rightSharpNum = 0; for (int idx = 0; idx < n; idx++) { // 「#」マスでのみ処理をする if (!"#".equals(s[idx])) continue; // ①初期地点Aから「#」までの往復距離計算 long dist = Math.abs(a - idx) * 2; totalDist += dist; if (idx < a) { // 左側 // ②③初期地点Aより左側の「#」カウント leftSharpNum++; // ③左端の「#」の位置 if (mostLeftSharpIdx == -1) mostLeftSharpIdx = idx; } else { // 右側 // ②③初期地点Aより右側の「#」カウント rightSharpNum++; // ③右端の「#」の位置 mostRightSharpIdx = idx; } } // 左/右での「#」マス数の差 long dif = rightSharpNum - leftSharpNum; // ②の処理 if (dif >= 2) { totalDist += leftXDist * (dif - 1); } else if (dif <= -1) { totalDist += rightXDist * (dif) * (-1); } // ③の処理 if (dif > 0) { totalDist -= Math.abs(a - mostRightSharpIdx); } else { totalDist -= Math.abs(a - mostLeftSharpIdx); } return totalDist; } /** * 解く。 * @param n 両端を除いたスゴロクのマス数 * @param a コマの初期位置 * @param s スゴロクのマスの状態（文字列配列、要素は「#」「.」のみ） * @return 解答（「#」マスが全て無くなるまでに要する時間） */ private static int solve(int n, int a, String[] s) { int vec = 1; // コマのベクトル、始めは右方向 int idx = a-1; // コマ位置 int cnt = 0; // 経過時間カウント // sの文字全てが「.」になるまでループ while(!endCheck(s)) { cnt++; idx += vec; if (idx <= -1) { // 左端まで到達したら右方向へ vec = 1; continue; } if (idx >= n) { // 右端まで到達したら左方向へ vec = -1; continue; } if ("#".equals(s[idx])) { // 「#」マスに止まった場合は「.」に変えてベクトル反転 s[idx] = "."; vec *= -1; } } return cnt; } /** * 処理が完了してるかチェック * @param s スゴロクのマスの状態 * @return 処理完了か */ private static boolean endCheck(String[] s) { for (String str : s) { if ("#".equals(str)) return false; } return true; } }
