AtCoder ABC 054 B&C
やってみて思ったんだけど、実行速度がかなり遅い。
具体的にはfor文のみで記載した場合に比べて3倍遅い。
そして、ただ単にfor文を置き換えた場合、これは何というか。。。
この類のコードの場合、巷で言われる「for/whileを排除すれば可読性が上がる」という話が当てはまらない気がするが。。。とりあえずやってみた。という感じ。
書き方変更すればもっと速くなるのかな？
もっと検討してなれる必要があるな。
B問題
nextInt()での読み出しをStreamの中で処理している。
mapToObjでマッピングしたのち、toArrayでArrayに集約。
private void solveB2() {
int numN = nextInt();
int numM = nextInt();
String[] wkA = IntStream.range(0, numN).mapToObj(i -> next()).toArray(i -> new String[numN]);
String[] wkB = IntStream.range(0, numM).mapToObj(i -> next()).toArray(i -> new String[numM]);
boolean res = chkB2(wkA, 0, wkB, 0);
out.println(res ? "Yes" : "No");
}
wkAの配列の中からwkBにマッチするものを探す処理で利用。
anyMatchを使う。
- anyMatchは
空Streamの場合はfalseを返す。 - allMatchは
空Streamの場合はtrueを返す。
上記仕様は気をつけんとあかんな。特にallMatch。
private boolean chkB2(String[] wkA, int currentA, String[] wkB, int aPos) {
boolean res = false;
//wkAの残りがwkBより少ない場合は探索できない
if (wkA.length - currentA < wkB.length) {
return false;
}
//wkA[]の残り長がwkB[]より少ない場合は探索できない
if (wkA[currentA].length() - aPos < wkB[0].length()) {
return false;
}
//まず、Aの位置を決める
//そのために、BのcurrentB列目がAのcurrentA列目どこに出現するのか確認
//Aの横軸の値を取得
//※Aの横軸は複数取得できる可能性がある。
//BのcurrentB列目がAのcurrentA列目どこに出現するのか確認
boolean aPosWk = wkA[currentA].startsWith(wkB[0], aPos);
if (aPosWk) {
//Aの横軸出現したらcurrentA+1の列の横軸から、B列のcurrentB+1が出現するのか確認
res = IntStream.range(0, wkB.length).anyMatch(i -> wkA[currentA + i].startsWith(wkB[0 + i], aPos));
}
//Aの横軸が出現しなかったら、aPos+1列目を検索
//このaPosでは一致しない場合、aPosを+1して再探索
if (!res) {
//B列のcurrentB+1が出現しなかったら、もう一度、Aの横軸を検索
int len = wkA[currentA].indexOf(wkB[0], aPos + 1);
//横列にまだ候補があるので再検索
if (len >= 0) {
res = chkB(wkA, currentA, wkB, len);
}
}
//aPosが0でない場合は次のcurrentIdを
if (!res && aPos == 0) {
//Aの横軸が出現しなかったら、currentA+1行目を検索
res = chkB(wkA, currentA + 1, wkB, 0);
}
return res;
}
C問題
forEachの中でindexを取得して中で処理。
隣接行列を作るために外部のArrayを参照している。
ただ、「外部のArrayを参照している」時点でダメな気がする。
もっといい書き方ないか？
private void solveC2() {
int numN = nextInt();
int numM = nextInt();
boolean[][] wk = new boolean[numN][numN];
IntStream.range(0, numM).forEach(i -> {
int iA = nextInt();
int iB = nextInt();
wk[iA - 1][iB - 1] = true;
wk[iB - 1][iA - 1] = true;
});
boolean[] visited = new boolean[numN];
visited[0] = true;
int res = chkSolveC2(wk, 0, visited);
out.println(res);
}
処理本体の方は、条件文をfilter()に置き換えて、reduce()で畳み込み処理。
<U> U reduce(U identity,
BiFunction<U, ? super T, U> accumulator,
BinaryOperator<U> combiner);
やってみた感じ、隣接個所であるwkGを取り出して処理するところの扱いがわからない。
boolean[][] wkはfinalとして宣言しても構わない（というかそれが正しい）ので、、、
ここまで書いて思ったけど、reduce内で直接wkGを取り出してしまえばよいのかもしれない。
コメントアウトしているところは、reduceではなくforEachで実装してみたところ。
ただ、AtomicIntを使わないと再帰の戻り値を集計できなかったので気持ち悪くなったためreduceでの実装に切り替えた。
こう見ると、reduceがある状況下でforEach使うかな？
reduceはloop中でbreakできないけど、forEachならbreakできるみたいな例外があるならforEach使うかもしれんけどそういう例外があるわけではないし。
わざわざStreamを使っている状況で副作用のあるforEachを使う理由がいまいちわからんな。
private int chkSolveC2(boolean[][] wk, int currentI, boolean[] visited) {
boolean res = true;
res = IntStream.range(0, visited.length).allMatch(i -> visited[i] == true);
if (res) {
return 1;
}
boolean[] wkG = wk[currentI];
int sum = IntStream.range(0, wkG.length).filter(index -> wkG[index] && !visited[index])
.reduce(0, (sumResult, targetIndex) -> {
visited[targetIndex] = true;
int resNum = chkSolveC2(wk, targetIndex, visited);
visited[targetIndex] = false;
return sumResult + resNum;
});
return sum;
// AtomicLong temp = new AtomicLong();
// boolean[] wkG = wk[currentI];
// IntStream.range(0, wkG.length).filter(i -> wkG[i] && !visited[i]).forEach(i -> {
// visited[i] = true;
// temp.addAndGet(chkSolveC2(wk, i, visited));
// visited[i] = false;
// });
//
// return temp.intValue();
}