2019-07-18

ABC126-B - YYMM or MMYY を解く

ABC-B

ABC126-B - YYMM or MMYY

入力される4桁の数字が年月フォーマット表記で

MMYY であるか YYMM であるかを判定する問題

MM は月、YY は年（西暦の下2桁）を表す

MM は 01 〜 12 の範囲をとり、YY は 00 〜 99 の範囲をとる

こうして見るととても簡単そうに見えるが、この問題はやっかいなことに

MMYY でも YYMM とも判定できない場合（AMBIGUOUS）と

どちらの可能性もあり得ない場合（NA）

のパターンも入力値として与えられる場合がある

これらの場合も考慮して場合分けを行う必要がある

丁寧に一つずつ考えていきたい

まず、2桁の数字が 00 の場合、これは YY でしかあり得ないことがわかる

月は 01 〜 12 の範囲を取るからだ

同じ理由で 13 〜 99 の場合も YY でしかあり得ない

この範囲を取る場合はそれは YY だと考えられ、もう一方が MM だと考えられる

もう一方が MM だと考えられる場合、それが本当に MM の範囲を

満たしているかどうかを確認する必要がある

つまり、 01 〜 12 内の数字であるかどうかの確認だ

条件を満たしていなければ NA となる

また、YY の特定が困難な場合は AMBIGUOUS となる

例えば、1205 などは 12年05月なのか、05年12月なのか区別がつかない

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
S=input()

# MMの条件：01〜12
# YYの条件：00〜99

# 前半
a=int(S[:2])

# 後半
b=int(S[2:])

# "00"になるのはYYだけ
if a==0:
  if 0<b and b<13:
    print('YYMM')
  else:
    print('NA')

elif b==0:
  if 0<a and a<13:
    print('MMYY')
  else:
    print('NA')

# 13以上になるのはYYだけ
elif a>12:
  if 0<b and b<13:
    print('YYMM')
  else:
    print('NA')

elif b>12:
  if 0<a and a<13:
    print('MMYY')
  else:
    print('NA')

# それ以外の場合は断定できない
else:
  print('AMBIGUOUS')

提出結果はACでした

2019-07-17

ABC125-B - Resale を解く

ABC-B

ABC125-B - Resale

N個の宝石がある

i 番目の宝石は Vi の価値があり、コスト Ci を払って手に入れることができる

（手に入れた宝石の価値の和） - （支払ったコストの和）の最大値を求める問題

単純に考えて、 Vi ＜ Ci となる宝石を手に入れるメリットはないことがわかる

したがって、Vi ＞ Ci となる宝石を手に入れた場合について考えればいい

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
N=int(input())
vl=list(map(int,input().split()))
cl=list(map(int,input().split()))

ans=0
for i in range(N):
  if vl[i]>cl[i]:
    ans+=vl[i]-cl[i]

# 出力
print(ans)

提出結果はACでした

2019-07-16

ABC124-B - Great Ocean View を解く

ABC-B

ABC124-B - Great Ocean View

東西に N 個の山があり、西の果てには海がある

ある山（山Aとする）より西にある山の高さがすべて山A の高さ以下の場合

山Aからは海を見ることができる

このとき、海を見ることができる山はいくつあるかを求める

まず、西端にある山は、それより西に山がないので、必ず海を見ることができる

その次にある山は、西にある山より高いか、同じ高さなら海を見ることができる

その次にある山は、西にある山々より高いか、同じ高さなら海を見ることができる

その次にある山は、西にある山々より高いか、同じ高さなら…

というように、自分より西にある山々よりも高い、もしくは同じ高さなら

海が見えることがわかる

したがって、左端から山の高さの最高値を取っていって

今見ている山の高さがそれ以上の高さであるかどうかを確認していけばいい

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
N=int(input())
l=list(map(int,input().split()))

# 最高地
mx=0

# 海が見える山の数
c=0

for x in l:
  if mx<=x:
    # 海が見える山の数を更新
    c+=1

    # 西側にある山の最高値を更新
    mx=x

# 出力
print(c)

提出結果はACでした

2019-07-15

ABC123-B - Five Dishes を解く

ABC-B

ABC123-B - Five Dishes

調理時間がそれぞれ A分、B分、C分、D分、E分かかる料理がある

また、10の倍数の時間のときだけ注文ができる

すべての料理を注文するとき、最後の料理の到着が最も早くなる注文方法を求める

5つの料理の注文順番は 5! = 120 通りある

全パターンについてかかる時間を求め、最も短いものを答えとすれば良い

（ちょっと書くの難しそう）

パターンの列挙には itertools モジュールが便利

>>> import itertools
>>> l=[1,3,5]
>>> for c in itertools.permutations(l):
...     print(c)
... 
(1, 3, 5)
(1, 5, 3)
(3, 1, 5)
(3, 5, 1)
(5, 1, 3)
(5, 3, 1)

itertools.permutations 関数を使用することで上記のように順列を求めることができる

今回はこれを利用する

以上を踏まえて書いたコードを以下に示す

提出したコード

import itertools

# 入力
A=int(input())
B=int(input())
C=int(input())
D=int(input())
E=int(input())

# 時刻の最小値（とても大きな値で初期化しておく）
ans=10**10

