BFT名古屋 TECH BLOG

日々の業務で得た知識を所属するエンジニアたちがアウトプットしていきます。

【Python】AtCoder Beginner Contest 259(A~C問題)やってみた!

はじめに

こんにちは!BFT名古屋支店の猫です。
突然ですが皆さん「競プロ」をご存じですか?
「競プロ」とは「競技プログラミング」の略で、Wikipediaでは以下のように説明されています。

競技プログラミングでは、参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。コンピュータサイエンスや数学の知識を必要とする問題が多く、新卒学生の採用活動などに使われることもある。

引用元:競技プログラミング - フリー百科事典 ウィキペディア日本語版(2022年5月11日 (水) 04:17 UTC
https://ja.wikipedia.org/w/index.php?title=%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0&oldid=89464281



今回は AtCoder という競プロに参加できるサイトで「AtCoder Biginner Contest 259」に参加してみたので、その振り返りを記事にしたいと思います。

atcoder.jp

ABC(AtCoder Biginner Contest)の概要

ABCは以下のルールで開催されます。

  • コンテスト時間:100分
  • 配点:
    • A問題:100点
    • B問題:200点
    • C問題:300点
    • D問題:400点
    • E問題, F問題:500点
    • G問題, Ex問題:600点
  • ルール:
    • コンテスト中に問題に正解すると点数を獲得できる
    • 順位は総合得点で決定する
    • 同点の場合は提出時間の早い人が上の順位になる
    • 誤答を提出するたびにペナルティが加算される(このコンテストのときのペナルティは5分)

ちなみに私が参加した ABC259 では、7,000人以上の方が参加していました。

コンテスト参加の流れはこんな感じです。

  • 参加登録
    AtCoderのアカウントを作成し、コンテストページで [参加登録] を押す。
  • 問題を読む
    どの問題から取り組んでもOKですが、まずは一番易しいA問題から順番に取り組むのがベターだと思われます。
    なお問題には実行時間制限〇秒、メモリ制限〇MBと制限がありますので、コーディングの際は注意が必要です!
  • コーディング
    ローカルの環境でやるもよし、コンテストページの [コードテスト]タブを開いてそこで書くもよしです。
    [コードテスト] タブでは環境構築不要でプログラムを動かすことができるのでとっても便利です。
  • 提出
    [提出]タブを開いて"提出する問題"と"言語"を選択したら 、"ソースコード"欄に作成したプログラムを貼り付け、[提出]ボタンをクリックします。制限時間内であれば何回でも提出可能です。
    私はPythonで参加しましたが、他にもC++JavaScript、GOなど様々な言語で提出することができます!

    提出画面

    提出後はこのように ↓ 結果が表示されます。
    この画像の結果列にある「AC」は正解を表しており、他には「WA(不正解)」、「TLE(実行時間超過)」などがあります。

    提出結果画面

100分という制限時間の中で、私が正解までたどり着けたのはA問題とB問題だけでした。
C問題があとちょっとで完成する…!というところでタイムアップになってしまいとても悔しかったです……。
これからたくさん練習して、もっと速く・たくさん解けるようにがんばります!

問題と回答

ここでは私が実際にAC(正解判定)を得ることができた回答と、そこに至る考え方をご紹介します。
本当は全問分書きたかったのですが、D問題以降は難しくて解説を読んでもコード書けませんでした…(T T)
そのためA~C問題についてのみ記載しています。

A - Growth Record

  • 問題

高橋君は N 歳の誕生日を迎えました。この時の彼の身長は T cmです。
また、以下のことが分かっています。
高橋君は 0 歳の誕生日(生まれた当日)から X 歳の誕生日までの間、毎年身長が D cmずつ伸びた。より厳密に書くと、i=1,2,…,X それぞれに対し、i−1 歳の誕生日から i 歳の誕生日までの間に身長が D cm伸びた。
高橋君は X 歳の誕生日から N 歳の誕生日までの間、身長が変化していない。
高橋君の M 歳の誕生日の時の身長が何cmだったかを求めてください。

  • 制約

0≤M<N≤100
1≤X≤N
1≤T≤200
1≤D≤100
高橋君の 0 歳の誕生日の時の身長は 1 cm以上である
入力はすべて整数

  • 入力

入力は以下の形式で標準入力から与えられる。

N M X T D
  • 出力

答えを整数として出力せよ。

  • 解き方

高橋くんの  x 歳のときの身長を  y (cm)とすると、以下の式が成立する。

 
y = D \cdot x  + ( T - D \cdot X  ) \quad   ( 0 \le x \lt X ) \qquad \cdots ① \\\\
y = T  \qquad \qquad \qquad \qquad \quad  ( X  \le x )  \\

①の式を少し変形すると

 y = T - (X - x) \cdot D

となる。

MとXの大小関係で場合分けをしながら身長を計算する。

  • 回答
# 標準入力から値を取得し、整数値に変換して変数に格納
N,M,X,T,D = map(int, input().split())

# MとXの大小関係で場合分けして身長を計算
if M < X:
  height = T - (X-M)*D
else:
  height = T
 
print(height)

B - Counterclockwise Rotation

  • 問題

x 軸の正の向きが右、y 軸の正の向きが上であるような xy 座標平面において、点 (a,b) を原点を中心として反時計回りに d 度回転させた点を求めてください。

  • 制約

−1000≤a,b≤1000
1≤d≤360
入力はすべて整数

  • 入力

入力は以下の形式で標準入力から与えられる。

a b d
  • 出力

求めるべき点を (a′ ,b′ ) とするとき、 a′ と b′ をこの順に空白区切りで出力せよ。
なお、各出力について、解との絶対誤差または相対誤差が 10-6 以下であれば正解として扱われる。

  • 解き方

異動前の点を点  A ( a, b ) 、異動後の点を点 A' ( a', b' )とする。
 A と原点との距離は

  \displaystyle{AO  = \sqrt{a^{2} + b^{2}}}

と表せる。
また、点 Aと原点を繋いだ線が  x 軸となす角を  \theta とすると

  \displaystyle{\theta  = tan^{-1}\frac{b}{a}
}

と表せる。
移動後の点  A' と原点との距離は、点 Aと原点との距離に等しく、
 A'と原点を繋いだ線が  x 軸となす角の大きさは  \theta + d と表せるので、以下の式が成り立つ。

  \displaystyle{
a' = \sqrt{a^{2} + b^{2}} \cdot \cos{(\theta + d)}\\\\
b' = \sqrt{a^{2} + b^{2}} \cdot \sin{(\theta + d)}
}

  • 回答
import math

# 標準入力から値を取得し、整数値に変換して変数に格納
a,b,d = map(int, input().split())

# アークタンジェントを使用してθを求める
# math.atan2で算出されるθはラジアンの値なので、度に変換することが必要
theta = math.degrees(math.atan2(b, a))

# 「原点を中心として反時計回り」ということは移動前後の点は原点からの距離が同じ
# 三平方の定理と三角関数を利用して移動後の点の座標を求める
a_dash = math.sqrt(a*a + b*b) * math.cos(math.radians(theta + d))
b_dash = math.sqrt(a*a + b*b) * math.sin(math.radians(theta + d))
 
print(a_dash, b_dash)

C - XX to XXX

  • 問題

英小文字からなる 2 つの文字列 S,T が与えられます。 次の操作を好きな回数( 0 回でも良い)行うことで、S を T と一致させることができるかを判定してください。

S において同じ文字が 2 文字連続しているところの間に、その文字と同じ文字を 1 つ挿入する。 すなわち、下記の 3 つの手順からなる操作を行う。
現在の S の長さを N とし、S=S1 S2 …SN とする。
1 以上 N−1 以下の整数 i であって、S i=Si+1 を満たすものを 1 つ選択する。(ただし、そのような i が存在しない場合は、何もせずに手順 3.をスキップして操作を終了する。)
S の i 文字目と i+1 文字目の間に文字 S i(=S i+1) を 1 つ挿入する。その結果、S は長さ N+1 の文字列 S 1 S2 …S i S i S i+1 …SNとなる。

  • 制約

S と T はそれぞれ英小文字からなる長さ 2 以上 2×105 以下の文字列

  • 入力

入力は以下の形式で標準入力から与えられる。

S
T
  • 出力

S を T と一致させることができる場合は Yes を、そうでない場合は No を出力せよ。 ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

  • 解き方

問題で指定された操作では、以下のことが言える。

  • 出現する文字の種類や順番を変えることはできない
    たとえば、S = xyz , T = abc のとき、SをTと一致させることはできない
  • Siの繰り返し回数を減らすことはできない
    たとえば、S = xxxyz , T = xyz のとき、SをTと一致させることはできない。
  • Siの繰り返し回数が1回のとき操作を行うことはできない。
    たとえば、S = xyz , T = xxxyz のとき、SをTと一致させることはできない。

そのため、操作を行うことでSとTを一致させることができる場合、次が成り立つことが分かる。

  1. SとTで出現する文字の種類と順番が完全に一致している
  2. Si = Tj かつ ( Siの繰り返し回数 ) ≠ ( Tjの繰り返し回数) である Si と Tj があるとき、
    2 ≤ ( Siの繰り返し回数 ) < ( Tj の繰り返し回数 )

文字列SとTそれぞれについて、「出現文字(どの文字がでてきたか)」と「出現回数(何回繰り返されたか)」を求め、上記2つの条件を満たしているか判定する。

  • 回答
"""
出現文字の順番と個数を数える関数
入力:input_str 入力の文字列
出力:app_char  出現文字を順番に格納したリスト
      app_num  出現回数のリスト。添え字はapp_charと連動。
"""
def char_count(input_str :str):
  app_char = []
  app_num = []
  c_tmp = input_str[0]
  c_cnt = 0

  for c in input_str:
    if c != c_tmp:
      app_char.append(c_tmp)
      app_num.append(c_cnt)
      c_tmp = c
      c_cnt = 1
    else:
      c_cnt += 1

  app_char.append(c_tmp) #最後の出現文字と回数はここでリストに挿入
  app_num.append(c_cnt)
  
  return app_char, app_num


"""
メイン
"""
# 標準入力から文字列を受け取る
S = input()
T = input()

# 文字列SとTそれぞれの、出現文字の順番と個数を数える
S_char, S_num = char_count(S)
T_char, T_num = char_count(T)

# 初期化
YorN = "Yes" 

# 判定
if S_char != T_char:  # 出現文字の種類と順番が違ったらアウト
  YorN = "No"
  
else:
  for c_num in range(len(S_char)):
    if S_num[c_num] != T_num[c_num]:
      if (S_num[c_num] > T_num[c_num]) or (S_num[c_num] < 2):  # 2 ≤ ( S_iの出現回数 ) ≤ ( T_jの出現回数 ) が成り立たなければアウト
        YorN = "No"
 
print(YorN)

おわりに

今回は「AtCoder Biginner Contest」についてご紹介しました。

AtCoderには、常時できる練習問題や、過去のコンテスト問題+解説が用意されていますので、問題を解きながらプログラミングを学習したい方に持ってこいのサイトです。

興味をもっていただけたら、ぜひ一緒に参加しましょう!

ここまで読んでくださりありがとうございました(^^)