イバコの生存記録

毎日更新が目標。「その日一番考えたこと」を書き留めていきます。

41. AtCoder参加記録(AtCoder Beginner Contest 235)

前回の記録が出ていたので、とりあえず現状から。

f:id:ibako_piyo:20220115230841p:plain

 

f:id:ibako_piyo:20220115230055p:plain

 

5回参加しないと正確なレーティングが出ないようなので暫定ですが、こんな感じです。パフォーマンスは 983 だったので、このくらいのパフォーマンスを出し続けられれば、およそ緑に着地するはずです。

 

今回もビギナー向けのABCに参加しました。
結果は、ABCD完答・EFGEx未回答です。Dで1回ミスりました。

f:id:ibako_piyo:20220115230739p:plain

 

各問題の感想です。

A

何てことはない問題ですが、競技プログラミング特有の緊張感からか、入力の扱いでちょっと焦ってしまいました。どうも緊張が取れないですね。5分ほどで解けたので及第点だとは思います。

B

やることが非常に単純なので、その通りに書けば良いだけです。この辺りから緊張がほぐれてきました。

C

クエリごとに計算するのでは、制約的にたぶん間に合わないです。
問題の性質上、あるクエリに対しての出力は常に一定となる(クエリによって状態が変化しない)ので、初めに答えを全て計算しておき、クエリが来たらキャッシュから回答します。

答えの計算は  N 個の数列を順番にスキャンするだけで出来るので、これで十分です。

D

あー、探索系の問題だなーと思いました(前回解いた問題には無かったタイプ)。

探索用のライブラリは特に書いていなかったので、素直に再帰で解きました。再帰を使うと深さ優先探索になるので、問題的にこれで十分だと思いました。

問題は探索を打ち切る条件です。判定のしやすさを考えて、以下のような条件で打ち切ることにしました。

  • x の桁数が N より大きい
    • 雑ですが、とりあえず ToString して Length を見てやれば良いです
  • 今までの探索で既に見た数である

これで提出したのですが、1つだけ WA になりました。
少し考えたのですが、太文字の判定方法に問題がありました。深さ優先探索なので、最初に見つけた経路が最短手数である保証はありませんでした。普通に迂闊でした。

というわけで、「今までの探索で既に見た数である、かつ、手数が最短手数候補より大きい」という条件に変更して無事通せました。

E

あー、グラフ系の割と基本的な問題だなーと思いました。

ただ、やはりグラフ用のライブラリも書いていなかった上、流石にいきなり書けるほど知識もなかったので、最初はこれを飛ばしてF問題を見ていました。しかし、Fが無理そうだったのでEに戻り、ダメ元で実装を進めていましたがやはり間に合いませんでした。

これは取りたかった問題なので、しっかり勉強しておきます。

F

尋常じゃない桁数が制約になっているので、文字列でどうにかすべきパターンです。

…ということしか分かりませんでした。少し考えましたが方針が立たないので、諦めてEに戻りました。

G, Ex

見てないです。

 

 

反省点としては、

  • 前回ほど無駄な時間を掛けることがなく、この点は成長を感じた
  • 入力処理がダルいので何か良い感じにユーティリティ作っておきたい…
  • 少しずつライブラリを充実させていこう

という感じです。