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分

方針

全完以外ありえない

A - Next Alphabet

問題文

z でない英小文字 $C$ が与えられます。アルファベット順で $C$ の次の文字を出力してください。
制約
$C$ は z でない英小文字

解法

これは知っておくと便利なことですが、ASCII上ではアルファベットの文字コードは連続しています。
従って、答えは(char)(C+1)で求めることができます。
私の提出

感想

タイピング勝負かな？
ちなみに最速を望むならこれ3byteのACコード

B - Achieve the Goal

問題文

高橋君は $N$ 科目のテストを受けます。各テストは $K$ 点満点であり、点数はそれぞれ $0$ 以上の整数です。
高橋君は $N-1$ 科目のテストを既に受けており、 $i$ 番目の科目のテストの点数は $A_i$ 点でした。
高橋君の目標は、 $N$ 科目のテストの平均点を $M$ 点以上にすることです。
高橋君が目標を達成するためには、最後のテストで最低何点取る必要があるか出力してください。
達成不可能である場合は、代わりに -1 を出力してください。
制約

$2 \leq N \leq 100$

$1 \leq K \leq 100$

$1 \leq M \leq K$

$0 \leq A_i \leq K$

入力中のすべての値は整数である。

解法

平均が $M$ 点以上であるということは、合計点は $NM$ 点以上であるということです。
従って、各テストの合計を $sum$ とすると、 $\max(0, NM-sum)$ 点取れば良いことになります。
ただしこれの値が $K$ 以上ならば不可能なので $-1$ を出力します。
私の提出

感想

一瞬だけ $0$ 点以上を忘れてたけど、サンプルで落ちて安心したね。
やっぱりサンプルチェックは大事よ。

C - Welcome to AtCoder

問題文

高橋君は AtCoder のコンテストに参加しています。
このコンテストでは、 $N$ 問の問題が出題されます。
高橋君はコンテスト中に $M$ 回の提出を行いました。
$i$ 回目の提出は $p_i$ 番目の問題への提出であり、結果は $S_i$ (AC または WA) でした。
高橋君の正答数は、AC を $1$ 回以上出した問題の数です。
高橋君のペナルティ数は、高橋君が AC を $1$ 回以上出した各問題において、初めて AC を出すまでに出した WA の数の総和です。
高橋君の正答数とペナルティ数を答えてください。
制約

$N$ , $M$ , $p_i$ は整数

$1 ≤ N ≤ 10^5$

$0 ≤ M ≤ 10^5$

$1 \leq p_i \leq N$

$S_i$ は AC か WA のいずれか

解法

まず、HashMapを(まだACしていない問題, その問題のペナ数)とします。
最初に $(i, 0)$ を $i$ が $1$ から $N$ まで入れておきます。
すると、各 $p_i$ に対して

$p_i$ がHashMapに入っていない→AC済みなので飛ばす
$S_i$ がWA→ $(p_i, w)$ を $(p_i, w+1)$ に変える
$S_i$ がAC→ $(p_i, w)$ に対し、AC数に $+1$ , ペナルティ数に $+w$ した後でHashMapから $p_i$ を削除

となり、この操作は網羅的です。
計算量は ${\rm O}(N)$ ですが、工夫すれば ${\rm O}(M)$ でも解けます。(AC済みを別に管理するなど)
私の提出

感想

こういう問題は競プロ入門になって良いねって思う。

D - Maze Master

問題文

