競技プログラミング初心者のためのatCoder参加記録（Beginner Contest 336）

ABC336は、いつもの土曜日ではなく日曜日の２１時に開催されました。私は翌日の仕事に差し支えるのでやむなく不参加でした；；

問題文

2024年1月14日（日）21時に行われた ABC336 の C問題について解説します。

問題解説

良い整数：0, 2, 4, 6, 8 で構成された数値を昇順に並べ、小さい方から N番目の整数を返す問題です。

表にすると以下のようになります。例えば、N：12が入力された場合、12番目の値：42 が答えになります。

解答例

Nの制約が 10¹² なのでループで単純に処理すると 実行時間制限（LTE）に引っかかってしまいます。ですので、入力値 N と 出力値との間に何らかの関係性を見出す必要があります。

• 作成した表を眺めると、２ずつ増えて１０で２つ桁上がりしています。

  

• ここで閃くかどうかが分かれ道になるのですが、「良い整数」を２で割ってみます。 すると値が 5進数になっていることが解ります。

  

• 「良い整数」が０からスタートしているので、便宜上 Nもそれに合わせ N-1 にします。

  

• N-1は、10進数で 「良い整数/2」が 5進数の関係になっているので、10進数から 5進数へ変換すればOKなのです。

  

• 後は変換結果を 2倍にして元に戻し出力するだけです。

numpyを使用したプログラムの解説

numpyのbase_reprという 10進数から N進数へ変換するサブルーチンを使用した場合、コメント除けば４行でコーディングできます。

numpyモジュールについては、次のドキュメントを確認ください。 numpy base_reprサブ

#numpyモジュールインポート
import numpy as np

#入力値を取得
N=int(input())-1

#numpyのbase_reprサブを使用して10進数->5進数変換
n5=int(np.base_repr(N, 5))

#変換結果を2倍にして出力
print(n5*2)

変換処理を自作する場合のプログラムの解説

N=int(input())-1

#10進数->base進数へ変換するサブ
def base10int(value, base):
    if (int(value / base)):
        return base10int(int(value / base), base) + str(value % base)
    return str(value % base)

n5 = int(base10int(N, 5))
print(n5*2)

最後に

入力値と出力値の関係性が導き出せるか否かが運命の分かれ目になる問題でした。 次回は土曜日開催ですので、眠たい目を擦りながらも参加したいと思います。