AtCoder ABC 032 A&B&C
A問題
- aとbの最小公倍数を求める
- n以上で、nに一番近い最小公倍数を求める
- nを最小公倍数で割って切り上げる
- 最小公倍数×求めた値
private void solveA() {
int a = nextInt();
int b = nextInt();
int numN = nextInt();
int baisu = koubaiA(a, b);
/*
* int res = (int) (baisu * Math.ceil(numN / baisu));
*/
int res = baisu * ((numN + baisu - 1) / baisu);
out.println(res);
}
private int koubaiA(int a, int b) {
return a * b / kouyakuA(a, b);
}
private int kouyakuA(int a, int b) {
int max = Integer.max(a, b);
int min = Integer.min(a, b);
int amari = max % min;
while (amari != 0) {
max = min;
min = amari;
amari = max % min;
}
return min;
}
A問題：別解
- これでも通った
- n以上の数で、aでもbでも割り切れるものを1個ずつ試す
private void solveA2() {
int a = nextInt();
int b = nextInt();
int numN = nextInt();
while (true) {
if (numN % a == 0 && numN % b == 0) {
out.println(numN);
return;
}
numN++;
}
}
B問題
- kのサイズの文字列を全部切り出す
- setに入れて重複を除外する
private void solveB() {
String s = next();
int k = nextInt();
Set<String> wk = new HashSet<String>();
for (int i = 0; i <= s.length() - k; i++) {
String moji = s.substring(i, i + k);
wk.add(moji);
}
out.println(wk.size());
}
C問題
-
これもしゃくとり法で
- むしろ、しゃくとり法以外の解き方がわからん
-
数列の中に0が入っていた場合、全体が0になるので最初に判定してそれは除外している
- しゃくとり法の途中で0が出現したときの除外を書くよりは、最初に排除したほうが楽だったので
private void solveC() {
int n = nextInt();
int k = nextInt();
int[] wk = IntStream.range(0, n).map(i -> nextInt()).toArray();
for (int i = 0; i < wk.length; i++) {
if (wk[i] == 0) {
out.println(n);
return;
}
}
int right = 0;
int left = 0;
long innerResult = 1;
long res = 0;
while (left < n) {
/*
* 右を進める
*/
while (right < n && innerResult * wk[right] <= k) {
/*
* 右の数値を一つずつかける
*/
innerResult *= wk[right];
/*
* 数値をつくったら一つ進める
*/
right++;
}
/*
* どれだけながくできたのか？
*/
res = Long.max(res, right - left);
/*
* 右を進める?
*/
if (left == right) {
right++;
} else if (innerResult >= wk[left]) {
/*
* 左の数値を除去
*/
innerResult /= wk[left];
}
left++;
}
out.println(res);
}