AtCoder Beginner Contest 151
AtCoder Beginner Contest 151(ABC151)に参加しました!
解けた問題だけ解説をしていきますー
要項
AtCoder Beginner Contest 151
rated ~1999
2020/1/12(日) 21:00 ~ 22:40 (100分)
100-200-300-400-500-600 (6問)
ペナルティ: 5分
方針
全完以外ありえない
B - Achieve the Goal
問題文
高橋君は
科目のテストを受けます。各テストは
点満点であり、点数はそれぞれ
以上の整数です。
高橋君は科目のテストを既に受けており、
番目の科目のテストの点数は
点でした。
高橋君の目標は、科目のテストの平均点を
点以上にすることです。
高橋君が目標を達成するためには、最後のテストで最低何点取る必要があるか出力してください。
達成不可能である場合は、代わりに-1
を出力してください。制約
- 入力中のすべての値は整数である。
解法
平均が点以上であるということは、合計点は
点以上であるということです。
従って、各テストの合計をとすると、
点取れば良いことになります。
ただしこれの値が以上ならば不可能なので
を出力します。
私の提出
感想
一瞬だけ点以上を忘れてたけど、サンプルで落ちて安心したね。
やっぱりサンプルチェックは大事よ。
C - Welcome to AtCoder
問題文
高橋君は AtCoder のコンテストに参加しています。
このコンテストでは、問の問題が出題されます。
高橋君はコンテスト中に回の提出を行いました。
回目の提出は
番目の問題への提出であり、結果は
(
AC
またはWA
) でした。
高橋君の正答数は、AC
を回以上出した問題の数です。
高橋君のペナルティ数は、高橋君がAC
を回以上出した各問題において、初めて
AC
を出すまでに出したWA
の数の総和です。
高橋君の正答数とペナルティ数を答えてください。制約
,
,
は整数
は
AC
かWA
のいずれか
解法
まず、HashMap
最初にを
が
から
まで入れておきます。
すると、各に対して
がHashMapに入っていない→AC済みなので飛ばす
が
WA
→を
に変える
が
AC
→に対し、AC数に
, ペナルティ数に
した後でHashMapから
を削除
となり、この操作は網羅的です。
計算量はですが、工夫すれば
でも解けます。(AC済みを別に管理するなど)
私の提出
感想
こういう問題は競プロ入門になって良いねって思う。
D - Maze Master
問題文
高橋君は、縦[tex:H マス、横
マスの
マスからなる迷路を持っています。
上から行目、左から
列目のマス
は、
が
#
のとき壁であり、.
のとき道です。
道のマスからは、上下左右に隣接する道のマスに移動することができます。
迷路の外に移動すること、壁のマスへ移動すること、斜めに移動することはできません。
高橋君は、道のマスからスタートとゴールを自由に決め、迷路を青木君に渡します。
青木君は、移動回数が最小になるようにしてスタートからゴールまで移動します。
高橋君がスタートとゴールの位置を適切に定めたとき、青木君の移動回数は最大で何回になるでしょうか?制約
は
.
か#
は
.
をつ以上含む
- 任意の道のマスから任意の道のマスまで
回以上の移動で到達できる
解法
青木君は最短経路を使うので、最短経路が最長の場所を知りたい訳です。
始点を決め打つと、そこから最長の位置は幅優先探索で求めることができるので、その最大を出力すれば良いです。
計算量はです。
私の提出
ちなみにこれはグリッドグラフの直径を求める問題であり、この問題はもっと高速なオーダーで解けるはずなのですが……誰か資料をお持ちでないでしょうか?
感想
こういう時のためにグリッドグラフ用ライブラリとか四方向移動ライブラリとかを作ったはずなのですが、何故か見つかりませんでした。
おそらくゲーム用のプロジェクト側において競プロライブラリに置き忘れたと思うのですが、使う場面で使えないのは痛いですね……。
まぁすぐかけるし別に良いっちゃ良いのですが。
E - Max-Min Sums
問題文
有限個の整数からなる集合
に対し
と定義します。
個の整数
が与えられます。
このうち個を選び、それらからなる集合を
とします。同じ値であっても添字が異なる要素を区別すると、そのような選び方は
通りありますが、その全てについての
の合計を求めてください。
答えは非常に大きくなる可能性があるので、で出力してください。
制約
解法
まず、別に順番が関係ないのではソートしておきます。
各数字について、その数が最小値、最大値として何回使われるかを考えれば、答えを求めることができます。
まず最大値の方で考えると、最大値が番目、最小値が
番目であるとき、残りの
個は最大値と最小値の間にある値から自由に選べるので、これは
通りあります。
従って最大値の合計はとなります。
最小値の合計も同様に考えるととなり、これを求めれば答えが分かることになります。
ところで、の合計は累積和を用いると前もって計算しておくことができるので、
を決め打った時の計算量が
になります。
従って、この問題はソートがボトルネックとなりで解くことができました。
私の提出
感想
また言い換えると解ける問題で、なんか三日連続で同じ問題を出された気分になっています。
この手の問題は得意だから良いけど、うんざりしそう?
ところで、サンプルチェックを怠ったのでの時に不正引数例外で弾かれました。(ちなみにこのケースの答えは
)
ちゃんとサンプルチェックをするんじゃなかったの?
F - Enclose All
問題文
平面上の
個の点
が与えられます。
これら全てを内部または周上に含む円の半径の最小値を求めてください。
制約
- 与えられる
点は全て異なる
- 入力で与えられる値は全て整数
解法
まず、全ての点を内部に含む円は、明らかに周上に点が触れるまで半径を小さくしても問題ないことが分かります。
また、1点を周上に含む円は、その1点が周上にある状態を維持したまま円を小さくすることができます。
次に、2点を周上に含む円を考えます。
これは、もし2点が円の中心を挟んで丁度向かいの位置にある場合、円は一意に定まります。
またそうではない場合、円を小さくしながら2点が向かいの位置に近くなるような方向に回してあげるともっと小さくなることが分かります。
最後に、3点を周上に含む円を考えます。
実はこれは(3点が一直線上に無ければ)一意に定まるので、後はこの円の中に全ての点が含まれるか調べれば良いです。
なお、3点が一直線上にある場合、どうやってもその3点を周上に置くことはできないので無視して大丈夫です。
従ってこれまでの考察を纏めると、
- 任意の2点に対して、その2点が円の向かい側にあるとしたときに全ての点が円に含まれるならば解の候補とする
- 任意の3点に対して、その3点が一直線上じゃないかつ3点から構成できる円に全ての点が含まれるならば解の候補とする
この2つによって全ての解を調べているので、問題ないことが分かります。
計算量は3点決め打ち+解の正当性調査で合計
となります。
私の提出
結果
oooooo 6完(2100点) 0:45-3:27-7:37-18:08-38:23(1WA)-64:29 / 69:29
196位 パフォーマンス: 2046
感想
競プロ感はあるセットだったし、別に良いとは思うけど……若干面倒かなって思うかな?
まぁただ典型知識(最後は本当か?)のセットでもあるのでちゃんと学んでおきたいものよね。