高橋君は、縦[tex:H マス、横 $W$ マスの $H \times W$ マスからなる迷路を持っています。
上から $i$ 行目、左から $j$ 列目のマス $(i,j)$ は、 $S_{ij}$ が # のとき壁であり、. のとき道です。
道のマスからは、上下左右に隣接する道のマスに移動することができます。
迷路の外に移動すること、壁のマスへ移動すること、斜めに移動することはできません。
高橋君は、道のマスからスタートとゴールを自由に決め、迷路を青木君に渡します。
青木君は、移動回数が最小になるようにしてスタートからゴールまで移動します。
高橋君がスタートとゴールの位置を適切に定めたとき、青木君の移動回数は最大で何回になるでしょうか？
制約

$1 \leq H,W \leq 20$

$S_{ij}$ は . か #

$S$ は . を $2$ つ以上含む

任意の道のマスから任意の道のマスまで $0$ 回以上の移動で到達できる

解法

青木君は最短経路を使うので、最短経路が最長の場所を知りたい訳です。
始点を決め打つと、そこから最長の位置は幅優先探索で求めることができるので、その最大を出力すれば良いです。
計算量は ${\rm O}((HW)^2)$ です。
私の提出
ちなみにこれはグリッドグラフの直径を求める問題であり、この問題はもっと高速なオーダーで解けるはずなのですが……誰か資料をお持ちでないでしょうか？

感想

こういう時のためにグリッドグラフ用ライブラリとか四方向移動ライブラリとかを作ったはずなのですが、何故か見つかりませんでした。
おそらくゲーム用のプロジェクト側において競プロライブラリに置き忘れたと思うのですが、使う場面で使えないのは痛いですね……。
まぁすぐかけるし別に良いっちゃ良いのですが。

E - Max-Min Sums

問題文

有限個の整数からなる集合 $X$ に対し $f(X)=\max X - \min X$ と定義します。
$N$ 個の整数 $A_1,...,A_N$ が与えられます。
このうち $K$ 個を選び、それらからなる集合を $S$ とします。同じ値であっても添字が異なる要素を区別すると、そのような選び方は ${}_N C_K$ 通りありますが、その全てについての $f(S)$ の合計を求めてください。
答えは非常に大きくなる可能性があるので、 $\bmod 10^9+7$ で出力してください。
制約

$1 \leq N \leq 10^5$

$1 \leq K \leq N$

$|A_i| \leq 10^9$

解法

まず、別に順番が関係ないので $A_i$ はソートしておきます。
各数字について、その数が最小値、最大値として何回使われるかを考えれば、答えを求めることができます。
まず最大値の方で考えると、最大値が $i$ 番目、最小値が $j$ 番目であるとき、残りの $K-2$ 個は最大値と最小値の間にある値から自由に選べるので、これは ${}_{i-j-1}C_{K-2}$ 通りあります。
従って最大値の合計は $\sum_{i=K}^{N} A_i \sum_{j=1}^{i-K+1} {}_{i-j-1}C_{K-2}$ となります。
最小値の合計も同様に考えると $\sum_{i=1}^{N-K+1} A_i \sum_{j=i+K-1}^{N} {}_{j-i-1}C_{K-2}$ となり、これを求めれば答えが分かることになります。
ところで、 $_{j-i-1}C_{K-2}$ の合計は累積和を用いると前もって計算しておくことができるので、 $i$ を決め打った時の計算量が ${\rm O}(1)$ になります。
従って、この問題はソートがボトルネックとなり ${\rm O}(N \log N)$ で解くことができました。
私の提出

感想

また言い換えると解ける問題で、なんか三日連続で同じ問題を出された気分になっています。
この手の問題は得意だから良いけど、うんざりしそう？
ところで、サンプルチェックを怠ったので $K=1$ の時に不正引数例外で弾かれました。(ちなみにこのケースの答えは $0$ )
ちゃんとサンプルチェックをするんじゃなかったの？

F - Enclose All

問題文

平面上の $N$ 個の点 $(x_i, y_i)$ が与えられます。
これら全てを内部または周上に含む円の半径の最小値を求めてください。
制約

$2 ≤ N ≤ 50$

$0 ≤ x_i ≤ 1000$

$0 ≤ y_i ≤ 1000$

与えられる $N$ 点は全て異なる

入力で与えられる値は全て整数

解法

まず、全ての点を内部に含む円は、明らかに周上に点が触れるまで半径を小さくしても問題ないことが分かります。
また、1点を周上に含む円は、その1点が周上にある状態を維持したまま円を小さくすることができます。
次に、2点を周上に含む円を考えます。
これは、もし2点が円の中心を挟んで丁度向かいの位置にある場合、円は一意に定まります。
またそうではない場合、円を小さくしながら2点が向かいの位置に近くなるような方向に回してあげるともっと小さくなることが分かります。
最後に、3点を周上に含む円を考えます。
実はこれは(3点が一直線上に無ければ)一意に定まるので、後はこの円の中に全ての点が含まれるか調べれば良いです。
なお、3点が一直線上にある場合、どうやってもその3点を周上に置くことはできないので無視して大丈夫です。
従ってこれまでの考察を纏めると、

任意の2点に対して、その2点が円の向かい側にあるとしたときに全ての点が円に含まれるならば解の候補とする
任意の3点に対して、その3点が一直線上じゃないかつ3点から構成できる円に全ての点が含まれるならば解の候補とする

この2つによって全ての解を調べているので、問題ないことが分かります。
計算量は3点決め打ち+解の正当性調査 ${\rm O}(N)$ で合計 ${\rm O}(N^4)$ となります。
私の提出

感想

なんだこれ、幾何面倒だけど
誤差の関係とかいろいろ考えなきゃいけないし方程式は解かなきゃいけないし、えー
予めユークリッド距離を求めるライブラリがあったのだけが救いね、次は連立方程式を解くライブラリがあった方がいいのかな。

結果

oooooo 6完(2100点) 0:45-3:27-7:37-18:08-38:23(1WA)-64:29 / 69:29
196位パフォーマンス: 2046

感想

競プロ感はあるセットだったし、別に良いとは思うけど……若干面倒かなって思うかな？
まぁただ典型知識(最後は本当か？)のセットでもあるのでちゃんと学んでおきたいものよね。