目的
ABC413のD問題。
長さNの数列Aがインプットされるので、Aを並び替えて等比数列にすることができるのか判定する。
Aの要素は0ではない整数。
時間内にACできなかったのでメモ。
環境
Windows、pycharmでコード作成
pypyで提出
コード作成までの考え方
- 等比数列のパターンを考える。
- パターンごとの判定方法を考える
等比数列のパターンを考える
| 配列 | 公比 |
|---|---|
| 1, 2, 4 | 2 |
| -1, -2, -4 | 2 |
| 1, -2, 4 | -2 |
| 1, 1, 1 | 1 |
| 1, -1, 1 | -1 |
ここから分かること
- 数列を絶対値の昇順に並べれば、公比の絶対値は1以上になる
- 公比が1の時は、数列の値はすべて同じ
- 公比が-1の時は、数列は同じ絶対値の値をプラス、マイナスで交互に繰り返す
パターンごとの解法を考える
公比-1のとき
- インプットの絶対値がすべて同じ、かつ負の個数が要素数の半分であればYes
- 負の個数の判定は、要素数の偶奇により変えた
Nが偶数の時は負の個数がN//2であればYes。
Nが奇数の場合は負の個数がN//2もしくはN//2+1であればYes。
公比-1ではないとき
- インプットを絶対値の昇順に並びかえ、符号も分かるようにした配列Bを作成する
＜例＞
(Aの絶対値, プラスの場合0マイナスの場合1)の配列を作る
Aが[4,-2,1]の時、[(4,0),(2,1),(1,0)]を作り、並び替えると、B[(1,0),(2,1),(4,0)]となり絶対値順に並ぶ。
Bのi個目の要素の値は、B[i][0]*((-1)**B[i][1]) で復元できる。
- 配列Bの最初の2要素から公比※を求める
※公比は整数にならないことがあるので、Fraction関数（Bの1個目の要素の値,Bの0つ目の要素の値）で求める。
- 配列Bの要素がすべて「（i+1）番目の要素の値＝公比*i番目の要素の値」となっていればYes
最後に
与えられた例はパターンを網羅していない場合があるので、自分で色々振った簡単なインプット例を作って試してみる。
競技プログラミング面白い。