ABC226参戦記

ABC226の参加記録です。

レートは600程度で、使用言語はPython3です。
私が理解した内容でABC226のA問題からC問題までのACコード付き振り返る記事です。

A – Round decimals

標準入出力と、条件分岐が問われる問題。

整数部分と、小数点以下の部分を分けて入力でもらって、問題文に書かれている通り、少数第一位を四捨五入するプログラムを書けばOKですね。

四捨五入する組み込み関数 round() を使いたくなりますが、注意して使わないとWAになります。
このあたりの記事がわかりやすいと思います。

私は、上記の通り、問題文に書いてある通りの実装をしてACしました。

# AtCoder Beginner Contest 226
# A - Round decimals

N1,N2=map(str,input().split('.'))
if int(N2[0])>=5:
    print(int(N1)+1)
else:
    print((int(N1)))

組み込み関数の round() を使用する場合には、小数第3位よりも少ない適当な数字を足してround() を使用した以下のようなコードでもACしますね。

print(round(float(input())+0.0001))

B – Counting Arrays

過去問(ABC216-B Same Name)を復習していますか？が問われる問題 。
今回のA問題については、問題に書いてある通りの実装をしたらACしますが、このB問題については、問題文に書いてある通りの実装をしようとすると、ものすごく難しいと思います。

私は、問題文に書いてあることを実装しようとして30分程度、「書けない。書けない。どうしよう。」と言っていました。

よく考えると、上記の通り、ABC216-B問題の類題であることがわかります。

for文で 入力をset に入れていき、setの要素数を出力すればOKですね。

# AtCoder Beginner Contest 226
# B - Counting Arrays

N=int(input())

S=set()

for _ in range (N):
    L=input()
    S.add(L)

print(len(S))

C – Martial artist

メモ化再帰が解けますか。という問題。

私は再帰関数が本当に苦手で、苦労しました。
アルゴ式というサービスで再帰関数を繰り返し解いて、昔に比べて少し慣れていたため、解くことが出来ました。

以下、この問題を解く方針は以下のようにして解きました。

• 技Nを習得するために、事前に習得しておかなければならない技があるか。
• もし、事前に習得しておく技がないならば、技Nを習得するための時間を記録する。
• もし、事前に習得しておく技はあるが、全て習得済みならば、技Ｎを習得するための時間を記録する。
• もし、事前に習得しておく技があり、未収得の技がある場合、その各技に対して、再帰的に解く。

再帰関数の上限を増やすのを忘れないようにしましょう。

# AtCoder Beginner Contest 226
# C - Martial artist

import sys

# 再帰上限を増やす
sys.setrecursionlimit(1000000000)

def training(waza_index):
    # 技の情報を取得する
    datum = DATA[waza_index]
    # その技が習得済みかどうか
    if learned[waza_index] == True:
        return
    else:
        # 事前習得必要な技が無いなら、習得する時間を書き込み、習得済みにする
        if datum[1] == 0:
            practice_time[waza_index] = datum[0]
            learned[waza_index] = True
            return 
        # 事前習得必要な技があるなら、事前習得に必要な各技について再帰的に解く
        else:
            for i in range (datum[1]):
                if learned[datum[2+i]] == False:
                    training(datum[2+i])
            # 事前習得が必要な各技が全て習得出来たら、習得に必要な時間を書き込み、習得済みにする
            practice_time[waza_index] = datum[0]
            learned[waza_index] = True



N = int(input())

# 各技(1-index)の情報が格納された配列
DATA = []
DATA.append(list()) # 1-indexにするため
for _ in range (N):
    l = list(map(int,input().split()))
    DATA.append(l)

# 技i(1-index)が習得済みならTrue
learned = [False]*(N+1)
# 技i(1-index)を習得するのに必要な時間
practice_time=[0]*(N+1)


training(N)

print(sum(practice_time))