AtCoder Beginner Contest 010 B花占いについて

Question

問題文

高橋君の秘書のなぎさちゃんは、高橋君が大好きです。つまり、高橋君もなぎさちゃんの事が大好きであるに違いありません。 そのことを確認するために、庭に咲いている花で、花占いをすることにしました。

「好き」、「嫌い」、「好き」、「嫌い」、「好き」、「嫌い」……。

おかしいです。高橋君はなぎさちゃんの事が好きであるはずなのに、花占いの結果は「嫌い」でした。 これは、花が悪いに違いありません。

なぎさちゃんは、使用人達に、花占いの結果が「嫌い」にならないように、花びらを毟るよう命じました。

なぎさちゃんの花占いは、2つのパターンがあります。 一つは、「好き」「嫌い」を交互に言いながら、花びらを 1 枚ずつ毟っていくパターンです。 もう一つは、「好き」「嫌い」「大好き」の 3 つを繰り返しながら、花びらを1枚ずつ毟っていくパターンです。

どちらのパターンにおいても、最後に言った言葉が、花占いの結果となります。

なぎさちゃんの使用人であるあなたは、なぎさちゃんがどちらのパターンで花占いをしたときも、「嫌い」にならないように、 花びらを事前に毟ってあげる必要があります。

庭に咲いている花の数と、その花びらの枚数が与えられるので、花びらを毟る必要のある枚数を出力してください。

入力
入力は以下の形式で標準入力から与えられる。

n
a1 a2 ... an
1 行目には、庭に咲いている花の数を表す整数 n(1≦n≦10) が与えられる。
2 行目では、それぞれの花の花びらの枚数に関する情報が、スペース区切りで与えられる。 i 番目の花の花びらの枚数は、 i 番目に与えられる整数 ai(1≦ai≦9)によって与えられる。
出力
毟る必要のある花びらの枚数を 1 行で出力せよ。出力の末尾には改行をいれること。

入力例1
Copy
3
5 8 2
3
5 8 2
出力例1
Copy
4
4
最初の花に注目します。

花びらの数が 5 枚の時、2 つ目のパターンの花占いで、「好き」「嫌い」「大好き」「好き」「嫌い」となり、「嫌い」になってしまうので、花びらを毟らなければなりません。
花びらの数が 4 枚の時、1 つ目のパターンの花占いで、「好き」「嫌い」「好き」「嫌い」となり、「嫌い」になってしまうので、花びらを毟らなければなりません。
花びらの数が 3 枚の時、1 つ目のパターンで「好き」、2 つ目のパターンで「大好き」となるため、花びらを毟る必要がありません。
同様に、花びら 8 枚の花は 7 枚に、花びら 2 枚の花は 1 枚にすることにより、「嫌い」になることを防ぐことが出来ます。

花びらを毟る必要のある枚数の合計は、2+1+1=4 枚となります。

質問文　この問題をpythonで解けずに困っています。

方針1は、一つ目のパターンなら、余りが出ないとき1枚毟る。二つ目のパターンなら余りが2のとき1枚毟るを利用して。以下のコードを考えました。
n = int(input())
x = [int(input()) for i in range(n)]
if x[i] % 2 == 2:
x[i] = x[i] - 1
if x[i] % 2 == 0:
x[i] = x[i] - 1

ここまで考えましたが、これだと毟った数をどのように足せばいいのかわからないので別の方針を試そうと思い、解説を読んだところ、方針2で
「それぞれの枚数について、毟る枚数をあらかじめ書いておく。
{0, 0, 1, 0, 1, 2, 3, 0, 1, 0}を用いる。」とありましたが、{0, 0, 1, 0, 1, 2, 3, 0, 1, 0}がどの枚数を表しているかわかりません。

長々と書きましたが、アルゴリズム的に簡単なのは方針2だと思います。そのため、こちらで解きたいので{0, 0, 1, 0, 1, 2, 3, 0, 1, 0}がどの枚数を表しているか教えてください。

Answer 1

方針２においては、以下の表を見てよく考えると理解できるかと思います。

花弁枚数	1	2	3	4	5	6	7	8	9
好/嫌	○	×	○	×	○	×	○	×	○
好/嫌/大好	○	×	◎	○	×	◎	○	×	◎
毟る枚数	0	1	0	1	2	3	0	1	0

ただし、題意ではありえない花弁０枚をリスト操作の都合上、先頭に０を入れていると思われます。

Comments

[negoto]

とてもわかりやすい解説ありがとうございます！
問題見直してみたら花弁は最大で10枚だからこのようなものを用いたんですね。

Answer 2

{0, 0, 1, 0, 1, 2, 3, 0, 1, 0}がどの枚数を表しているか

各花の花びらの枚数の入力での制約は、1-9ですが、値から見る限り、0から9の10個を表現しているように思います。

---

# coding: utf-8
def conv(x):
    leafToRemove = {"1":0, "2":1, "3":0, "4":1, "5":2, "6":3, "7":0, "8":1, "9":0}
    return leafToRemove[x]

input()
print(sum([conv(x) for x in input().split(" ")]))

Comments

[negoto]

回答ありがとうございます！
コードまで示していただき大変わかりやすかったです。