🕒 2021/06/14

ABC205感想戦

🍉

ABC205 に参加しました。結果は、Dまでできて、Eは格闘したけど思いつけず。画像はコンテスト中に書いていたメモです。

A問題 は、A / 100 * B をやる。1分。

B問題 は、与えられた数列が、 $1$ から $N$ までの整数の並び替えかどうかを答える問題。 $1$ から $N$ まで、1個ずつあるかを確認する。ここまでで3分。

C問題 は、AのC乗とBのC乗の大小関係を調べる問題。

Cが奇数のときは、AとBの大小関係と同じ。偶数のときは結果が0以上になるので、符号の問題が出てくる。ただ、2乗して比較すればいい。ここまでで7分。

D問題 は、数列が与えられるので、その数列に含まれていない正の整数のうち、小さい方から K 番目の値を答えていく問題。

サンプル1を見ながら考えて、例えば5番目を答えるとき、「8」はダメ。8以下の数字達には、数列の要素が4つあって、数列にないものが4つあるから。

こう考えると、二分探索が使えそう。より具体的には、「値 m は、K番目以降ですか？」を答えていく。0 はダメな値、2e18 はOKな値。ある値が境になるので、その境い目を見つければいい。

値 m が数列の要素になっていると絶対に答えにならないので、それを除くようにする。ここまでで、1WAで28分。

E問題 は、白いボール $N$ 個と黒いボール $M$ 個を横一列に並べる問題。左から i 番目までの白いボールの個数 $w_i$ と黒いボールの個数 $b_i$ について、必ず $w_i\leqq b_i+K$ が成り立つような並べ方の総数を答える。

サンプルがあまりヒントにならない。1つ目は除外される並べ方は1通り。2つ目は全部除外。3つ目は除外されるものがない。

ボールの個数を経路のように考える。白が並ぶと右へ、黒が並ぶと上へ、という感じ。で、最短経路問題的に考えるのかなぁ、と思ってました。

そうすると、除外すべき経路は、隅っこの三角形の地帯だとわかります。これをどう除外すべきか。

一番シンプルなケースは、カタラン数のときで、正方形と対角線であればカタラン数が出てくることは知ってたので、それがうまく使えないか考えていました。

で、折り返しで計算する方法もあったなぁと思って、上の画像の左下のほうでも折り返した図をかいていたのですが、結局細かいところを詰め切れずに終了。

後で解説を見たら、解説にも折り返しの図がかいてあるじゃないですか。解説と同じ図をかいていたのに通せてないのはダメすぎですね。