つちのこの日記

競プロと音ゲーがメインです。

AtCoder Beginner Contest 205 一言解説

30分で解き終わって暇だったので書きます。

A.kcal

$\frac{AB}{100}$ を出力します。

B. Permutation Check

与えられた配列をsortして、 $1,2,\dots,N$ になってるか確かめましょう。 std::iotaを用いると配列 $(1,2,\dots,N)$ が得られるのでこれを用いるのが簡潔でしょう。

C.POW

$C$ の偶奇で場合分けしましょう。 $C$ が奇数ならば $A,B$ の、 $C$ が偶数ならば $|A|,|B|$ の大小関係を判定すればよいです。

D.Kth Excluded

$X$ が小さい方から $K$ 番目 $\leftrightarrow X$ より小さい数が $K- 1$ 個あるという同値変形を行いましょう。

$X$ を二分探索し、判定にはsetのlower_boundを用いることでこの問題に答えられます。

E.White and Black Balls

カタラン数を知っていますか?カタラン数は競プロで頻出なので、知らなかった場合は覚えておくと良いでしょう。

知っていればあとはその考えを用いることで答えが $\binom{N+M}{N}–\binom{N+M}{N-K- 1}$ となります。

$M+K<N$ ならば答えが $0$ になることに注意しましょう。

F.Grid and Tokens

蟻本210ページのDiningとほぼ同じ問題です。辺を湧き出し口→行番号→駒→駒→列番号→吸い込み口の順番で貼ります。

aclのmf_graphを用いると実装が簡潔でしょう。