yukicoder No.443 GCD of Permutation

嘘解法でコンテスト終了後に落ちました。
あとで書き直します。

何回か再提出したらACするクソ解法が出来上がりました。

精神が不安定になるので放置します。
記事を消すのは卑怯な気がしたので、
歴史として残しておきます。



No.443 GCD of Permutation - yukicoder

解法までの道のり

全然分からない。皆目見当もつかない。

仕方ないので「最大公約数 並び替え」でググる

すると以下の記事を発見。

blogs.yahoo.co.jp

ここでは、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の入力で落とせないだろうか。