ARC108の感想

AtCoder Regular Contest108に参加したのでその感想を書いていきます。

問題はこちらから。

Tasks - AtCoder Regular Contest 108

結果はこんな感じでした。

3213 / 4237 でパフォーマンスは364でした。aしか解くことができませんでした。悔しいですね。

今回の感想は短くなりますが、お付き合いいただけると幸いです。

ではいきます。

A問題

 n+m = s, n*m=p となる正の整数(n,m)が存在するかどうかを判定します。ただし、制約は 1<= s,p <= 10^12です。

制約が厳しいの、s,p を10^12まで回すのはできないなーとかをまず考えてました。そのあと、文字が2つあると面倒くさいので、片方を消しました。

m^2-sm+p = 0

これが、解をもつから、判別式をもちいて

0 <= D = s^2-4p

とすれば、for文回すことなく、一発で判定を行えます。試験中に「今日冴えてるな」と自分で感心してました。

ただし、上記の方法で求まるのは実数解を持つかどうかです。ということで、いままでの議論はすべて嘘です。

次に10^12の範囲を絞りたいなと考えました。m*(s-m) = p の条件であれば、sqrt(10^12)= 10^6でいけるなとなりました。そのため、whlile文で上記の判定式を回しました。

B問題

文字列中に「fox」という部分文字列があったら消去をします。消去後の文字列の長さを求めます。

foxという文字を消した後に、その前後の文字で新たなfoxが作れるときはどうしようかなーってとっても悩みました。

f - fox -ox
fo -fox - x
f - fox- o -fox - x

こうなってたら全部消えます。さらに言うなら、これらを組み合わせて

f-f-fo-f-fox-o-fox-x-x-o-fox-x-ox

となっていても全部消えます。はじめは文字列の場合分けを再帰関数にて実装すれば解けそうだなと思いました。ただ、実装がうまくいきませんでした。

いろいろと考えた結果、そもそも管理しなければいけない文字って、fかfoがfoxの前にどんな感じに存在しているかということを思いました。

ということで、vectorにてfとfoをスタックするような構造を用いました。

foxまでは、fかfoをスタックする。fox後はスタックされているものと整合が取れるかをチェックする。

という感じで実装したら解けました。コンテスト終了5分後の出来事でした。

また、コンテスト後に解答を見たら3行でシンプルに書かれてました。驚きました。

今回は残念な結果となりました。とても残念です。

でも、今回B問題に70分ぐらいかけましたが、色々と考えて、解けたときのあの感じは気持ちよかったです。まだまだ楽しく取り組んでいます。

明日はBeginner Contestがありますので、切り替えて楽しく臨みたいと思います。