嘘解法でコンテスト終了後に落ちました。
あとで書き直します。
何回か再提出したらACするクソ解法が出来上がりました。
精神が不安定になるので放置します。
記事を消すのは卑怯な気がしたので、
歴史として残しておきます。
No.443 GCD of Permutation - yukicoder
解法までの道のり
全然分からない。皆目見当もつかない。
仕方ないので「最大公約数 並び替え」でググる。
すると以下の記事を発見。
ここでは、A>B>C とします。g を使うと
ABC=gt、ACB=gu、
CAB=gv、CBA=gw となり、
ABC-ACB=g(t-u)
CAB-CBA=g(v-w) --------------------------(1)
(ABC=100A+10B+C という書き方です。)
※ g は、ABC,ACB,BAC,BCA,CAB,CBA
という6つの3桁の整数の最大公約数なので、
t,u,v,w,は4つ全部が、言い換えると、どの2つをとっても
互いに素とは限りませんが、
(t-u)と(v-w)は互いに素だと思います。
でないと、g が変わってしまうと思います。
こんなおいしい性質があるらしい。
これは互いに異なって0を含まない数じゃないとダメ?
何はともあれ理解せずに引用するのはよくなかった。
解法
先のblogをもとに3つのバラバラな適当な数を生成して、
ソートし、差分を取る。
その差分をgcdしたやつが答え
になるはずが、そんなうまくいかなかった。
例外処理として、
- 0を含む可能性があるので、一番小さい数ともgcdを取る
- n の桁数が2 のときは3つ作れないので愚直にやる
- 全部同じ数のときは、入力をそのまま返す
- 一番大きい数ともgcdを取っておこう
何回か提出するとACできた
http://yukicoder.me/submissions/129926
http://yukicoder.me/submissions/130064
http://yukicoder.me/submissions/130089できる回数まで乱択
乱択って123456789000000....000の入力で落とせないだろうか。