ABC123 感想

ABC123

4月6日（土）21:00~21:40に開催されたABC123に参加しました。この記事はその記録兼復習です。

atcoder.jp

また、私のコードはGitHubにあります。参考にどうぞ。

github.com

A - Five Antennas

一組でも距離が離れてる組み合わせがあるとダメなので、一番遠い組だけを見てやれば良い。 私はなぜかはじめ二番目に距離が離れてるやつでやってしまいWAでした。

B - Five Dishes

はじめは、どんな料理が来てもそれより大きい10の倍数を加算していって通るかと思ってやったらWA。 よくよく見てみると、最後のやつだけは料理が来た瞬間に終了することを忘れてた。 そのため、10の倍数との差が最も大きなやつを最後に持っていけば良し。 2回くらいWAしてしまった。

C - Five Transportations

複数の交通機関を乗り継いで目的地に行かせるには最低何分かかるかという問題。 Nが小さければ適当に計算してやれば良いのだけれども、おそらくそれでやるとTLEになるため工夫する必要がある。 この場合は最も輸送能力が少ない交通機関に律速されるのでそれが何往復するかということに着目すれば大丈夫。 余りがある場合の処理も忘れずにすればOK

long long ans = n / min + 4;
  if (n % min != 0) {
    ans++;
  }

私はこうやりました。最小の輸送能力minで人数を割った商 - 1 + 5(分)とすることで「余りを除いた乗客」が何分間で輸送されているかを計算しています。-1は一番最初の乗客グループは0分に移動し始めること、5分は移動し始めてから終わるまでに5分あることを示しています。 あとは余りグループがあるときは一分遅れて到着するのでそれを考えて終わりです。 10¹⁵なのに、minの初期値を10¹⁴+1とするタイポにより、WAが発生。

D - Cake 123

コンテスト中には解けなかったので終わってから解きました。 xyz種類の値から上位kまでを出力すればいいという言ってしまえば簡単な問題ですが、真面目に全探索しているとTLEになってしまうため、工夫していく必要があります。解説によると何個か方法があるらしいです。今回はX、Yから選んで確実に必要ないk+1番目以降を捨ててから、Zを選んでいくという方法をとりました。これでなんとか制限に収まるようです。こんな感じに制約に収まるように少しづつ処理していくというのはよく見る手法ですので、きちんとマスターしていきたいところ。

感想

A、Bでくだらないミスを連発し、CもタイポでWAするというアホっぷり。なぜレートが下がらなかったのか不思議なレベル。ただ、最近三回くらい連続でCまで解けているので成長はしている実感はあります。次はDもちゃんと解き切れるように精進を重ねていきたいですね。そして次こそは緑に昇格していきたいですね。