【Python】初心者でも分かるように「名刺バインダー管理 (paizaランク B 相当)」を解説してみた

問題文

解説

標準入力

本問題の入力される値は次の形式で与えられます。

n m

入力の受け取り方については過去に次のような記事を書いているので参考にしてみてください。

この記事によると map(int, input().split()) で受け取れば良いことがわかるので、

# 標準入力
n, m = map(int, input().split())

となりますね。

アルゴリズム

次のような表を考えてみましょう。ただし、 $n = 3$ とします。

【$1$ 枚目のファイル】

$1$	$2$	$3$
$6$	$5$	$4$

【$2$ 枚目のファイル】

$7$	$8$	$9$
$12$	$11$	$10$

$\qquad\quad\ \vdots$

$1$ 枚目のファイルを例に表の見方について説明します。

$1$	$\color{red}2$	$3$
$6$	$\color{#1e90ff}5$	$4$

$m = 2$ のとき、この要素を含む列に着目すると、

$\color{red}2$
$\color{#1e90ff}5$

となりますね。このとき $\color{red}2$ でない方、すなわち $\color{#1e90ff}5$ が $m = \color{red}2$ のときの答えになります。同様に $m = \color{#1e90ff}5$ のときにも同じような表が得られるので、 $\color{red}2$ が $m = \color{#1e90ff}5$ のときの答えになります。

つまり、この表の列は、その名刺の裏側にある名刺の番号を表していることがわかるかと思います。そこで、まずは $1$ 枚目のファイルを作ってみましょう。

$n = 3$ のときは

$1$	$2$	$3$
$6$	$5$	$4$

であったので、一般化すると次のようになります。

$1$	$2$	$\dots$	$n$
$2n$	$2n - 1$	$\dots$	$n + 1$

$1$ 行目と $2$ 行目をそれぞれ max_card_n 、 max_card_2n という名前のリストで作成するとこのようになります。

# アルゴリズム
# 1, 2, ..., n
max_card_n = [i for i in range(1, n + 1)]
# 2n, 2n - 1, ..., n + 1
max_card_2n = [i for i in range(n + 1, 2 * n + 1)][::-1]

最終行で [::-1] を用いていますが、これを使うとリストの要素を逆順にできます。

arr = [1, 2, 3]
print(*arr)       # 1 2 3 と出力される
print(*arr[::-1]) # 3 2 1 と出力される

もし、この表の中に探している要素がない場合は $2, 3, \dots$ 枚目とファイルをめくっていけば良いですね。

現在の表の中で最も大きい要素は $2n$ であり、 max_card_2n[0] でその値を確認することができます。$m$ が $2n$ より大きいならば、その間はファイルをめくる必要があるのでこれをループで処理します。

ファイルをめくる処理を考えるために $n = 3$ のときに、ファイルをめくるときの数値の増減を観察してみましょう。

【$1$ 枚目のファイル】

$1$	$2$	$3$
$6$	$5$	$4$

【$2$ 枚目のファイル】

$7$	$8$	$9$
$12$	$11$	$10$

ここで、 $2$ 枚目のファイルを次のように変えてみます

$1 + 6$	$2 + 6$	$3 + 6$
$6 + 6$	$5 + 6$	$4 + 6$

$n = 3$ なので、 $6 = 2 \times 3 = 2n$ が成り立ち、

$1 + 2n$	$2 + 2n$	$3 + 2n$
$6 + 2n$	$5 + 2n$	$4 + 2n$

となるので、ファイルをめくる前の表の各要素に $2n$ を足すことはファイルをめくることに等しいことがわかります（一般の場合における証明は省略しますが成り立ちます）。

したがって、ファイルをめくる処理は次のように書けます。

# m 番目の名刺が見つかるまでファイルをめくる
while m > max_card_2n[0]:
    for i in range(n):
        max_card_n[i] += 2 * n  # 2n を足す
        max_card_2n[i] += 2 * n # 2n を足す

この処理によって探している要素 $m$ が見つかるまでファイルをめくったので、 $2$ つのリスト max_card_n 、 max_card_2n のうちいずれかにその要素がありますね。

$1$ 行目の表が max_card_n に、 $2$ 行目の表が max_card_2n に対応しているので、まずは $1$ 行目の表にその要素がないかチェックし、そうでないときは $2$ 行目の表をチェックします。

$1$ 行目の表にその要素があるかどうかは max_card_n の末尾の要素 max_card_n[-1] が最大の要素なので、これが $m \le$ max_card_n[-1] であるかどうかを見れば良いですね。

もし max_card_n の中にあった場合は、左から何番目にあるかを求め、その番地で max_card_2n の同一番地にアクセスすれば表の同じ列で見ていることになり、答えが求められます。　max_card_2n の中にあった場合にも同様にして求められますね。

if m <= max_card_n[-1]:
    # 表の上側（1行目）に m 番目の名刺がある場合
    idx = max_card_n.index(m)
    ans = max_card_2n[idx]
    print(ans)
else:
    # 表の下側（2行目）に m 番目の名刺がある場合
    idx = max_card_2n.index(m)
    ans = max_card_n[idx]
    print(ans)

上記コードにある arr.index(x) はリスト arr の左から何番目に要素 x があるかを返します（$1$ 番目ではなく、 $0$ 番目から始まることに注意）。

arr = [1, 2, 3, 1]
print(arr.index(1)) # 0 複数個ある場合は最も左にあるものが選ばれる
print(arr.index(3)) # 2
print(arr.index(5)) # ValueError

提出コード（Python）

# 標準入力
n, m = map(int, input().split())

# アルゴリズム
# 1, 2, ..., n
max_card_n = [i for i in range(1, n + 1)]
# 2n, 2n - 1, ..., n + 1
max_card_2n = [i for i in range(n + 1, 2 * n + 1)][::-1]

# m 番目の名刺が見つかるまでファイルをめくる
while m > max_card_2n[0]:
    for i in range(n):
        max_card_n[i] += 2 * n  # 2n を足す
        max_card_2n[i] += 2 * n # 2n を足す

if m <= max_card_n[-1]:
    # 表の上側（1行目）に m 番目の名刺がある場合
    idx = max_card_n.index(m)
    ans = max_card_2n[idx]
    print(ans)
else:
    # 表の下側（2行目）に m 番目の名刺がある場合
    idx = max_card_2n.index(m)
    ans = max_card_n[idx]
    print(ans)