🎉

ABC255 C - ±1 Operation 1のメモ

2022/11/18に公開

AtCoder

競プロ

tech

目についたC問題を解いてみようとしたけど解けなかったシリーズです。

ABC255自体は参加していましたが、Bも解けずに終わったのでこの問題は初見です。

考察

操作は±1なので、操作回数とは最も近い「良い数」との差ですね。なので最も近い「良い数」を見つける問題と解釈しました。
数列自体は与えられず、数列を探索するとしたら自分で生成しないといけませんが、制約が大きいので生成途中でTLEになりそうです。

おそらく計算で求めることになります。まずは単純なケースで考えてみます。Aが0、XとDが正の数です。
この場合、XをDで割った余りとかがそれっぽい気がします。たとえばXが37でDが3とかだとすると、最も近い「良い数」は36で答えは1、37を3で割った余りは1なのでそれっぽいです。
ただ、これだけだとダメそうでした。たとえばXが35だとすると、37の場合と同じく最も近い「良い数」は36で答えは1ですが、余りをとると2となり答えと違います。これはどうやって解決すればいいのか、結局わかりませんでした。

また、上記は単純なケースです。実際にはAは0じゃないかもしれないし、XやDが負の値かもしれない。なんかいい感じに補正する方法はあるのだろうなあと思ったのですが、実際にどうやって補正すればいいのかまではわからず。

あとは、補正するとしてそのために足し引きするとしたら、それによって数列をはみ出すようなことはあるのだろうか、あったらどう考えればいいのか、などと考えだすとわけがわからなくなりました。

つまりこの問題は私には解けませんｗ

XがA未満の場合はAとの差が答え、またはXが数列の最大値を超える場合はその最大値の差が答え（最大値は $A + (N - 1) * D$ ）とかの例外的なケースについてはわかったのですが、メインのケースについてはわからず。

ある意味ソート済の数列だから二分探索？とか思ったりもしましたが、どう使えばいいのかは全然わからず。

解説を見て

とりあえず解説を見て書いたコードを貼ります。

import kotlin.math.min

fun main() {
    var (x, a, d, n) = readLine()!!.split(" ").map { it.toLong() }

    var first = a
    var last = a + d * (n-1)
    // 公差が負の数だった場合は正の数に補正
    if(d < 0) {
        val (tmpLast, tmpFirst) = listOf(first, last)
        first = tmpFirst
        last = tmpLast

        d *= -1
    }

    // 初項を0に補正
    last -= first
    x -= first
    //first = 0

    if(x <= 0) {
        println(-x)
    } else if(x >= last) {
        println(x - last)
    } else {
        println(min(x % d, d - x % d))
    }
}

やはり、補正できるようでした。というか、補正するのはそれだけでいいんですね。Xが負の数だったらどうするのか、とかも考えていたのですが…

それと、負の数は反転させたいとは思っていたのですが、初項を補正できるとはなぜか思いつきませんでした。数列の全要素は、初項が0とすると公差の倍数になる、実際にはそれぞれの要素に初項を足した数になる、とは気づいたんですが、なぜそれを補正しようという発想にならなかったのか。

補正さえすれば、あとはかなりシンプルな場合分けだけでいいんですね。上で書いたXがA未満のケース（実際には以下…）、Xが数列の最大値を超えるケース（実際には以上…）、あとはXが数列の最小値と最大値の間にあるメインのケースだけ。
メインのケースは、やはり余りで求められると。わからなかったケースは、余りがDから引けばいいと。

なにげに、等差数列なので最小値と最大値さえあれば数列を表現できる、というのもポイントなんですね。実際に数列を作ることはできなくても、そこさえ押さえればいいと。うーん、これも気づけなかった。

感想

まあ、これでは自分は全然ダメという感想にしかならないですね…ｗ
完全に数学力の敗北です。数学力が課題というのは何度も何度も痛感しているので、一から勉強し直してはいます。ただ、時間がかかります。気長にやっていくしかないですね。

数学力がネックという現実を何度も突きつけられるけど、すぐには解消できないというのはなかなか辛いものがありますね。しかし、数学力の必要性を何度も痛感するというのは良いことでもあります。これにより、数学の勉強のモチベが上がる（少なくとも下がらない）からです。いろいろやることはあるので、必要性がわからなくなった勉強などすぐにやめてしまいます。数学に関しては必要性を何度も痛感させられるので、やめてしまう心配をほぼ考えなくて済んでいます。
（まあ競プロをやめてしまったら数学の必要性を感じるシーンもなくなるので、数学もやめてしまうでしょうけど…）

そういう意味だと、精神的にはキツイですが、この問題に出会えてよかったです。

あと反省すべき点としては、場合分けですかね。個別の条件を導き出せなかったというのもありますが、そもそも思考方法自体に問題があったといいますか。
場合分けをいろいろ考えないといけない場合、そもそも補正をして場合分け自体を減らすとか、愚直に場合分けするとしても、落ち着いて一つ一つ片付けていくように考えればよかったのですが、一気に複数のことを思い浮かべてしまってパニックになったという面があります。
こうなると、もうやだわかんない、という感情に支配されて投げ出すみたいになってしまいます。（なりました）

まあこの問題の場合は愚直に場合分けするときつすぎるので無理だったでしょうし、補正したいとは思ってもどう補正すればよかったのか自力で理解できたとは思えないので、やはり全然手に負える問題ではなかったということになってしまうのか…

とはいえやっぱり初項の補正について考えられなかったのは、現状を鑑みたとしても失点ですね。反省点として記録しておきます。

こういう問題を普通に解けるようになる日は来るのかなあ。道は険しいですｗ

考察

解説を見て

感想

Discussion