AtCoder Beginners Contest 168のA,B,C問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル:余計なことを考えずに済む
- 実装が楽:ミスやバグが減ってうれしい
- 時間がかからない:パフォが上がって、後の問題に残せる時間が増える
AtCoder Beginners Contest 168
全提出人数: 10866人
パフォ | AC | 点数 | 時間 | 順位 | 目安 |
---|---|---|---|---|---|
400 | ABC--- | 600 | 62分 | 6607位 | 茶パフォ |
600 | ABC--- | 600 | 36分 | 5323位 | 8回で茶レート |
800 | ABC--- | 600 | 16分 | 4025位 | 緑パフォ |
1000 | ABCD-- | 1000 | 76分 | 2861位 | 8回で緑レート |
1200 | ABCD-- | 1000 | 48分 | 1950位 | 水パフォ |
(参考)私:1244位 パフォーマンス1418
私は、センター数IIBでベクトルをやりたくないから、統計を選んで逃げた人間です。(いつの話だ)
- A問題 (10686人AC) 『∴ (Therefore)』
- 1の位の取り出し方を知っていれば解けます。よく使うので3秒で思い出せるようにしましょう。
- B問題 (10466人AC) 『... (Triple Dots)』
- Pythonならそのままやるだけですね。
- C問題 (7598人AC) 『: (Colon)』
- 余弦定理、覚えてますか?私はググりました。
- D問題 (3856人AC) 『.. (Double Dots)』[この記事では解説しません]
- 1から幅優先探索(BFS)するとできます。なお、答えは常にYESです。
A問題 『∴ (Therefore)』
問題ページ:A - ∴ (Therefore)
むずかしさ:★☆☆☆☆
ポイント:文字列の扱いor余りの扱い
与えられた数字の1の位がわかれば、あとは場合分けで解けます。
A問題にしては若干面倒だと思います。こういうのは考える前に手を動かしたほうが、結果的に早く済みます。
解き方
1. 実装を考える
ステップ1:実装を考える
1の位の求め方は次の2パターンがあります。
- 文字列で受け取って、
c = n[-1]
とする(str型) - 整数で受け取って、
c = n % 10
とする(int型)
そのあと、if c in ["0", "1", "6", "8"]:if c in "0168"
などとすればいいです。(リストより文字列のほうが打つのが楽なので、変更しました)
コード
文字列で受けとるパターンだとこうなります。"hon"
パターンは一番多い5文字打つ必要があって面倒なので、elseブロックにするとちょっと楽です。
bon
,pon
,hon
は似ていて紛らわしいので、無駄なWAを出さないよう、焦らずよく確認してから提出しましょう。
(しかし、文字列なら"24579"
も一瞬で打てるので、問題文の通りの順番で書いたほうがミスしづらくていいかもしれません)
n = input()
c = n[-1]
if c in "3":
print("bon")
elif c in "0168":
print("pon")
else:
print("hon")
整数で受け取って、10で割った余りで1の位を求めるパターンはこうなります。
n = int(input())
c = n % 10
if c in [3]:
print("bon")
elif c in [0, 1, 6, 8]:
print("pon")
else:
print("hon")
B問題 『... (Triple Dots)』
問題ページ:B - ... (Triple Dots)
むずかしさ:★☆☆☆☆
ポイント:文字列の扱い
Pythonだと超簡単なやつです。Pythonに感謝しています。
解き方
1. 実装を考える
ステップ1:実装を考える
とりあえず、文字列の長さを求めましょう。これはl = len(s)
で一発ですね。
if l <= k:
ならば、そのまま出力すればいいので、print(s)
です。
そうでない場合、先頭 $K$ 文字を切り出して、末尾に'...'
を付加して出力します。つまり、print(s[:k]+'...')
です。s[:k]
は、sの0文字目~k-1文字目なので、合計でk文字です。
コード
'...'
は念の為、問題文からコピーしてペーストしたほうが間違いがなくていいです。
見間違えて'...'
とか'…'
などと書いてWAを出す可能性も、ないとは言えません。
k = int(input())
s = input()
l = len(s)
if l <= k:
print(s)
else:
print(s[:k]+'...')
C問題 『: (Colon)』
問題ページ:C - : (Colon)
むずかしさ:★★★★☆(個人差あり)
ポイント:高校数学、ラジアンと度数法の知識
高校数学の問題です。余弦定理を使います。
こういう数学問題は、手元に関数電卓があると便利かもしれません。
持ってない人でも、Windows付属の電卓に関数電卓モードがあります。または、Google検索で関数電卓と検索してもいいです。
数学問題は個人差が大きいです。AtCoder ProblemsのDifficultyは107でしたが、水や青コーダーでも解けなかった人がそこそこいるので、できなくても落ち込まなくて大丈夫です。
具体的な数字を出すと、AC者 / 参加者は、水 702 / 742、青 333 / 350です。このレート帯の人たちは、普段のC問題ならほぼ全員がACするので、かなり特殊な問題だったと言えます。
解き方
1. 解法を考える
2. 針の間の角度を求める
3. Pythonのcos関数の使い方に気をつける(度数をラジアンに直す)
4. ちゃんとルートを取る
ステップ1:解法を考える
解き方は2パターンあります。
- 余弦定理を使って求める
- 針の座標を求めて、三平方の定理を使う
余弦定理でやる人がほとんどなので、こちらで解説します。というか、座標で求めようと思う人は数学が得意なはずなので、こんな解説を読む必要はないですね。
高校でやった余弦定理は、三角形の2辺とその間の角度から、残り1辺の長さを求める公式です。
$c^{2} = a^{2} + b^{2} - 2abcos{θ}$
$a$と$b$はそれぞれ時針、分針の長さとして与えられているので、時針と分針の間の角度 $θ$ がわかれば解けます。
やる気があれば図を書くところですが、面倒なので、グーグルで余弦定理と検索するといい感じの画像がいっぱい出てきます。
ステップ2:針の間の角度を求める
どうやって針の間の角度を求めればいいでしょうか。
0時0分の頂点を0度として、分針と時針の角度をそれぞれ求めます。そして、進んでいるほうから、もう一方の角度を引けばいいです。
例えば時針が15度、分針が60度なら、60-15=45度です。(適当な数字なので、リアル時計でこういう角度にはならないと思います)
分針の角度
60分で360度なので、1分で360÷60 = 6度進みます。
時針の角度
12時間で360度なので、1時間で360÷12 = 30度進みます。ただし、現実の時計がそうなっているように、分単位でも進むことに注意しましょう。
60分×12時間=720分で360度と考えて、1分で360÷720 = 0.5度進むとしたほうがわかりやすいです。例えば9時45分なら、9×60+45 = 585分で、585×0.5 = 292.5度です。
鋭角になおさなくてもいい
例えば、時針が5度で分針が350度だったとします。(この角度も適当です)
このとき、350-5=345度になりますが、針と針の間は鋭角の15度な気がします。
ですが、345度の鈍角のまま計算しても大丈夫です。$cos(θ)=cos(360°-θ)$だからです。単位円を覚えている人は、思い出してみるとわかると思います。細かい話は数学をちゃんと解説してるサイトを見てください。
なお、私はこれを忘れて変換しようとしたうえ、変換で間違って1WA出しました。
ステップ3:Pythonのcos関数の使い方に気をつける(度数をラジアンに直す)
math
モジュールにmath.cos()
というそのものな関数があります。
しかし、さっき求めた角度をそのままmath.cos()
関数に入れてはいけません。math.cos()
関数の入力は、ラジアン($\pi = 180^\circ$)だからです。
わざわざ計算したり、ラジアンの定義を思い出して計算する必要はありません。度数をラジアンに変換する関数math.radians()
を使えばいいです。
ステップ4:ちゃんとルートを取る
もう一度書きますが、余弦定理の公式は
$c^{2} = a^{2} + b^{2} - 2abcos{θ}$
です。
求められるのは $c^{2}$ なので、ちゃんとルートを取って $c$ にしてあげましょう。
コード
「進んでるほうの針の角度からもう一方の針の角度を引く」は「差の絶対値」を取るのと同じなので、そう書きました。(実はこれもやらないでマイナスになってもいいのですが)
import math
a, b, h, m = list(map(int, input().split()))
deg_a = (60 * h + m) * (360 / (60 * 12))
deg_b = m * (360 / 60)
deg = abs(deg_a - deg_b)
rad = math.radians(deg)
c2 = a ** 2 + b ** 2 - 2 * a * b * math.cos(rad)
print(c2 ** 0.5)
余談:マイナスのままでもいい
さきほど書いたように、abs(deg_a - deg_b)
として、進んでいる針の角度から進んでいない針の角度を引いた値を求めていますが、マイナスのまま計算しても別にいいです。
三角関数の性質的にそうなるからです。ググるとわかります。