' P '

whatever I will forget

計算量検討ロジック編

AtCoder

C問題がいつまでも解けないのは悲しいので特訓中!（B問題も怪しいときあるけど...）

問題達

atcoder.jp

atcoder.jp

atcoder.jp

基本的に、上記の問題達は時間量を検討しないとダメな問題達.

C - Takahashi's Information

これはもうそもそも問題を勘違いしてました, がそれは言い訳になりません.

f:id:mankozooyork:20200623222730p:plain

上記画像を見ると、x1は0でも1でもよく、一旦y1~3を全て求めたら、その後x1~3も求められることがわかります。
あとは、求めた仮のx/yを足した数が3*3のマスと同じになるかどうかを判定し、１つでも違えばNoになるってわけですね〜

下記はNGケース
f:id:mankozooyork:20200623222525p:plain

C - Half and Half

こういう最低値をもとめなさい系は基本下記アプローチの（掛け算で組み合わせる）でいいはずですが
本問題は実は制約にヒントが隠れているパターンでして、初パターンのため全く気づけませんでした...
あと、ABピザの価格を単純に*2するアイデアもでてこなかった... 必死にA=0.5, B=0.5として考えてました。

int tmp = 0;
int ans = Integer.MAX_VALUE;
for(int i=0; i<n; i++) {
  tmp = a*i + b*i + c*i
  if(ans > tmp) {
    ans = tmp;
  }
}

ABピザの個数と２倍した価格を使って、制約の100000まで数え上げると上記アプローチで解けるのですが、
ABピザを買った時点でX,Yを超えることがあるので、Math.max(0, X-ABピザの個数)として A/Bピザの価格を掛け合わせれば超過した場合の価格は0になるため、最適なアプローチになります。

C - Digits in Multiplication

これは素数判定や約数列挙のテクを覚えていれば余裕っぽいです
1 <= \sqrt{n} までループして、あとはいつものように桁数とるだけですから...
ただ、なんで\sqrt{n}まででいいんだっけ？ってお話。すっかり忘れてましたが、その数字の平方根を垣根として、あとは小さい数字で割り切れた片側がもう一度登場するからです。
そのため、\sqrt{n}までループしてn % i == 0になるのであれば、片方のbはb = n / aができるよいうことになります。
こういうテクを活用すること1010なんて数字がきても計算量を削減できるわけですね。
一度忘れたことは将来また忘れるだろうし、これから何回も見るだろう下記リンクを...

qiita.com

        long ans = Long.MAX_VALUE;
        for(long a=1; a*a<=n; a++) {
            if(n % a == 0) {
                long b = n / a;
                int digits = Math.max(String.valueOf(a).length(), String.valueOf(b).length());
                ans = Math.min(ans,digits);
            }
        }

C - Tsundoku

atcoder.jp

累積和を使って二分探索するか、累積和を使ってしゃくとり法を実施するかのやり方があるようです.
とりあえず解説にはしゃくとり法が紹介されていたので、それを理解する必要があります.
要は2つのループポインタを使って片方は初めから、もう一方は後ろから検査していき、後ろ側のポインタは対象となる判定まで後ろにずらしていくようなやり方だと今の所は認識しています.
肝となる実装部分は下記となります

        long[] ca = new long[n+1];
        for(int i=0; i<a.length; i++) ca[i+1] = ca[i] + a[i];

        long[] cb = new long[m+1];
        for(int i=0; i<b.length; i++) cb[i+1] = cb[i] + b[i];

        int cnt = 0;
        int j = m;
        for(int i=0; i<n+1; i++) {
            if(ca[i] > k) {
                break;
            }
            while(cb[j] > k-ca[i]) {
                j--;
            }
            cnt = Math.max(cnt, i+j);
        }
        System.out.println(cnt);

C - XYZ Triplets

本番中はfor(int i=1; i<=n; i++){//}をして、ループごとに答えを求めようとしてしまったためTLE....
方程式に当てはまる解はそれずなわちnなので、上記のループは不要.
また、例題を見る限りnを満たす数字の組み合わせは\sqrt{n}くらいで十分.
あとはn分のarrayを作成しておき、方程式を満たした解=indexとして++するだけ

        int[] ans = new int[n+1];
        for(int x=1; x<=(int)Math.sqrt(n); x++) {
            for(int y=1; y<=(int)Math.sqrt(n); y++) {
                for(int z=1; z<=(int)Math.sqrt(n); z++) {
                    int rst = x*x+y*y+z*z+x*y+y*z+z*x;
                    if(rst <= n) {
                        ans[rst]++;
                    }
                }
            }
        }
        for(int i=1; i<ans.length; i++) {
            System.out.println(ans[i]);
        }