【paiza問題集 解説】
paizaの森練習問題コンテスト過去問題セット3

s = input()
print(s[::-1])

これが最も簡単な文字列の逆順方法です。文字列変数に [::-1] を添えるだけです。リストならともかく、文字列の逆順をこれ以外の方法で実現しようとすると面倒が多いです。

気後れせずに、この方法一択で使いまくってしまいましょう！😉

s1, s2 = input().split()
print(s1 + s2)

s = input()
print(s.replace(' ', ''))

例１は、 s1 と s2 を文字列として分割で受け取り、それを + で繋ぎ直して画面に出力しています。

例２は、入力を１つの文字列として受け取ったものを .replace() メソッドを使って、空白の部分を '' に置き換えて空白部分を削除するという処理をしています。

.replace() メソッドの使い方は「２章 文字列の操作を使いこなす機能一覧」をご覧ください。

s = input()
print(s.lower())

.lower() メソッドを使うと、文字列をすべて小文字に変換することができます。例えば、

学習を続けますか？ (yes or no) _

という質問に対して、YES と入力しても、yes として処理することができるようになります。yeS でも YeS でも、

if s.lower() == 'yes':

だけでよく、想定し得る入力値を予め全て用意しておく必要も無く、yes 以外の入力を拒否して再入力を求めたりする必要も無くなります。

全て大文字にしたい場合は .upper()メソッドを使います。

n = int(input())

capslock = False
text = ''
for _ in range(n):
    c = input()
    
    if c == 'capslock':
        capslock = not capslock
        continue
    
    if ('shift' in c) or capslock:
        text += c[-1].upper()
    else:
        text += c

print(text)

ポイントは、

1. capslock の状態をフラグで管理する
2. shift キーが押されている時の文字列の抽出

casplock がロックの状態を True、解除されている状態を False とし、capslock が初め解除されている状態を前提とした問題の書き方がされているだけで capslock の初期状態が問題のどこにも書かれていないのですが😅、初めは解除されている状態でないと出力例のとおりにならないので capslock = False で初期化します。

ここからまず、入力が capslock の時の処理をしておきます。

capslock = not capslock

capslock が False の時は True に、True の時は False へ、not によって反転させています。読むまでもない簡単な内容ですが、この関係を一応「３章 bool型 True と False」の「True or not True」で表にしてあります。

次に、大文字判定の処理をします。単純に 'shift' という文字列が入力 c の文字列の中に含まれている場合、shift キーが押されている状態と判断します。また capslock がロックの状態(True)の時も入力文字が大文字で出力される状態です。この２つのどちらかが True の時、入力文字が大文字で出力されます。出力文字は文字列 c の末尾にありますので要素番号 [-1] を指定します。そして .upper() メソッドを使って末尾の１文字を大文字に変換します。

それ以外の場合は、そのままの文字列を出力します。

このプログラム例の書き方の場合、入力 c が 'capslock' かどうかの判定を先に書かないと、入力値が 'capslock' の場合でも常に 文の else が実行されて capslock という文字列が text に追加されてしまいますので注意です。😅

n = int(input())
x = [int(input()) for _ in range(n)]

results = set()
for i in range(1, 1 << n):
    tmps = []
    for j in range(n):

        if i & 1 << j:  # ビット演算
            tmps.append(x[j])
    
    if sum(tmps) == 777:
        results.add(tuple(sorted(tmps)))

    if len(results) > 1:
        break

if len(results) > 1:
    print('multiple answers')
elif len(results) == 1:
    print(*results.pop())
else:
    print('no answer')

この問題は、入力された数列の中から、その中の数を選んで合計すると 777 になる組み合わせを求める問題です。条件が (1 ≤ n ≤ 8) で $2^8$ = 256、何も選ばないという組み合わせは無いので 1 引いて、最多で255通りの組み合わせ数となります。組み合わせ数自体はまだ許容範囲なのですが、用意される数が 1 〜 8 個と可変なので、それに対応するための 文や 文を書くのは困難極まります。

そこで今回は、ビット演算を用いたビット全探索というアルゴリズムを使って全ての組み合わせを求めます。この方法を知らないと、いくら知恵を絞っても自力で解くのはなかなか難しいでしょう。😓

プログラム例に沿ってどのようにビット全探索で解決をしているのか、見える化して実際に目で追っていってみましょう。

入力例は問題の 入力例1 を利用します。

