ABC166

ABC166に参加しました。

三日連続更新にはしっかり失敗しました。

5完でパフォが1400だったのでとても嬉しかったです。Fはなんとなく分かったのですが、実装はできませんでした。解説を見てみたところ、解き方はあっていたのですが2020/5/8時点でまだ実装しきれていません。

AtCoder Beginner Contest 166 - AtCoder

All Submissions - AtCoder Beginner Contest 166

A-A?C

入力を受け取ったら”ABC"と一致するかどうかを調べて、一致すれば”ABC"、しなければ”ARC"を出力します。制約が”ABC""ARC"のどちらかになっているので片方を調べるだけでいいです。

B-Trick or Treat

人数分の配列を用意しておいて、入力を受け取るたびに持っている子のお菓子の数を1ずつ増やしていきます。最後に持っているお菓子の数が0の子を数えます。

C-Peaks

それぞれの展望台について一つずつ確認していくと結構時間がかかりそうです。そこでM本の道について一つずつ見ていくことにしました。bool型の配列で各展望台が良い展望台かを管理します。配列はtrueで初期化しておいて、道iについて確認するたびに条件を満たさない展望台はfalseにしていきます。この時、同じ高さにある展望台はどちらもいい展望台ではなくなります。最後にいい展望台の数を数えて出力します。

D-I hate Factorization

一目見ただけではよく分からなかったので、とりあえずどのくらいの大きさまでがA,Bの候補になるのか考えたところ、100の5乗で10の9乗よりも大きくなることにすぐ気が付きました(当たり前のことですが…)。A,Bどちらもせいぜい三桁程度の範囲しか動かないのであれば、全探索でも十分に間に合います。A,Bは整数なので、-300から300までの範囲で全て確認して出力しました。

E-This Message Will Self-Destruct in 5s

この問題もC問題同様全て調べるのでは時間がかかりすぎるので、ほかの方法を考えました。条件は参加者x,y(y>x)についてy-x=Ay+Axとなることです。これを式変形すると、x+Ax=y-Ayとなります。そこで、mapに身長と番号の差、その人数を格納していきます。その後、各参加者の身長と番号の和をそれぞれ求め、mapに格納されている差と一致していた場合はその人数を加算していきます。全員分を調べ終わったところで合計を出力します。

F-Three Variables Game

とりあえずいくつか具体的な数を決めて動かしてみました。結局、条件を整理すると、三つとも0である場合はもちろん不可能です。また、二つが0であり、もう一つが1の場合は、非負の範囲で1を引けるものは常に1つしかないため動かし方は一意に定まるので最後まで確認すれば可能かどうかが分かります。それ以外の場合、初めに動かすことが出来れば選択するどちらかは1以上の状態を常に作ることができます。動かし方は、どちらも1の場合は次に使う予定のほうに1を足します。それ以外の場合は小さいほうに1を足します。

この方針で解けるはずなのですが、実装がぐちゃぐちゃのままです…。明日中にはACしたいと思います。

今回は以上です。結果はかなり良かったのでこの調子でやっていきたいです。ちょっとだけ、ちょろ～っとだけFも解ききれたらなという気持ちになりました。