2020/2/25バチャ反省
バチャリンク
緑問題解けるようになろうと思って緑問題を4問選んでやってみました。
nabefutaとSatoooonくんと3人でやったんですけど、なんとびっくり三人とも30~35分で全完でした
思ったよりだいぶ解けてびっくりしましたね。ペナありならビリですけど
解説を書いていきます
1問目 互除法
考察A
フィボナッチ数列を使います。
なぜフィボナッチ数列がこれに使えるのかというと、問題文にあるコードの
int gcd(int a, int b) { if (b == 0) return a; counter++; return gcd(b, a%b);
の部分に理由があります。
以下では実装と同じ目線で話すために0-indexedを採用しています
フィボナッチ数列を数列Fと置いた際に、gcd(F_i, F_(i-1))
の挙動は以下のようになります。
F_(i-1)
が0の時:終了します。counter
の値は増えませんF_(i-1)
が1の時:gcd(1, 0)
が呼ばれます。counter
の値は1増えますF_(i-1)
が2以上の時:gcd(F_(i-1), F_(i-2))
が呼ばれます(これの証明は、F_i % F_(i-1)
がこの二つの差分(つまりF_(i-2)
)に等しくなるからです。フィボナッチ数列はその定義より一項前の倍を超える値になることがなく、この性質が使えます)。counter
の値は1増えます。- なお、
gcd(F_i, F_(i+1)) [i>1]
が呼ばれた際は、a, bが入れ替わってgcd(F_(i+1), F_i)
が呼ばれます。(この性質により二通りの答えが生まれます)
考察B(公式想定解)
さて、挙動3について考えていきます。
gcd(F_i, F_(i-1))
を呼んだとき、gcd(F_(i-1), F_(i-2))
が呼ばれるわけですが、これはi>2のどのiから始めてもgcd(F_2, F_1)
であるgcd(2, 1)
になります。
ここで、
gcd(2, 1)
はcounter
を1増やし関数を終了させるgcd(F_i, F_(i-1))
がgcd(F_2, F_1)
にたどり着くまでにcounter
はi-2増える
の二点より、gcd(F_i, F_(i-1)) [i>2]
が終了した時点で、counter
はi-1であることがわかります。
よって、counter
をKにするには
gcd(F_(K+1), F_K)
を呼べばいいことがわかります。
即ち、
a=F_(K+1), b = F_K
です。
考察C(別解)
挙動4を使うともう一つの解が見つかります。それは
a = F_(K-1), b = F_K
なのですが、これは挙動4より最初にa, bの反転が起こりcounter
が増加、そこから考察Bの通りK-1増加するので全体でK増加する、ということです。
これだとK=1の時に考察Bのi>2(i-1>1)を破りますが、挙動2よりbが1の時はaに依存せず1回で終わるので、問題ありません。
実装(考察Cを採用)
fib = [1, 1] for i in range(50): fib.append(fib[-1]+fib[-2]) K = int(input()) print(fib[K-1], fib[K])
2問目 Insertion
考察
まず、辞書順で小さいということがどうかを考えます。(
と)
では(
のほうが小さいので、(
ができるだけ先に、)
ができるだけ後に来るようにすればよいです。
これはまぁ簡単で、以下の流れで最適解が出ます。
- Sを左から見ていく
(
があったら変数rに1足す)
があったら、- rが1以上の場合:rを一つ減らす(括弧の対応付け)
- rが0の場合:先頭に
(
を追加(括弧の対応を無理やり生やす)
- さいごにrの数だけ
)
を配列の最後に追加
するだけです。これで括弧の対応を守ったまま(
を最初に、)
を最後に持っていくことができました。
実装
N = int(input()) S = list(input()) stack = [] ans = S[::1] r = 0 for c in S: if c == "(": r += 1 if c == ")": if r > 0: r -= 1 else: ans.insert(0, "(") for _ in range(r): ans.append(")") print("".join(ans))
3問目 引越しできるかな?
考察
今城くんが注文しなければならないダンボールの容積の最小値はいくらでしょうか
という部分から、最適な選択したときに必要となる箱の体積を求めればいいことがわかります。
これは各箱を最適に重ね合わせるときの各軸(x, y, z)の最大値の積であることがわかります(イメージをすると自明だと思います)
では、「最適に重ね合わせる」がどういうことかを考えていきます。
これは、「ソートしてから各軸に対応させたindexに応じて値を更新していく」という風に表せます。具体的には、
- x軸に1番目に大きいものを
- y軸に2番目に大きいものを
- z軸に3番目に大きいものを
という風にしていくことです。何故これが最適かというと、数式での証明が浮かびません。どうしましょう
良いたとえを思いつきました。
例えば箱の中にたくさんの積み木があるとして、それらすべてを十分な時間揺らした場合、それらは最初の乱雑な状態より小さい体積に収まっています。
それと同じで、今回の場合はx > y > zの順に安定するようにする、と考えます。
実装
C = int(input()) a, b, c = 0, 0, 0 for _ in range(C): N, M, L = sorted(list(map(int, input().split()))) a = max(a, N) b = max(b, M) c = max(c, L) print(a*b*c)
4問目Digits in Multiplication
考察
2つの正の整数の組(A, B)がN=A*Bを満たすように動くとき
回りくどい言い方をされていますが、これはつまりNの約数A, Bのペアということです。
つまり、Nの約数のペア全通りについて関数Fを計算し、最小値を出力すればよいです。
Nの約数のペアを求める
一瞬O(N)に見えますが、約数のペアは約数i
についてN//i
でだせるので、sqrt(N)まで探索すればよく、O(sqrt(N))になります。
今回はN = 1010までなので、最悪で105回となり間に合います。
10進数の数の桁を求める
ある10進数の整数Xについて、その桁数はint(log10(X))+1
で求めることができます。
よって関数Fの実装は以下のようになります
def F(A, B): return max(int(log10(A))+1, int(log10(B))+1)
あとは用意したペアすべてについて計算をしながら最小値を更新していけばよいです。
実装
def make_divisors(n): divisors = [] for i in range(1, int(n**0.5) + 1): if n % i == 0: divisors.append((i, n//i)) divisors.sort() return divisors from math import log10 N = int(input()) div = make_divisors(N) def F(A, B): return max(int(log10(A))+1, int(log10(B))+1) ans = 10**9 for a, b in div: ans = min(ans, F(a, b)) print(ans)
終わりに
疲れた~~~!!!今日のバチャは全体的に爆速でとても楽しかったです!今回の解説で一番楽しかったのは1問目の「フィボナッチ数列を使える理由」のところですね、自分で気づいて天才かと思った!!!