1
    4
    333
    222
    444
    666

x = [333, 222, 444, 666]

要素数が n = 4 なのでビット数も 4 です。0001 〜 1111 までの二進数を使い、15 通りの組み合わせができます。

for i in range(1, 1 << n):

ループは 1 〜 15 です。1 からスタートします。1 << n というのは $2^{\mathrm{n}}$ (2**n) と同じです。n = 4 なので 16 、range(1, 16) ということになります。i はこの後のビット演算で使いますが、10進数をビットにすると次のようになります。

この 10進数を 2進数に変換するプログラムを自力で組んで使うということではありません。10進数のままビット演算にかけると勝手に 2進数として演算してくれます。この時点ではちょっと何言ってるかわからないかもしれませんが、その疑問を一旦置いといてこのまま解説を続けます。

tmps = []
for j in range(n):
    if i & 1 << j:
        tmps.append(x[j])

ここに組み合わせ問題を解く鍵が詰まっています。n というのはビット数 4 です。

if i & 1 << j:

詳しく説明するよりまず、実際に数値を当てはめて見てみましょう。

i = 10, j = 0 の時

10 & 1 << 0
↓
1010 & 0001 << 0 ← ２進数
↓ 0 ビット左にシフトする(変わらないけど😅)
1010 & 0001
↓
0000 ← ２進数
↓
0 ← 10進数
↓
if False:
(0 は False)

j = 1 の時

10 & 1 << 1
↓
1010 & 0001 << 1 ← ２進数
↓ 1 ビット左にシフトする
1010 & 0010
↓
0010 ← ２進数
↓
2 ← 10進数
↓
if True:
(0 以外は True)

j というのが左にシフトするビット数で、1 << j の 1 (0001) を左に j ビットシフトしていくことで 1 になっている箇所を見つけていきます。(まだ意味わからなくても大丈夫👍)

10進数で 10 (2進数で1010)の時は２ビット目と４ビット目、言い換えると左に１つシフトした時と、３つシフトした時に 1 を見つけることができます。1 を見つけた時のこの j が、

x = [333, 222, 444, 666]

の要素番号として使われます。x[j]

そして実際にこの部分のループを回して tmps の中身がどうなっているかを見てみます。

tmps = []
for j in range(n):
    if i & 1 << j:
        tmps.append(x[j])

tmps の総和が 777 の時、この組み合わせを results に追加します。i = 10 の時では 777 になりませんので、例を変えて説明を続けます。

tmps = [333, 444] の時

if sum(tmps) == 777:
    results.add(tuple(sorted(tmps)))

tmps を昇順ソートし、その結果をタプルにしてからセット型の results に格納します。問題文に『それらの数字を小さい順に出力してください。』とあります。もし、[333, 444] と [444, 333] が見つかったとなった場合、昇順ソートするとどちらも同じ [333, 444] となりますが、重複は１つとカウントすることになりますので、発生したこの重複分を削除する為にリストではなく、セット型でデータを扱います。

sorted() 関数でソートすると、戻り値がリストとして返ります。セット型で扱える値は不変の型(イミュータブル)でなければなりませんので、可変(ミュータブル)の型であるリストから不変の型であるタプルに変換して、そのタプルをセット型の results に格納します。

tmps = [444, 333]
↓ sorted(tmps)
tmps = [333, 444]
↓ tuple([333, 444])
(333, 444)
↓ results.add((333, 444))
result = {(333, 444)}

「足して 777」となる組み合わせが２つ以上ある場合は multiple answers と出力するだけですので、３つ目以降を見つける意味は無く、２つ見つけた時点でループを抜けてしまいましょう。

if len(results) > 1:
    break

if len(results) > 1:
    print('multiple answers')
elif len(results) == 1:
    print(*results.pop())
else:
    print('no answer')

最後に見つけた組み合わせの個数に合わせた結果を画面に出力したら完了です。*results.pop() は、

results = {(333, 444)}

となっています。これを print(*results) だけで画面に出力すると、

(333, 444)

と、セットが外れただけになってしまいます。{ } の中のタプルを取り出してから展開する必要がある為に、.pop() を使っています。*results[0] でも構いません。

入力例1 で実際にビット全探索で組み合わせを作っている様子を表にしました。

x = [333, 222, 444, 666]

333
444

ついでなので入力例2 の時も表にしてみました。

x = [111, 222, 333, 444]

multiple answers