🙄

ABC209 C - Not Equalのメモ

2022/12/17に公開

AtCoder

競プロ

tech

バチャで取り組んだ問題です。（解けたとは言っていない）

考察

正直バチャ中にはまともな考察はできませんでした。Nが1なら答えは明らかにC1ですが、それが2つ、3つと増えていったらどうなるのだろうと思いましたが、Cの個数が増えることによって答えが減少する可能性もあることに気づいた辺りで思考が止まりました。

解説を読んで

まず、Cはソートしても組み合わせの数は変わらないということでした。そのため、昇順ソートすることで上記のようなCの個数が増えることで減るという計算上面倒なパターンをなくせますと…

それで、Cの個数が増えていくことで答えがどう変動していくのかという思考自体は正しくて、結果としては $C_i - i + 1$ を掛けていくことで求められるということでした。何も制約がなければただ $C_i$ を掛けていくだけだったと思いますが、制約が加わることでどうなるのかはわからず。
解説を読んでも、なぜそれでいいのかはよくわかっていません。ただ、解説にもある通り具体例を考えれば法則を見出すことはできていたかもしれません。自力計算は面倒なので愚直実装して、出力された答えをもとになんかそれっぽい法則を見出して…みたいな。
あまり正しい方法とは言えないのかもですが、過去実際にその手法で解いた問題もあったんですよね。今回もそれを試せばよかったのに試さなかったのは反省点です。

あとは計算途中で随時余りをとればいいです。

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val c = readLine()!!.split(" ").map { it.toInt() }.sorted()

    val mod = 1000000007

    var ans = 1L
    for(i in c.indices) {
        ans *= max(0, c[i] - i)
        ans %= mod
    }
    println(ans)
}

maxは $C_i - i + 1$ が負の数になった場合の対策です。
$C_i - i$ で計算していますが、$ + 1$が必要だったのは1-indexedだからということで、実装では0-indexedなので不要になります。

感想

反省点が多く感じられました。
まず、数列が来たらソートできないかを考えるというのは以前教訓として記憶していたはずなのですが完全に忘れていた点です。教訓が多すぎて正直全部は覚えてられないというのもありますが、これはかなり重要な教訓だと思っていたので忘れていたのはちょっとショックでした。再度認識したいです…

あとは上にも書きましたが、愚直実装により答えを出して法則を見出す手法を試さなかったこともそうですね。まあそれが本当に正しい方法かというと怪しいのかもしれないですが、現状数学的な考察をする能力がないため、そういう方法に頼るしかないです。数学的考察ができない現状をそのままにするつもりはないですが、この点は時間がかかります。
不正行為でなければどんな手段を使っても解ければ勝ちのはずだから多少アレでもなんとか解いてやるぞ、という気概を忘れていたのではと残念に思いました。

最近はぬるめのC問題とか、アルゴ式のような教育的問題などを解くことが多くて、こういう問題は久しぶりでした。やっぱり色々な問題を解かないとだめですね。

色々な問題を解くためには、いちいちこうやって記録していては時間がなくなるので、その分を他の問題を解くのに振り向けたほうがいいのではという気もしてきました。
そういう意見を見たのですが、自分でもそうかもという気が…時間をとられているのは間違いないので。

ただ、記録するのも重要っちゃ重要なので、どちらのほうが優先度が高いかという問題ですね。
もしくは、記録はするけどこういった文章ではなく箇条書きなど簡易的な記録にとどめて時間を節約するとか。
まあ、多くはないですが読んでくださっている方もいらっしゃるので、簡易的にしすぎるのも申し訳ない気がします。どのあたりがバランスがいいのか模索していきます。
（余談のほうが長くなった…）

考察

解説を読んで

感想

Discussion