しょぼなまログ

ABC481の振り返り

2026/10/26
最終更新: 2026/10/26
タグ: article, ブログ, AtCoder, 競プロ
目次

SMBCプログラミングコンテスト #2(AtCoder Beginner Contest 481)の振り返りをします。

最初の記事でABCの振り返りなどを予定していますとか言っておきながら振り返り記事がなかったのと、今記事を書くモチベーションがあるので書きます。

来週からはコンテスト中に書いたろうかなとか言ってます。

結果

A-D 4完

負け

感想

A問題

while (AB > 0) AB /= 10 的なことをして桁を数えたが、実は 1≤A,B≤91 \le A, B \le 9 だから A + B >= 10 ? 2 : 1 でいいらしい...

B問題

端点が KK ぴったりの場合もまとめて処理する方式にしたけど、分けたほうが考えるのが楽だったっぽい。

C問題

コワスギ銀行過去に何回か出てるみたいで驚いた(コンテスト後の話)

map にぶち込むだけで終わり。これでええんか。

D問題

DはDijkstraのDまでは一瞬だったがダイクストラ下手すぎ侍出陣して1WA。MLEが出てたのでとりあえず枝刈っとけばええやろ精神(だめ)で力業AC。

どうやら < を <= にして seen[S] = 0; を削除したら通っていた模様。それくらい考えようね、かつ、ダイクストラ練習しようね案件。

E問題

これは下手です。

偏角ソート(名前があるのは知らなかった)を最初してたのに通らなかったので結果的に外積(式変形で出したので外積だとは思ってない)でソートする方法に変えてそれは上手くいかず、 atan2(y, x) に戻したら最後の30秒で float128_t の引数だと精度が上がることに気づいてしまい、死ぬ気でコーディングするも間に合わずCE。終了29秒後に提出したらなんとAC。これは下手。

まず浮動小数点で解こうとしたのが下手。次からは外積の符号で判定しようね(外積の符号が負かどうか見れば誤差無しで180度超えたかどうかの判定ができたという話)。

F以降

解きたい気持ちはやまやまですが、今日はこの辺で。

コンテスト中ちらっと見ただけなもんで...

終わりに

Dはみなさん01-BFSなるもので解いてたらしいけどそれもやっとこうかな

次回、目指せ爆勝ち入水

記録用

毎回ブランチを切るのがめんどくさくなったので本日はdevelop直コミットでお送りします。