2020年 5月32日

まえがき

コンテストのオーバーフローの問題にムカついたので今日は5月32日です。 5月32日のぶんの記事を公開します。

投稿した後気づいたから付け足すけど、$なんか式$でいい感じにしてくれないのかえー

健康管理

何した

コンテストに出た

具体的に

今日解いた問題

ABC169-B Multiplication 2

[いじめ,オーバーフロー]
…… 1e18を超えた時の判定がむずいので a[0] * a[1] * ... をnowっていう変数にとりあえず入れておく。
$$now * a[i] > 1e18$$ ってことは $ now > 1e18 / a[i] $(式変形)かぁ、って思ってそうしたら行けた。

オーバーフロー嫌い

ABC169-C Multiplication 3

[いじめ,オーバーフロー,小数]
なんか、よくわからないけどbを受け取って (B をDOUBLEで受け取る)$ a * b $ を出力するだけだとエラーになるな ↓ $ a * (b * 100) / 100 $ これでもエラー（は？？？） b * 100 で壊れるらしい（ふざけるな)

仕方ないのでx.yzで与えられるbを string で受け取りました。
その後 100x + 10y + z としてint型のbを作成して、　$ a * b $ を出力して勝ちました（わけわからん。ふざけるなよ。俺は競プロerであってプログラマーじゃねえぞ。)

[素因数]
$ z = p^e $ っていうのがミソじゃね。知らんけど。なんかまぁ、$N = 2 ^ 4 * 3 ^ 2 ( = 144) $ みたいな時, zは2,4,3,の3つが行けて（答えは３) Nは最終的には6 になってるんだけど、この時Nの素因数は2と3、1個ずつ使って6で割る！！！みたいなことは出来ない。
だからまぁ、$ N = a ^ x * b ^ y * c ^ z $みたいな形してるとき、xを1+2+3+...+kって感じで分割するのが良くて…みたいな感じでやってったら行けた。

でまぁ、a っていうのはvector<pair<int,int>> で、.firstに素因数, .secondにその素因数が何個あるかが格納サれてるから…こんな感じでやって…
( N <= 10 ^ 12), 10¹²って2⁴⁰ぐらいだから 1 + 2 + 3 + 4 + ... + k>= x ってなるkを見つけるループは全然重くない
なんかまぁ、ノリで伝われよ（投げやり)

for(auto x:a) {
        // xはpair型
        ll now = 0 ;
        for(int i = 1; i <= 50; i++){
            if (x.second >= now + i){
                ans ++;
                now += i;
            } else {
                break;
            }
        }
    }

ABC169-E Count Median

[中央値,最大化,最小化]
残り2分ぐらいで通せました（やったね）

なんかまぁ、さ、とりあえず考えることは中央値として採用される値の範囲を求めろってことジャン（じゃん？)
で、値の数が偶数のときは、 x[n/2] x[n/2 + 1]の2つの値の平均が中央値じゃん…
だから、一回N=奇数の時を片付けよう。 N=奇数のとき
求めるのはx[n/2 + 1]の範囲

で、なんかよくわからないけどx[n/2 + 1]の最小はAをソート（小さい順)したときのA[n/2 + 1]で、最大はBをソートしたときのB[n/2+1]だった。
（もうなんか、なんでか知らないけどそうなったから良いや）

N = 偶数のとき
x[n/2]とx[n/2+1]の最小最大をそれぞれ求める（どうして俺が求められたのかはよくわからない)
でまぁ、 x[n/2]のmin,maxがそれぞれa, b
x[n/2+1]のmin,maxがそれぞれc,d とするじゃん（どうやって求めるのかは知らんけど), {3,5}の中央値って4じゃん
{1,7}の中央値も4じゃん。
これをどうやって同一視させてやるか迷うじゃん。
でまあ、天才にぼしは考えたんだよ。 ,a+c がx[n/2] + x[n/2+1]の最小で b + d がx[n/2] + x[n/2 + 1]の最大じゃん（ﾎｹﾞｰwｗｗ)つまり、a+c からb+d が中央値の2倍が取りうる値の範囲なんだよね　笑

ま、分かったふりして何も分かってないんだけどね。

あとがき

また月曜日がやってきたよ。誰も望んでないのに。

まぁ俺は望んでるんだけどね。

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)

草体にぼ日記

だらだらと

2020年5月32日　日記