Official

A - Shampoo Editorial by kyopro_friends


プログラミングの学習を始めたばかりで何から手をつけるべきかわからない方は、まずは「practice contest」(https://atcoder.jp/contests/practice/) の問題A「Welcome to AtCoder」をお試しください。言語ごとに解答例が掲載されています。
また、プログラミングコンテストの問題に慣れていない方は、「AtCoder Beginners Selection」(https://atcoder.jp/contests/abs) の問題をいくつか試すことをおすすめします。
「競プロ典型 90 問」(https://atcoder.jp/contests/typical90) では、プログラミングコンテストで扱われる典型的な 90 問の問題に挑戦可能です。
「C++入門 AtCoder Programming Guide for beginners (APG4b)」(https://atcoder.jp/contests/APG4b) は、競技プログラマー向けのC++入門用コンテンツです。


解法1

実際にシミュレーションをしてみましょう。シャンプーが不足するまで無限ループする、以下のような実装が容易です。

実装例(Python)

V,A,B,C=map(int,input().split())
while True:
  if V<A:
    print("F")
    exit()
  V-=A
  if V<B:
    print("M")
    exit()
  V-=B
  if V<C:
    print("T")
    exit()
  V-=C

このアルゴリズムの計算量は \(O(V)\) です。

解法2

まず \(V<A+B+C\) の場合を考えてみましょう。 このときは、以下のような単純な場合分けで答えを求める事ができます

if V<A:
  print("F")
elif V<A+B:
  print("M")
else:
  print("T")

\(V\geq A+B+C\) である間、シャンプーは \(1\) 日あたり \(A+B+C\) ずつ消費されます。したがって、ある日の朝の時点でシャンプーの残りが \(A+B+C\) 未満になったとき、その量は \(V\%(A+B+C)\) です。(\(x\%y\)\(x\)\(y\) で割った余りを表します)
よって、全体としては次のような方法により解くことができます。

実装例(Python)

V,A,B,C=map(int,input().split())
V%=A+B+C
if V<A:
  print("F")
elif V<A+B:
  print("M")
else:
  print("T")

このアルゴリズムの計算量は適当な仮定の下で \(O(1)\) です。

posted:
last update: