DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選-D(500)
概要
数字を与えられる。数字の隣接する二つの桁の数をそれぞれ、a, bとして、次の操作を行う。
- aとbの2ケタをa+bで置き換える。
この操作を1回行うと、2751では例えば、951, 2121, 276のようになる。
順番を工夫して操作をするとき、与えられた数字からでは最大何回この操作ができるか？
ACするまで
1. 手元で実験してみる。すると、何パターンも手順入れ替えても手数は同じ。
2. 手数が同じなら手順関係ないのでは？と思い証明を考える。
3. 証明を思いつかない。風邪からか考える気力がなくなった。
4. いや考察続けろや。(もう一歩)
5. 簡単に変化を追跡できる量に着目する。二つの桁をそれの和で置き換えるとき、繰り上がるパターンと繰り下がらないパターンがある。それぞれのパターンについて、考えてみる。
6. 2つのパターンで少し詰めてみると証明のひな型が出来上がる。
7. AC
考察
手順は実はどうでもいいのではないか？という点からしても、こういう証明を考えるときは、不変量を含むに簡単に変化を追跡できる量に着目するのでうまくいくパターンがある。
今回の場合では、それはすべての桁の和に相当する。
- 繰り上がりがない場合(23 ->5のパターン)、桁が一つ減りすべての桁の和は減少しない。 (パターンAと呼ぶ)
- 繰り下がりがある場合(58->13のパターン)、桁は減らず、ちょうどすべての桁の和が9減る。 (パターンBと呼ぶ)
この二つの事実から考えてみる。
操作が終わるとき、すべての桁の和は9以下でないといけない。パターンAは和に影響しないので、パターンBの回数がおのずと定まる。パターンBの回数は、桁の総和をSとすると、 (S - 1)/9回となる。(9以下になるまでに必要な操作回数。)
一方、パターンAについては、桁の総和には影響しないが、数字の桁があきらかに一つ減る。よって、パターンAの可能回数は、(桁数の総和) - 1 となる。
この二つを纏めと、
(S - 1)/9 + (桁数の総和) - 1
これが答えとなる。以上の議論からも、操作手順はこの値に影響しないとわかる。このように、いくつかの簡単に変化を追跡できる量があり、それぞれが独立に変化したりするような今回のパターン(パターンAは桁数にしか影響しないし、パターンBは桁の和にしか影響しない)は、このように証明が生えてきやすい。
ACソースコード：
Submission #8588975 - DISCO Presents Discovery Channel Code Contest 2020 Qual
一言
風邪を言い訳に考察をやめるなや。個人コンテストなら無証明貪欲を日和るなや(いや臨機応変に考えろ)
