【AtCoder】ABC168 (A~D) 参戦記

今回も出来が良かったので記事に残すことにした

結果

順位:10866人中708位

得点:1000点

ペナルティ付き最終解答時間:23:19

パフォーマンス:1676

各問題の結果
得点 WA回数 解答時点での経過時間
A 100点 0 2:21
B 200点 0 3:40
C 300点 0 12:52
D 400点 0 23:19
E 500点 - -
F 600点 - -

レート変化

806→948 (+142)

f:id:monhime:20200518084817j:plain:w400

f:id:monhime:20200518083930j:plain:w400

初めての青パフォを取れ,レートが大幅に増加した

30分未満でA-D4完できたのでかなり良かった

解答

A: ∴ (Therefore)

A - ∴ (Therefore)

問題要約

$N$の1の位が2, 4, 5, 7, 9のとき"hon", 0, 1, 6, 8のとき"pon", 3のとき"bon"を出力せよ。

解答

$N$を10で割った余りで条件分岐

コードを見る(クリックして下さい)

ABC168 A問題 解答

 

Submission #13291399 - AtCoder Beginner Contest 168

B:... (Triple Dots)

B - ... (Triple Dots)

問題要約

文字列$S$の長さが$K$以下なら$S$をそのまま, $K$より大きければ先頭$K$文字だけを切り出し末尾に"..."を付加して出力せよ。

解答

文字列の一部の取り出しはpythonならs[:k]で簡単。

コードを見る(クリックして下さい)

ABC168 B問題 解答

 

Submission #13295194 - AtCoder Beginner Contest 168

C: : (Colon)

C - : (Colon)

問題要約

時針の長さが$A$, 分針の長さが$B$のアナログ時計について,$H$時$M$分のときの2つの針の先端間の距離を答えよ。

解法

単純に2点間の座標から距離を求める。余弦定理でも出来る。

0時0分の方向をx軸,3時の方向をy軸として,求めたい時刻のときの針の角度を出す。時針と分針の角度(弧度法)は,$\theta_A=\frac{H+\frac{M}{60}}{12}\times2\pi$, 分針は$\theta_B=\frac{M}{60}\times2\pi$で求まる。

時針の先端の座標$(x_A,\,y_A)=(A\cos \theta_A,\,A\sin \theta_A)$, 分針の先端の座標$(x_B,\,y_B)=(B\cos \theta_B,\,B\sin \theta_B)$を用いることで,求める距離は$\sqrt{(x_A-x_B)^2+(y_A-y_B)^2}$と表される。

解答

コードを見る(クリックして下さい)

ABC168 C問題 解答

 

Submission #13309145 - AtCoder Beginner Contest 168

D: .. (Double Dots)

D - .. (Double Dots)

問題要約

洞窟には$N$個の部屋と$M$本の通路があり,各部屋には1から$N$の,各通路には1から$M$の番号が付いている。通路$i$は部屋$A_i$と$B_i$を双方向につないでいる。どの2部屋間も,通路をいくつか通って行き来できる。部屋2からNの各部屋について,「その部屋から出発し,今いる部屋に設けられた道しるべに書かれた部屋の番号に移動する」ことを繰り返すことで部屋1に辿り着けるように各部屋に道しるべを設けたい。道しるべの番号は,その部屋から通路で直接つながっている部屋の1つである。道しるべの置き方が存在すれば,その配置を出力せよ。

解法

どの2部屋間も通路をいくつか通って行き来できるので,どの部屋からも部屋1に行くことができる。よって,必ず道しるべの置き方が存在する。

「今いる部屋からどの部屋に直接いけるか」というリストを予め作っておき,部屋1から次の操作を繰り返す。幅優先探索(BFS)と呼ばれるもの。

  • 今いる部屋から直接行ける各部屋について,まだ行ったことが無ければそれが部屋1までの最短経路なので,今いる部屋の番号をその部屋の道しるべの番号にし,「次に行きたいリスト」に追加する。

  • 今いる部屋から直接行ける部屋を全て見終わったら,「次に行きたいリスト」に一番昔に追加した部屋に移動する。

一番昔に追加した部屋に行くことで,部屋1から「まだ行ったことが無ければそれが部屋1までの最短経路」という条件を保ちながら部屋を廻ることが出来る。


注意点として,「次に行きたいリスト」は何度も「末尾に追加」,「最初の要素から取り出し」の操作は通常のリストではかなり時間がかかってしまう。

そこで,両端から追加・取り出しの操作が速い「deque」というデータ構造を使う。

deque.popleft()で最初の要素からの取り出し,deque.append(a)で末尾に要素を追加。これはいわゆる「キュー」と呼ばれるデータ構造だが,deque.pop()として末尾から要素を取り出すと「スタック」としても使える。

参考:Pythonのdequeでキュー、スタック、デック(両端キュー)を扱う | note.nkmk.me

解答

BFSの部分は頻出なのでどこかにメモしておくと一部分を変えるだけで済む。

コードを見る(クリックして下さい)

ABC168 D問題 解答

 

Submission #13316068 - AtCoder Beginner Contest 168

感想

今回のコンテストでは余弦定理がトレンド入りした

競プロ界隈ではコンテスト終了後に自分の解法をツイートする文化があり,B問題に余弦定理を使った人がいたり,「余弦定理の手があったか」ってツイートが短時間に大量に投稿された

その後余弦定理がトレンド入りすると一般人が「なんで余弦定理がトレンド入り??」というツイートを大量にして,一時はトレンド1位になった

コンテストが開催されるたびに何かがトレンド入りされるので面白い


AtCoder Scores の精進グラフが先週水色に入った

精進グラフと実際のレートは近くなることが知られているけど,筆者の場合もその傾向が出てる

f:id:monhime:20200518083939j:plain:w500

先週に引き続きAtCoder Problemsで表示されているAtCoderの過去問のdiffの値順(試験管は後回し)に解いていて,今は水diffの1250くらい

1日5問のペースで解き進めていて,今月中に水diff終わりそう