90. AtCoder参加記録（AtCoder Beginner Contest 245）

現状です。11回参加でレート 941 です（14回参加するまでレート補正期間中）。

今回はパフォーマンス 1144 でした。

ABCDを通して、EはWA、FGExは未解答です。Dで2ペナです。

各問題の感想です。

A

開始直後に問題一覧ページに飛ぶと何故か403エラーが出て、30秒ほど時間を取られました。

見た瞬間、「凡ミスが怖い問題だな…」と思いました。そのため、Aにしては念入りにチェックしてから提出しました。

B

HashSet で数列の要素を記録して、非負整数を前から順に探索して存在しないものを出せばOKです。HashSet じゃなくて bool 配列でも良いでしょう。

これも凡ミスが怖い問題で、2001が答えになる可能性があります…と思ってたんですが、よく制約を読むと なので大丈夫でしたね。

安全に行くなら無限ループの中で判定する方が良かった気がしました。

C

条件を読むと、連続する2つの要素のみが関連しています。 だけを考えてみましょう。 番目の要素が決定しているとして、 番目の要素は条件を満たすもの全てを「候補」とすればよいことが分かります。ここで「候補」が選べなかった場合は「No」が答えになります。

次に、 番目も同様に考えられることが分かります。ここで 番目の要素は決定していないのですが、たとえ「候補」が2つあっても先ほどの考察からどちらを選んでも良いわけなので、どちらも決定しているとみなして 番目の「候補」を出せばよいです。後から辻褄を合わせればよいわけです。今回は存在判定だけなので具体的な決定項を出す必要すらありません。

D

…という式から、定数項から順に芋づる式に導出する方法を取りました。

ただ、この方法はゼロ除算の扱いがめちゃくちゃ面倒くさいので、普通に多項式の割り算で高次の項から求めた方が楽です。

面倒くさい例外処理を色々と書いて、2 WAで何とか通せました。

E

縦の長さを して横の長さと足し合わせればまとめて二分探索できるのでは？と考えたのですが、縦の長さが十分で横の長さがダメなパターンで上手く行きませんでした。

この方針以外思いつかなかったので色々やっていたのですが、結局 TLE が取れず終了しました。

F

終了10分前くらいに見たのですが、これ強連結成分分解では…となってこっちの方が解けそうだったことに気付きました。先にE/F問題を両方見ておくべきですかね…。

G, Ex

見てないです。

実は、今回は頭痛がひどくて全然頭が回っていない状態で挑んでいました。なんで Rated 参加にしたのかというと、コンディションによってどの程度出来に違いが出るのか確かめたかったのと、レート補正期間を早く抜けたかったのがあります。

体調不良による影響ですが、まず問題に対して最初に思い浮かんだ方針以外を思いつく余力がありませんでした。考えると頭痛が増すので、最初の方針をざっと実装して、細かいところを詰めるのもしんどいのでとりあえず提出して、コケたら微修正を繰り返す…ということをやっていました。E問題は方針から間違っていたので、それが悪影響した感じではあります。

また、短期記憶のスペースが狭くなったのか、直前に解いた問題を完全に忘却していました。これは目の前の問題に集中できるという点で逆に良かったかもしれません。

パフォーマンス自体は思ったほど悪くなく、妥当なところに収まった気がします。体調が良ければ普通に水パフォ出てたと思いますが、まぁ仕方ないです。