CodeChef June Challenge 2020 - Operations on a Tuple

• 問題
• AC

場合分けがかなりありそうだが、簡単なケースから考えていく。

• 0手で到達できるのは3対が最初から一致している場合
• 3手あればかならず到達できる
• 1手で到達できるのは次の5つの場合
  1. 2対が一致する
  2. 1対が一致して、残り2対の差が等しい
  3. 1対が一致して、残り2対の比が等しく、整数である
  4. 3対の差が等しい
  5. 3対の比が等しく、整数である

あとは2手と3手を区別する問題になるので、2手で到達できる $\Leftrightarrow$上の1-5のうちの少なくとも1つの状態に1手で到達できる、にしたがって考えればよい。とりあえず$p$に対する「意味のありそうな加算・乗算」を全部並べてみる:

• $p$に整数を足して$a$と等しくする ($a-p$を足す)
• $p$に整数を掛けて$a$と等しくする ($a/p$を掛ける)
• $p$に整数を足して、$a-p$と$b-q$を等しくする ($a+q-b-p$を足す)
• $p$に整数を掛けて、$a-p$と$b-q$を等しくする ($(a+q-b)/p$を掛ける)
• $p$に整数を足して、$a/p$と$b/q$を等しくする ($(aq-bp)/b$を足す)
• $p$に整数を掛けて、$a/p$と$b/q$を等しくする ($aq/bp$を掛ける)
• $p$と$q$に同じ整数を掛けて、$a-p$と$b-q$を等しくする　($(a-b)/(p-q)$を掛ける)
• $p$と$q$に同じ整数を足して、$a/p$と$b/q$を等しくする ($(bp - aq)/ (a - b)$を足す)

これらの8種類の加算・乗算を$p$には必ず適用するとして$q, r$に同じ操作を適用する/しないの4通りを調べ、それぞれの結果に対してあとで1手で到達できるかを上の基準で判定する。さらに、全体を$p, q, r$の順列6通りに対して調べる。

あとは、ゼロ除算が絡む場合の処理について検討する。「1手で到達できる場合」の3と5については場合分けするとして、後半の8種類の操作について考える。非ゼロ/0のように割り算が不能な場合については、その操作自体が不可能ということなので無視してよい。また、0/0が現れる場合は操作をせずとも目標とする状態が達成されているということなので、ほかの判定で拾われているはず……ということで、やはり無視してよい。