2020年 8月 21日

まえがき

はいどうも。皆様、夏休みも残すところ残り僅か(40日ぐらい）となりましたが、いかがお過ごしでしょうか。
お宅にはイカがお過ごしでしょうが、我が家にはおらぬでござる。
さてさて、本日皆様にお集まり頂いたのは、大事な報告があるからですか？
いいえ

健康管理

健康と申します。

何した

ふふふｗｗｗ

具体的に

最近は絵日記描いてました。
見たい人は俺のTwitterのメディア欄を漁るか、ハッシュタグ夏休みのえにっきで検索かければ見れるよけんさくけっかｗｗｗｗ
ねこねこねこねこ

今日解いた問題

うーちゃん。

ABC175 C-Walking Takahashi

[オーバーフロー,k回操作] この問題のダメな解法について少しかこ〜っと

K回(Kが10⁹を超える)操作の問題です。実行時間が間に合わないからK回実際に操作させることは出来ないよ〜って問題ですね。
コンテスト中は1発ACしたんですけど、さっきやったらWAを生やしたので何がダメなのか考えてました。ちなみにWAコードです。

int main()
{
    ll x, k, d;
    cin >> x >> k >> d;
    x = abs(x);

    // k回移動して、原点をまたぐことが出来るか
    if(x - k*d < 0){
        // またぐ時
        ll kai = x / d;
        k -= kai;
        x -= kai * d;
        if(k % 2 == 0){
            cout << x << endl;
        } else {
            cout << abs(x-d) << endl;
        }
    } else {
        // またがないとき
        cout << x - k * d << endl;
    }
}

最初の条件分岐は、 - K回同じ操作をしたら座標0を通りすぎることが出来るか - K回同じ操作をしても座標0を通りすぎることが出来ないか
この2つで分岐させました。
後者の時は、座標0に向かってずっと近付こうと操作するのが最善で

else {
    cout << x - k * d << endl;
}

で終わりです。
前者の時は、まず座標0に近づけるだけ近づきます。
この時の移動回数を kai って名付けてます。で、後k - kai 回移動しなきゃ行けない。
れが偶数回なら、右に動いて左に動いて…っていうのを繰り返すことで、kai 回移動した座標が最後の座標にできる。
奇数回なら右に動いて左に動いて…を繰り返して、最終的には右（まぁ右か左かは知らんが）に移動して操作を終えることになります。

これが最善っていうのは別に今回話したいことじゃなくて、なんでこのコードがダメなのかってことが話したいことです。

if(x - k * d < 0)

こいつが犯罪者。
k == 10 ^ 15,
d == 10 ^ 15
このとき、k * d = 10 ^ 30
2¹⁰が10³ぐらいなので,10³⁰は2¹⁰⁰ぐらい…long long じゃ足りませーん。
はい、終わり。

よってこの問題をとくことが出来る解法は、座標0を通り過ぎることが出来るかの条件を抜きにして、 座標0を超えない程度にとりあえず座標0に向かって進むっていうのをやるとover flowを気にせずに解けます。で、座標0を超えない程度に進むって、それ何回やねん！っていうのが x / d　回です。
x / d は、やべえときでも10¹⁵(2の50乗くらい)(x == 10¹⁵, d == 1)で、d * (x / d)をしても10¹⁵なのでlong long で扱える！嬉しいね！
ってノリでとけちゃんまん。

ってノリでとけちゃんまん。

あとがき

D問題解く気起きねえ

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

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

草体にぼ日記

だらだらと

2020年8月21日　日記