今回で3回目のコンテスト参加となりました。前回が2月22日(土)だったので1ヶ月ぶりでした。この1ヶ月、AtCoderの問題に取り組んでいなかったので、散々な結果となりました。。(日頃からコツコツとやらないとダメですね。)

今回の結果はC問題が解けずに終わってしまい、悔しかったです。今後、類似問題が出てきても解けるように振り返りをします。 今回の僕の結果はこちら から。(弱弱なので、お恥ずかしい。笑)

A - Coffee

問題文

ある長さ6の英小文字からなる文字列がcoffeeに似ているとは、3文字目と4文字目が等しく、5文字目と6文字目も等しいことを言います。与えられる文字列Sがcoffeeに似ているか判定してください。

制約

Sは長さ6の英小文字からなる文字列である。

解説

この問題は長さ6の文字列が3文字目 = 4文字目5文字目 = 6文字目の時にYes、違う時にNoを表示すればOKです。

回答

N = input()
if(N[2] == N[3] and N[4] == N[5]):
    print("Yes")
else:
    print("No")

B - Golden Coins

問題文

高橋君は金色の硬貨が好きです。自分が持っている500円硬貨1枚につき1000、5円硬貨1枚につき5の嬉しさを得ます。高橋君はX円を持っています。これを高橋君の嬉しさが最大になるように両替したとき、高橋君の嬉しさはいくらになりますか? (なお、利用できる硬貨は500円玉、100円玉、50円玉、10円玉、5円玉、1円玉の6種類とします。)

制約

  • 0≤X≤10^9
  • Xは整数

解説

高橋君が持っているX円が500円何枚分(Y枚)あるのかを求めてから、X=X-500*Y円をして、同様にX円が5円何枚分(Z枚)あるか求めます。 その後、Y*1000+Z*5を表示すればOKです。

回答

math.floorを使うことで小数点以下を切り捨てしています。

import math

X = int(input())
total_500 = 0
total_5 = 0
total_count = 0

if(X >= 500):
    total_500 = math.floor(X/500)
    total_count += total_500 * 1000
    X -= total_500 * 500

if(X >= 5):
    total_5 = math.floor(X/5)
    total_count += total_5 * 5
    X -= total_5 * 5

print(total_count)

C - Traveling Salesman around Lake

問題文

1周Kメートルの円形の湖があり、その周りにN軒の家があります。i番目の家は、湖の北端から時計回りにAiメートルの位置にあります。 家の間の移動は、湖の周りに沿ってのみ行えます。 いずれかの家から出発してN軒すべての家を訪ねるための最短移動距離を求めてください。

制約

  • 2≤K≤10^6
  • 2≤N≤2×10^5
  • 0≤A1<…<AN<K
  • 入力中のすべての値は整数である。

解説

この問題を解いているとき、全ての出発地点からの最短経路を全部計算するのかなと思ってしまい、実装方法が訳分からずに途中で解くのをやめました。。
解き方として、円形の湖沿いを通って全ての家を通る必要があるので、最短経路を求めるには家と家の距離が最大の道を通らなければいいみたいです。(こういう問題を円環っていうらしいです。) 以下の画像のように、湖を2周した長さを直線で表示すると、それぞれの家と家の距離がわかるので、最大の道をKメートルから引いてあげます。 解説

a,b = [int(i) for i in input().split()]
l  = [int(i) for i in input().split()]
l.append(l[0] + a)

l2 = [l[i+1] - l[i] for i in range(b)]

print(a - max(l2))

まとめ

AtCoderはプログラミング力と数学的思考力が求められて、いい勉強になるので、今後もコンテストに参加していきます!! まずは、C問題までをミスなく解けるようにならなくては。。

今回引用した問題

https://atcoder.jp/contests/abc160