ABC-308 振り返り
CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)
問題ページ: AtCoder Beginner Contest 308 - AtCoder
当面の目標
水色
全体の振り返り
A,B完答。 C,DはそれぞれWAとLTEで完了できなかった。残念。 それぞれPythonでは対応がし辛い問題だった。 C++への移行を考えたほうがいいかもしれない。 C++でやるとなると、競プロ専用のマクロみたいなのが多く混ざってきて、特殊対応している感あってあまり気が進まなかったのだけど・・・。
追記: 学び
- コマンドライン引数の受け取りは、中継用のリストを利用せずに直接利用するリストに流し込むほうが有意に早い
- データの溜め込みはリストよりもタプルにしたおいたほうが早い
- グリッドの現在地店から次地点4箇所の探索について、
filter
を使うよりもdx[4], dy[4]の配列をforで回したほうが早かった。テーストによっては2倍以上、1.4sec以上差が開いているものもあり。
A
条件式を並べるだけ。
B
PythonのDictではdefaultdict
を使わなくても、
キーがなかった場合のデフォルト値が設定できる。
get
を利用して要素にアクセスする。
d.get("a", default_val)
C
最初デバッグ用のprint
が残っていたのに気が付かず数回のWA。
その後printを修正しても、数件がWAのまま解決できなかった。
Zereo Divisionがあるのかなとか色々探しても解決できず。
割り算の箇所で丸め込みの誤差が発生しているため、割り算を排除する形で計算を行えば解決していた。
確率と人のindexそれぞれを用いてソートするため、ソートに関する比較関数内でIFを利用する必要があるが、標準のkey指定では対応できない。
from functools import cmp_to_key
を利用することで対応可能。
Pythonのデータソートについて検証してみた | DevelopersIO
D
アルファベットの順に並んでいる道を探してゴールまで辿り着く問題。 訪問済みの箇所を塗りつぶしていく形でDFSすれば良いのまではすぐに思いついた。 実装苦労するかと思ったが意外と楽だった、15分ほど。
再帰関数の呼び出し回数制限でWAが1回。 下記が必要だった。
import sys sys.setrecursionlimit(10**6)
ここからLTE1件が最後まで解決できなかった・・・。 解答例を見てもPythonでやっている例はあまりない。C++じゃないと厳しかったか?