動くけどダメダメ
やっとSランクに来たわいいけど、やっぱり難しいものね。
マジで納得がいかない出来だけど、とりあえず動くものが出来たので晒し上げようかと。
今回は2つの言語で書いたよ
いつもはJavaScriptで書いていたけど、今回はJava版も書いてみたよ！
理由としてはJavaScript版だと【入力例3】を実行するとメモリエラーで落ちてしまうという問題があったため、急遽同じようなコードをJavaで書いてみて動かしてみたって感じです。
プログラムの概要
・ステージ分ループしてステージ内で起こり得る結果を生成
[
[ '1', '01', '001', '000' ], // ステージ1:x(負け),ox(勝ち負け),oox(勝勝負),ooo(勝勝勝)
[ '1', '01', '00' ], // ステージ2:x(負),ox(勝負),oo(勝勝)
[ '1', '01', '001', '000' ] // ステージ3:x(負け),ox(勝ち負け),oox(勝勝負),ooo(勝勝勝)
]
・後はそれらをループして組み合わせを文字連結して、隠し連勝数が含まれてるかをチェック
※生成した際に隠し連勝以上の連勝が有る場合は、チェック前に除外する
生成される文字列（チェック対象）の組み合わせとoxを付けてみる
x 111 // 全負け
x 1101 // ステージ1/2は初戦負け、ステージ3で1回勝った
x 11001 // ステージ1/2は初戦負け、ステージ3で2回勝った
x 11000 // ステージ1/2は初戦負け、ステージ3で全勝ち
x 1011
x 10101
x 101001
x 101000
x 1001
x 10001
o 100001
x 0111
x 01101
x 011001
x 011000
x 01011
x 010101
x 0101001
x 0101000
x 01001
x 010001
o 0100001
x 00111
x 001101
x 0011001
x 0011000
x 001011
x 0010101
x 00101001
x 00101000
x 001001
x 0010001
o 00100001
x 00011
x 000101
x 0001001
x 0001000
o 000011
o 0000101
o 00001001
o 00001000
JavaScript版
入力例2までは問題なく動くし、入力例3をステージ数10にすれば動くけど、入力例3をそのまま入れるとメモリエラーで落ちるからね！
面倒くさいので画面パタメータをListでもらった後のFunctionだけ
ちなみに引数のListを作ってる箇所はこっちの記事に書いてあるYO!!
continuousWinning.js
// [問題文（原文）]
// あなたは、ゲーム会社 PAIZA でゲームを作っているエンジニアです。あなたは、今、新しい格闘ゲームを作っています。
//
// あなたが作っているゲームは、N 個のステージからなります。 i 番目 (1 ≦ i ≦ N) のステージでは、A_i 回の試合が行われます。次の図は、入力例 1 の場合のゲームのイメージを表します。
// 3 4
// 3
// 2
// 3
//
// 試合の例
//
// ゲームのプレイヤーは、それぞれのステージの試合を順に行っていきます。しかし、ステージの途中で試合に負けた場合、そのステージにまだ残っている試合があっても、強制的に次のステージに進んでしまいます。
//
// たとえば、1 番目のステージの第 2 試合で負けているので、1 番目のステージの第 3 試合を迎えること無く 2 番目のステージに進んでしまいます。
// 試合の例
//
// あなたは、このゲームに隠し要素を付けることにしました。その隠し要素とは、「1 番目のステージからはじめ、N 個すべてのステージを終えた時点で、それまでの最大の連勝数がちょうど X だった場合、ボーナスステージが出現する」というものです。
//
// ここで、連勝数とは、連続して勝った試合の数のことを指します。先程の図の場合、最大の連勝数は、第 2 ステージの第 1 試合から第 3 ステージの第 2 試合までで連続して勝っているため、 4 になります。
//
// あなたは、隠し要素の条件を満たすようにゲームをプレイしていく方法が何通りあるかが気になりました。そこで、隠し要素の条件を満たすプレイの仕方の総数をゲームのデバッグ画面に出力することにしました。しかし、デバッグ画面には 9 桁の整数までしか表示することが出来ません。そこで、条件を満たす通り数の下 9 桁を求めてください。
//
// 例)
//
// 入力例 1 の場合、隠し要素の条件を満たすプレイの仕方の総数は全部で 7 通りあります。これは 9 桁より少ないので、そのまま 7 と答えてください。
//
// 入力例 3 の場合、隠し要素の条件を満たすプレイの仕方の総数は全部で 3,247,159,393 通りあります。この場合、下 9 桁である 247159393 と答えてください。
// 14 6
// 8
// 5
// 9
// 7
// 6
// 9
// 0
// 9
// 8
// 2
// 8
// 1
// 4
// 10
// 連勝配列
winCnt = [0];
function continuousWinning(lines) {
const [stageCount, hiddenCondition] = lines[0].split(' ').map(Number);
const stages = lines.slice(1).map(Number);
// 連勝文字列パターン
const winsPat = Array.from({ length: hiddenCondition }, () => "0").join("");
const winErrPat = winsPat + "0";
// 総試合パターン(1ステージ内で連続連勝が超えた場合のケースは削除)
const stageDP = Array.from({ length: stageCount }, (_, i) => Array.from({ length: stages[i] + 1 }, (_, ii) => [...Array.from({ length: ii }, () => "0"), "1"].slice(0, stages[i]).join("")).filter(s => !s.includes(winErrPat)));
processCombination(winsPat, winErrPat, "", stageDP, 0);
console.log(winCnt[0] > 0 ? winCnt[0] % 1000000000 : 0);
}
async function processCombination(winsPat, winErrPat, current, arrays, index) {
if (index === arrays.length) {
if (current.length >= winsPat.length && current.includes(winsPat))
await winCnt[0]++;
return;
}
// 次の配列を取得
const array = arrays[index];
// 現在の配列の各要素を処理
for (const element of array) {
const newCurrent = current + element;
// 文字連結した時点で規定連勝数を超えていたら処理しない
if (newCurrent.includes(winErrPat))
continue;
processCombination(winsPat, winErrPat, newCurrent, arrays, index + 1);
}
}
module.exports = {
continuousWinning
};
Java版
入力例3だと実行時間がそこそこかかってしまいますが、結果的には問題なく動くものになってます。
ちょっと標準入力から受け取るところ書くとか、実行時にパラメータ書き換えてやるの面倒くさかったので、mainメソッドで文字列配列を生成して、チェック用メソッドにわたすようにしています。
ContinuousWinning.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class ContinuousWinning {
public static void main(String[] args) {
// 標準出力から配列でもらった体で実装
String[] lines = {
// パターン1
"3 4",
"3",
"2",
"3"
//パターン2
// "5 1",
// "1",
// "1",
// "1",
// "1",
// "1"
// パターン3
// "14 6",
// "8",
// "5",
// "9",
// "7",
// "6",
// "9",
// "0",
// "9",
// "8",
// "2",
// "8",
// "1",
// "4",
// "10"
};
new ContinuousWinning().continuousWinning(lines);
}
public void continuousWinning(String[] lines) {
List<Integer> conditions = Arrays.asList(lines[0].split(" ")).stream().map(Integer::parseInt)
.collect(Collectors.toList());
Integer hiddenCondition = conditions.get(1);
// 隠しパターン
final String winPat = IntStream.range(0, hiddenCondition)
.mapToObj(k -> "0")
.collect(Collectors.joining());
final String winErrPat = winPat + "0";
List<List<String>> stageDP = new ArrayList<>();
// ステージループ
for (int i = 1; i < lines.length; i++) {
Integer battleOfStageCount = Integer.parseInt(lines[i]);
List<String> stagePatList = new ArrayList<>();
for (int j = 0; j < battleOfStageCount + 1; j++) {
StringBuilder pat = new StringBuilder("1");
if (j > 0) {
pat.insert(0,
IntStream.range(0, j)
.mapToObj(k -> "0")
.collect(Collectors.joining()));
}
if (pat.length() > battleOfStageCount)
pat.setLength(battleOfStageCount);
if (pat.indexOf(winPat + "0") < 0)
stagePatList.add(pat.toString());
}
stageDP.add(stagePatList);
}
long[] patCnt = { 0L };
checkWinPat(patCnt, winPat, winErrPat, "", stageDP, 0);
System.out.println(patCnt[0]);
}
private static void checkWinPat(long[] patCnt, String winPat, String winErrPat, String current,
List<List<String>> arrays, int index) {
// 最終ステージまで行った場合に、隠しパターンが含まれているかチェック
if (index == arrays.size() && current.length() >= winPat.length() && current.indexOf(winPat) >= 0) {
// 存在したらカウントアップ
patCnt[0]++;
if (patCnt[0] == 1000000000L)
patCnt[0] = 0L;
return;
}
if (arrays.size() <= index)
return;
// 次の配列を取得
List<String> array = arrays.get(index);
// 現在の配列の各要素を処理
array.stream().forEach(pat -> {
String newCurrent = current + pat;
// 文字連結した時点で規定連勝数を超えていたら処理しない
if (newCurrent.indexOf(winErrPat) >= 0)
return;
checkWinPat(patCnt, winPat, winErrPat, newCurrent, arrays, index + 1);
});
}
}
久々にEclipse使ってJavaを書いたけど、
今まであんなゴミみたいなツールでよく実装してたなと思うくらい、
VSCodeと比べてトロ臭くてガッカリしたわ。
まとめ（るほどでもないもの
これぞって言う公式とかの理解があれば簡単に解けるような問題なのかもしれないですが、
学がないので総組み合わせ総チェックというクソみたいな力技でやりきったわけで、
まぁ【仕様通り動けばいいんだよ】という最低目標は達成できたので良し！（ってことにしたい