41. AtCoder参加記録（AtCoder Beginner Contest 235）
前回の記録が出ていたので、とりあえず現状から。
5回参加しないと正確なレーティングが出ないようなので暫定ですが、こんな感じです。パフォーマンスは 983 だったので、このくらいのパフォーマンスを出し続けられれば、およそ緑に着地するはずです。
今回もビギナー向けのABCに参加しました。
結果は、ABCD完答・EFGEx未回答です。Dで1回ミスりました。
各問題の感想です。
A
何てことはない問題ですが、競技プログラミング特有の緊張感からか、入力の扱いでちょっと焦ってしまいました。どうも緊張が取れないですね。5分ほどで解けたので及第点だとは思います。
B
やることが非常に単純なので、その通りに書けば良いだけです。この辺りから緊張がほぐれてきました。
C
クエリごとに計算するのでは、制約的にたぶん間に合わないです。
問題の性質上、あるクエリに対しての出力は常に一定となる（クエリによって状態が変化しない）ので、初めに答えを全て計算しておき、クエリが来たらキャッシュから回答します。
答えの計算は 個の数列を順番にスキャンするだけで出来るので、これで十分です。
D
あー、探索系の問題だなーと思いました（前回解いた問題には無かったタイプ）。
探索用のライブラリは特に書いていなかったので、素直に再帰で解きました。再帰を使うと深さ優先探索になるので、問題的にこれで十分だと思いました。
問題は探索を打ち切る条件です。判定のしやすさを考えて、以下のような条件で打ち切ることにしました。
の桁数が
より大きい
- 雑ですが、とりあえず ToString して Length を見てやれば良いです
- 今までの探索で既に見た数である
これで提出したのですが、1つだけ WA になりました。
少し考えたのですが、太文字の判定方法に問題がありました。深さ優先探索なので、最初に見つけた経路が最短手数である保証はありませんでした。普通に迂闊でした。
というわけで、「今までの探索で既に見た数である、かつ、手数が最短手数候補より大きい」という条件に変更して無事通せました。
E
あー、グラフ系の割と基本的な問題だなーと思いました。
ただ、やはりグラフ用のライブラリも書いていなかった上、流石にいきなり書けるほど知識もなかったので、最初はこれを飛ばしてF問題を見ていました。しかし、Fが無理そうだったのでEに戻り、ダメ元で実装を進めていましたがやはり間に合いませんでした。
これは取りたかった問題なので、しっかり勉強しておきます。
F
尋常じゃない桁数が制約になっているので、文字列でどうにかすべきパターンです。
…ということしか分かりませんでした。少し考えましたが方針が立たないので、諦めてEに戻りました。
G, Ex
見てないです。
反省点としては、
- 前回ほど無駄な時間を掛けることがなく、この点は成長を感じた
- 入力処理がダルいので何か良い感じにユーティリティ作っておきたい…
- 少しずつライブラリを充実させていこう
という感じです。
