AtCoder ABC 129 A&B&C&D
Bで50分以上溶かして途中泣きそうでしたまる
EとFは解法みて今月中に更新する！
A - Airplane
入力例を見て混乱したが、まぁ普通に読めば以下を問われているのがわかるよね。。。
- A-BとB-CとC-Aを移動するのに必要な時間が与えられるから、A-B-C全て回ることができる最短時間を求める
private void solveA() {
int p = nextInt();
int q = nextInt();
int r = nextInt();
out.println(Math.min(q + r, Math.min(p + q, p + r)));
}
B - Balance
入力例２がなぜそうなるのか理解できなくて大分溶かしました。。。
理由？何故か、入力したのをソートするべき！と思い込んだからですね。
自戒のためにコメントアウトでソートを残してる。。。
解法としては、以下
- iを1 - N-1まで動かして、0-i番目迄の合計とi+1 - N番目迄の合計の差が一番小さい値を出す
で、本番では累積和使いました（入力例2が理解できなくて「全探索じゃないよね？」的な思い込みが、、、）がやりすぎ。。
累積和
private void solveB() {
int n = nextInt();
int[] wk = IntStream.range(0, n).map(i -> nextInt()).toArray();
// sortedなんて入れるから... int[] wk = IntStream.range(0, n).map(i -> nextInt()).sorted().toArray();
int[] rui = new int[n];
//0-Nの累積和を行う
rui[0] = wk[0];
for (int i = 1; i < rui.length; i++) {
rui[i] = rui[i - 1] + wk[i];
}
long res = Integer.MAX_VALUE / 10;
/*
* 実際にT候補の数値を探すためにiを1からn-1まで移動させる
* 2グループに分けるためには、一番最初または最後まで行ってはいけない
* (rui[n - 1] - rui[i]) -> i+1からNまでの和
* rui[i] -> 0からiまでの和
*/
for (int i = 1; i < n - 1; i++) {
res = Math.min(res, Math.abs((rui[n - 1] - rui[i]) - rui[i]));
}
out.println(res);
}
全探索版
- sum1とsum2のところ、もっときれいに書けると思うんですがちょっと思いついてません。
private void solveB2() {
int n = nextInt();
int[] wk = IntStream.range(0, n).map(i -> nextInt()).toArray();
long res = Integer.MAX_VALUE / 10;
for (int i = 1; i < n - 1; i++) {
int sum1 = 0;
int sum2 = 0;
for (int j = 0; j < n; j++) {
if (j <= i) {
sum1 += wk[j];
} else {
sum2 += wk[j];
}
}
res = Math.min(res, Math.abs(sum1 - sum2));
}
out.println(res);
}
C - Typical Stairs
- 問題名通り、本当にTypicalなDP
- DPのサイズを
n+1ではなくてn+3にすれば、i + 2 <= nやi + 1 <= nの判定いらない
- DPのサイズを
参考
自分も全部終わらせていない(高配点問題全然解けない！)けど以下のコンテストがお役に立ちます。
AtCoder - Educational DP Contest / DP まとめコンテスト
AtCoder - Typical DP Contest
drkenさんの記事：動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集
drkenさんの記事：Educational DP Contest の F ～ J 問題の解説と類題集
※今回は配る方で実装。後で貰う方でも実装してみる
private void solveC() {
int n = nextInt();
int m = nextInt();
Set<Integer> key = new HashSet<Integer>();
for (int i = 0; i < m; i++) {
key.add(nextInt());
}
long[] dp = new long[n + 1];
dp[0] = 1;
long CONST_MOD = (long) (Math.pow(10, 9) + 7);
for (int i = 0; i <= n; i++) {
if (key.contains(i)) {
continue;
}
if (i + 2 <= n) {
dp[i + 2] = dp[i + 2] % CONST_MOD + dp[i] % CONST_MOD;
}
if (i + 1 <= n) {
dp[i + 1] = dp[i + 1] % CONST_MOD + dp[i] % CONST_MOD;
}
}
out.println(dp[n] % CONST_MOD);
}
D - Lamp
-
結構典型的な累積和の問題だった気がする
-
縦と横でそれぞれ累積和をとって最後に重ね合わせるイメージ
- 縦に何マス照らせるのか？横に何マス照らせるのか？を最初に作っておく
- コード途中にコメントで入力例1をもとにどんな操作をしているかを記載
-
累積をしておくことによって、[i][j]を見た際、Hの累積和の結果とWの累積和の結果を足すことができる
コンテスト中にコメント入れながら書いているからコード書くの遅いんだろうな
private void solveD2() {
int h = nextInt();
int w = nextInt();
char[][] wk = new char[h][w];
for (int i = 0; i < wk.length; i++) {
wk[i] = next().toCharArray();
}
int[][] rui1 = new int[h][w];
/*
* Wについて累積和を作成
*/
for (int i = 0; i < h; i++) {
int cnt = 0;
/*
* 入力例1だと、以下みたいな感じ(横並び)
* 012012
* 123450
* 123401
* 010123
*/
for (int j = 0; j < w; j++) {
if (wk[i][j] == '.') {
cnt++;
} else {
cnt = 0;
}
rui1[i][j] = cnt;
}
/*
* 累積した結果をならす(横並び)
* 012012
* 123450
* 123401
* 010123
* を
* 022022
* 555550
* 444401
* 010333
* に変換
*/
for (int j = w - 1; j > 0; j--) {
if (rui1[i][j - 1] != 0 && rui1[i][j] != 0) {
rui1[i][j - 1] = rui1[i][j];
}
}
}
int[][] rui2 = new int[h][w];
/*
* Hについて累積和を作成
*/
for (int j = 0; j < w; j++) {
int cnt = 0;
/*
* 入力例1だと、以下みたいな感じ(縦並び)
* 011011
* 122120
* 233201
* 040312
*/
for (int i = 0; i < h; i++) {
if (wk[i][j] == '.') {
cnt++;
} else {
cnt = 0;
}
rui2[i][j] = cnt;
}
/*
* 累積した結果をならす(縦並び)
* 011011
* 122120
* 233201
* 040312
* を
* 043021
* 243320
* 243302
* 040312
* に変換
*/
for (int i = h - 1; i > 0; i--) {
if (rui2[i - 1][j] != 0 && rui2[i][j] != 0) {
rui2[i - 1][j] = rui2[i][j];
}
}
}
/*
* 累積してあるので全てなめる
* ただし、上下左右が重なっている中央部分を-1する
*/
long res = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
long cnt = rui1[i][j] + rui2[i][j] - 1;
res = Math.max(res, cnt);
}
}
out.println(res);
}