2022-05-12 三井住友信託銀行プログラミングコンテスト2019 の A, B, C, D, E を解いた / java.util.stream.Stream の limit
三井住友信託銀行プログラミングコンテスト2019 の A, B, C, D, E を解いた。
- A - November 30
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_a
- 提出: https://atcoder.jp/contests/sumitrust2019/submissions/31619092
- D_2 (翌日) が 1 なら月末
- 公式解説の解法 3 だった
- B - Tax Rate
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_b
- 提出: https://atcoder.jp/contests/sumitrust2019/submissions/31619143
N <= 5 * 10^4と小さいのでXを 1 から順に全探索したX * 108 / 100(/は切り捨て) でNに一致するなら出力して終了する- 公式解説の解法 1 だった
- C - 100 to 105
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_c
- 提出: https://atcoder.jp/contests/sumitrust2019/submissions/31619250
X <= 10^5かつ商品は各10^6個あることから各商品の使える個数は気にしなくて良い100を好きなだけ使えるので100円未満の端数がなければ買い方が存在する100円未満の端数を101〜105円の端数部分でつくれるかどうか- そのときの
100円以上の部分が端数部分をつくるのに必要な枚数を超えているかどうか 99円までをつくるので105円で20枚あれば十分101〜105の 5 重ループを0..=20で回す20^5 = 3200000なので間に合う- 公式解説の解法 2 の派生だった
- D - Lucky PIN
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d
- 提出: https://atcoder.jp/contests/sumitrust2019/submissions/31619546
- 答えは
000から999の 1000 通りしかない N <= 3 * 10^4に対して1000通りなので10^7- すでにできている桁からの遷移でも間に合うと判断した
- ……が 2 TLE
- おそらく
0..と00.のケースを入れたりlogがついたりすると間に合わないのだと思う - 遷移はその文字を 1 桁目に使う 2 桁目に使う 3 桁目に使うの 3 通り
- 2 桁目・ 3 桁目はすでにできている 1 桁目・ 2 桁目から伸ばす形にする
- 公式解説の解法にはなさそう (遅い言語だと厳しそう)
- E - Colorful Hats 2
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e
- 提出: https://atcoder.jp/contests/sumitrust2019/submissions/31619846
- 最初に樹形図を書いてみた R, G, B, RR, RG, RB, ...
- 書いてみて A_i から数を数えていないといけないことと基本的な遷移が見えた
- R, G, B の具体的な値ではなく
(0, 0, 0)のようにある個数のものが何個あるかで良さそう - A_i と同じ個数の数だけ遷移があるので現在の値をそれだけ掛ける
- あとは A_i と同じ個数のところをどこか 1 インクリメントする
- 例
- 初期値を
ans = 1にしてA_1 = 0でcount = (0, 0, 0)なら0が3個あるので1 * 3してcount = (1, 0, 0)にする ans = 3A_1 = 1count = (1, 0, 0)なら1は1個なので3 * 1してcount = (2, 0, 0)にする
- 初期値を
- F - Interval Running
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_f
- 問題さえ読まず
Java の java.util.stream.Stream に takeWhile(Predicate) はあるが take(long) はない。代わりに limit(long) がある。
package com.example;
import org.junit.jupiter.api.Test;
import java.util.stream.Stream;
import static org.assertj.core.api.Assertions.assertThat;
class LimitTest {
@Test
void test() {
assertThat(Stream.of(1, 2, 3, 4).limit(2).toList())
.isEqualTo(Stream.of(1, 2).toList());
}
}
今日のコミット。