71. AtCoder参加記録（AtCoder Beginner Contest 239）
現状です。6回参加でレート 694 です。レート正常化まであと3回（のはず）。
今回はパフォーマンス 1120 でした（自己ベスト更新！）。ABCDEを通して、FGExは未解答です。Bで1ペナ、Eで2ペナです。
各問題の感想です。
A
なんか色々書いてますが、要するに書いてある式をそのまま出せば良いだけです。
B
今日あんまり頭が働いてなくて、1回 WA を出してしまいました…。
とりあえず long で扱える範囲です。基本的には普通に整数除算すれば良いんですが、負の数については理想的な挙動をしません。X が 10 で割り切れるかで場合分けが要るのですが、ここで条件式に「除算後の値」を使うというミスをして、-9 ～ -1 で上手く行かない解答を出してしまいました。
どこで変な値を出しているのか分からず、解決に5分ほど悩みました…。
C
図が無ければそこそこ難しかったかもですが、ここまで丁寧に説明されると「与えられた点から8点を導出し、一致するものがあるか判定せよ」と言われているようなものです。
D
最適戦略と言われるとちょっと難しく感じますが、要するに、以下のようなゲームです。
- 高橋くんの候補のうち、「それを出すと、青木くんがどの候補を選んでも素数に出来ない数」があれば高橋くんの勝ち
- それ以外なら青木くんの勝ち
制約から、見るべき数は 2 ～ 200 です。これについて予め素数テーブルを作っておきます。制約がかなり緩いので普通にやっても行けそうですが、エラトステネスの篩が一番スマートでしょう。
E
部分木に含まれる頂点に書かれた数を大きい順に並べることを考えてみます。考察すると、これは「根の値」と「"根の子"を根とする部分木集合から得られるリスト集合」から作れることになります。これは単純な深さ優先探索で表現できます。大きい順なので Priority Queue を使うと間に合いそうです。
あとは探索を行いつつ、葉から順番にリストを構築していきます。やっぱり頭が冴えていなくて、変なミスを連発して2ペナ喰らいましたが、どうにか通せました。
ちょうど今年初め、初参加の ABC でも Priority Queue を使う問題が出ました。積み重ねの成果が出た感じで嬉しいです。
F, G, Ex
E終了時点で残り10分とかだったので、眺めていたくらいでした。
前回の反動からか、簡単めの問題が多かったかな？と思いました。
Eは今の自分からすれば「時間内にギリギリ通せるか？」くらいの難易度で、ここを通せたのは成長を感じられて嬉しかったです。ただ、頭の調子が悪く変なミスが多かったのはちょっと悲しかったですね。
明日もABCがありますが、時間があれば参加したいと思います。結構微妙なところです…。
