#AtCoder Beginner Contest 006
ということで、さっそくAtCoder Beginner Contestの006から始めていきましょう！
（「001から始めないんかい」という気持ちは胸にしまっておいてください、、、）
##問題-A
数字Nが与えられます。Nに3が含まれる、もしくは3で割り切れる場合はYES、それ以外はNOと出力してください。
N = int(input())
if N % 3 == 0:
print("YES")
else:
print("NO")
FizzBuzz問題の少し簡単版でしょうか。答える際に改行を入れることを忘れずに。
##問題-B
トリボナッチ数列というものがあります。この数列は3つ前までの数字を足したものです。
厳密には、
a_1=0, a_2=0, a_3=1 \\
a_n=a_{n-1}+a_{n−2}+a_{n−3}
と定義されています。この数列の第n項、$a_n$を10007で割った余りを求めてください。
n = int(input())
a, b, c = 0, 0, 1
for i in range(n-1):
a, b, c = (b % 10007), (c % 10007), ((a+b+c) % 10007)
print(a)
この手の大きな数(10^7とか)で割って余りを表示する問題に弱いんです、、最近は最終的な答えを大きな数で割るのではなくてその都度計算するように対策しています。
この問題のほかの考え方としては、$a_1$と$a_2$の場合は0を出力するように分岐してそれ以外の場合はループ回数をn-3としたfor文を回すくらいかなと思います。(gitに上げようと思います。)
##問題-C
「この街には人間がN人いる。人間は、大人、老人、赤ちゃんの3通りだ。この街にいる人間の、足の数の合計はM本で、大人の足は2本、老人の足は3本、赤ちゃんの足は4本と仮定した場合、存在する人間の組み合わせとしてあり得るものを1つ答えよ。」
n, m = map(int, input().split())
for a in range(n+1):
b = 4*n -2*a - m
c = n -a -b
if b >= 0 and c >= 0:
print(a, " ", b, " ", c)
break
else:
print("-1 -1 -1")
何かいろいろ書いてありますが
a+b+c=N \\
2a+3b+4c=M
の連立方程式を解くということと同値ですね。意外と数学の知識を使うことがあるので、頭の中から抜け落ちないように気を付けておきたいところです。
ところで、解法を参考にしているとrange関数ではなくxrange関数というものを見かけました。初めて見かけたので調べるとこのような記事を発見しました。
なるほど、知らぬ間に廃止されていたわけですね。python3から使用してきた身としては全く知らないものでした。これを機にイテレータなどを勉強するのもよいかもしれませんね。
##問題-D
数字が書かれたカードがN枚あります。このカードの束（山札）に対して以下の操作が可能です。
山札からカードを1枚抜き取り、任意の場所に挿入する。
山札の上から下に向けて、カードを昇順に並べ替えるために必要な、最小の操作回数を求めてください。
import bisect
n = int(input())
cards = [int(input()) for i in range(n)]
sort_after_cards = [0]
for card in cards:
if sort_after_cards[-1] < card:
sort_after_cards.append(card)
else:
index = bisect.bisect_left(sort_after_cards, card)
sort_after_cards[index] = card
print(n - len(sort_after_cards) +1)
イメージ的には山札の上にあるカードを一枚引き別の山札を作る感じです。そして昇順にするためには、山札の下に本来元々あるカードよりも大きな数字がこなければならないため、もし小さい数字が来た場合は二分探索で本愛の位置に戻してあげましょう。最終的には交換したカードが除外された昇順の山札リストが作成されます。昇順にするだけならsortやsortedを使えばすぐですね。
#おわりに
初回としてはなかなか理解に苦しみながら進めました。特にC問題やD問題は数学的思考やアルゴリズムを駆使して、いかに計算量を抑えて効率化することが求められているかというのを感じます。
最近のコンテスト的には調子が良くてC問題までしか解けないので、たくさん練習していろんなか発想が思いつくように努力します。