# 120通りの注文パターン
for c in itertools.permutations([A,B,C,D,E]):
  # 時間を計測する（t=0からスタート）
  t=0
  for x in c:
    # 10の倍数のときに注文ができる
    if t%10==0:
      t+=x
    else:
      # 10の倍数でない場合は10の倍数まで時を進める
      t+=10-(t%10)
      t+=x

  # 時刻の最小値を更新
  ans=min(ans,t)

# 出力
print(ans)

初めに説明した通り

現在時刻が10の倍数でない場合は10の倍数まで時を進める必要がある

# 10の倍数でない場合は10の倍数まで時を進める
t+=10-(t%10)

t % 10 を計算することで現在時刻の一の位を求めることができる

その結果を 10 から引くことで

あと何分進めれば現在時刻が 10 の倍数になるかがわかる

提出結果はACでした

今回の問題は別解もあるので興味のある方は解説PDFの方もご覧ください

AtCoder Beginner Contest 123 解説

2019-07-14

ABC122-B - ATCoder を解く

ABC-B

ABC122-B - ATCoder

文字列 S が与えられる

Sの（連続した）部分文字列であり、最も長い "ACGT文字列" を求める問題

"ACGT文字列" とは、"A", "C", "G", "T" 以外の文字を含まない文字列を指す

今回は、カウンタ変数を用意し

ACGT文字列だったときに +1 ずつカウントしていく方法で解く

ACGT文字列でなかったときは最大値を更新し、カウンタを 0 にリセットする

このやり方であれば最も長いACGT文字列の長さを求めることができる

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
S=input()

# 最大連続数
mx=0

c=0
for x in S:
  if x in 'ACGT':
    c+=1
  else:
    mx=max(mx,c)
    c=0

# 最後にも忘れずに取る
mx=max(mx,c)

# 出力
print(mx)

注意しなければいけないこととして

ループ終了時にも最大値の更新をする必要がある

これを忘れると、全てがACGT文字列であった場合

最大値が一度も更新されず、答えが 0 になってしまう（これで 1WA した）

提出結果はACでした

2019-07-13

ABC121-B - Can you solve this? を解く

ABC-B

ABC121-B - Can you solve this?

N個の数列 { Ai1, Ai2, ... AiM } と数列 { B1, B2, ... , Bn } および整数 C が与えられる

Ai1B1 + Ai2B2 + ... + AiMBM + C > 0 となるものはいくつあるかを答える問題

問題文だけ読むとわかりづらいのでサンプルを見てみる

入力例1

2 3 -10

1 2 3

3 2 1

1 2 2

上記の場合、N = 2, M = 3, C = -10

{ B1, B2, B3 } = { 1, 2, 3 }

{ A11, A12, A13 } = { 3, 2, 1 }

{ A21, A22, A23 } = { 1, 2, 2 }

となる

以上より

Ai1B1 + Ai2B2 + ... + AiMBM + C の値は

A11B1 + A12B2 + A13B3 + C = 3 × 1 + 2 × 2 + 1 × 3 - 10 = 0

A21B1 + A22B2 + A23B3 + C = 1 × 1 + 2 × 2 + 2 × 3 - 10 = 1

となり、0より大きいものは 2番目のパターンのみであるため、答えは 1 となる

やっていることは各項をつき合わせて積を取り

総和を求めて最後にCを足す

その値が 0 より大きいものはいくつあるかを数えるだけだ

以上を踏まえて書いたコードを以下に示す

提出したコード

提出結果はACでした

2019-07-12

ABC120-B - K-th Common Divisor を解く

ABC-B

ABC120-B - K-th Common Divisor

AもBも割り切れる数のうち、K番目の大きさのものを出力する問題

1から順に割れる数を挙げていって、K番目の約数が見つかったら

出力すればいい

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
A,B,K=map(int,input().split())

# カウンタ（何番目に大きいか？）
c=0

for i in range(1,min(A,B)+1):
  if A%i==0 and B%i==0:
    c+=1

  # K番目に大きい割り切れる数が出たら終了
  if c==K:
    print(i)
    exit()

提出結果はWAでした。 …なんで？

問題文をもう一度読んでみる

＞ AもBも割り切る正整数のうち、K番目に大きいものを求めてください。

うーん、どうやら誤読していたっぽい

上記のコードは、小さい方からK番目に大きい数字を挙げていたが

この問題は大きい方からK番目に大きい数字を挙げる必要があるらしい

仕方ないので、AとBを割り切れる数を全て列挙して

大きい方からK番目の数を出力するコードに書き換えることにする

再提出したコード

# 入力
A,B,K=map(int,input().split())

# 割り切れた数を保存するリスト
l=[]

for i in range(1,min(A,B)+1):
  if A%i==0 and B%i==0:
    l.append(i)

# 出力
print(l[-K])

提出結果はACでした

いやー誤読って怖いなあ

考えて競プロする

プログラミングコンテストの問題をどう考えて解いたかを記録していくブログです。使用言語はPython3

ABC126-B - YYMM or MMYY を解く

ABC125-B - Resale を解く

ABC124-B - Great Ocean View を解く

ABC123-B - Five Dishes を解く

ABC122-B - ATCoder を解く

ABC121-B - Can you solve this? を解く

ABC120-B - K-th Common Divisor を解く