ABC242振り返り
AtCoder Beginner Contest 242に参加しました。
結果
ABC3完、パフォーマンスは879でした。1時間かけてD問題に挑みましたが、解けず。
レーティングの推移を見ると右肩上がりに見えますが、これは登録直後にかかるマイナス補正が外れつつあるためです。各コンテストのパフォーマンスは毎回ほぼ800台で、全然成長していない?
言語
今まではPythonを使っていましたが、今回はKotlinで書きました。本番までに過去問やCodewarsで練習していたので、とくに言語が変わったことによる苦労は感じませんでした。まあ、そもそもPythonに習熟していたわけでもないしね。
各問題振り返り
A - T-shirt
実数を扱う問題はあまり経験がありませんでした。大小比較の時に誤差が心配だったので、整数型で受け取り、割り算の時だけ実数に変換しました。
B - Minimize Ordering
ソートするだけ。
C - 1111gal password
問題を一読した時には、『典型90問』の069-Colorful Block 2と同様の問題かと思いました。しかし2~8の隣は3パターンあるのに、1と9の隣は2パターンのため、うまく計算で一撃では求まりそうにありません。
制約がN <= 10^6であるので、余裕をもってN回ループを回せそうです。ある桁のパターン数は隣の桁の数字によって決まるので、DPで解けました。
D - ABC Transform
二分木のような構造や、A-B-Cが循環しているということには気づきましたが、回答までたどり着けませんでした。制約が大きすぎる!
まとめ
- ✅ C問題をDPで解けるという発想ができた。
- ✅ 制約から計算量を見積もって、DPで間に合うことを確認してから実装できた。
- ❌ D問題歯が立たなかった。正直何が分かっていれば解法までたどり着けたのかもよくわからない。でも難しすぎるからしょうがないね。
Asprovaプログラミングコンテスト
3/6から第8回Asprovaプログラミングコンテストというヒューリスティック型のコンテストが始まるそうです。ヒューリスティックコンテストは一度だけ(AHC008)参加したことがあるのですが、その時は考えた動きをするコードを実装することができず、結局ランダムな動きをするコードを提出して終わってしまいました。
次はランダムよりはマシな得点を取ることを目標にして参加してみようかな。