競プロ参戦記 #30 「花壇とスシ」 | ABC 116

ABC-only 回に参加しました。いつもどおり考察を書きます。

AtCoder Beginner Contest 116

問題リスト: https://atcoder.jp/contests/abc116/tasks

A - Right Triangle

問題概要: ある直角三角形の3辺の長さが与えられる。面積を求めよ。

考察: 私は問題文を誤読してしまいました。

誤読時の考察: ~~直角三角形の面積は、直角の両隣の辺の長さを x, y とすると (x * y) / 2 です。3辺のうち、どれが直角の両隣にあるかが分かれば計算できます。直角の両隣にない辺 (斜辺) は3辺の中で最長のものです。したがって、辺の長さを配列に入れてソートし、最初の2つの要素を x, y とおけば上記の式で答えが出せます。~~

よりよい考察: ∠ABC が直角なので、直角の両隣の辺は AB と BC が底辺と高さです。(底辺 × 高さ) / 2 が答え。

筆者の回答 [AC]: https://atcoder.jp/contests/abc116/submissions/4054051

B - Collatz Problem

問題概要: 初項 s のコラッツ数列で最初に重複した値が出現する位置を求めよ。つまり、数列 A を次のように定義する。初項 A[1] = s は与えられる。A[n] が偶数なら A[n + 1] = A[n] / 2 とし、奇数なら A[n + 1] = 3 * A[n] * 1 とする。A[n] = A[m] となる整数 n (ただし n, m) が存在するような整数 m で最小のものを求めよ。

考察: A の値を順番どおりに計算していき、A[n] の値が出現済みなら n が答え、そうでなければ値 A[n] を「出現済み」であることを記録して次へ、とやっていけばOKです。m ≤ 1000000 なのは問題文で与えられているので、間に合うことが分かります。

要素の値がすでに出現したかどうかは集合 (あるいはマップ) で記録すればよいです。boolean の配列を使ってもOK。

筆者の回答 [AC]: https://atcoder.jp/contests/abc116/submissions/4053876

C - Grand Garden

問題概要: N 個の花がある。範囲 l..r の花の高さを1上げる、という操作を繰り返し行なって、花 i の高さがちょうど H[i] になるようにした。操作回数の最小値を求めよ。

考察: 1回の操作でなるべく多くの花の高さを目標に近づけるようにするのが最善です。

高さが目標に達していない左端の花を i とするとき、その花には操作をする必要があります。また、 i より右にある、高さが目標に達していないなるべく多くの花を巻き込んで操作をしたほうがよいです。(縮める利点がないから。)

範囲は実際にループで求めます。花の高さの更新もループでちまちまインクリメントすればいいです。計算量は O(N^3) ですが、 N ≤ 100 なので十分に間に合います。

筆者の回答 [AC]: https://atcoder.jp/contests/abc116/submissions/4053530

D - Various Sushi

問題概要: 品物が N 個ある。i 番目の品物の種類は t で、価値は d である。品物を K 個選んだ。選ばれた品物の種類数を x とし、価値の総和を s とするとき、スコア (s + x^2) の値が (選びかたの中で) 最大だった。この最大スコアを求めよ。

考察: 結果からいうとWA2個がとれなくてACできませんでした。それでも考察はおおよそ筋が通っていたようなので、自分の考えで書きます。

はじめ、種類数 x でつくスコアが問題をややこしくしているので、これを全探索して「x 種類の品物を選ぶときの最大のスコア」が求まらないか？ という方針を考えました。いかにも最悪計算量が O(N^2) 以上になりそうなのですぐ捨てました。

ひとまず状況を単純化したときの解を確認します。

- すべての品物の種類が同じだとします。このときは価値が高い順に K 個を選ぶのがベスト。
- すべての品物の価値が同じだとします。このときは種類が異なる K 個を選ぶのがベスト。

直感的に「価値が高い順に K 個を選ぶのがベスト」な気がしますが、スコアの x^2 の影響により、そうではないケースがあります。つまり、価値の高い品物を捨ててでも、他の種類の品物を取ることで種類数を増やしたほうがいいことがあるわけです。

一方で、種類数が増えないなら、価値の低い品物を選ぶ理由はありません。つまり価値が上位 K 個の品物と、同じ種類の品物は、もう選ぶ価値はないはずです。除外します。

このあたりで、こういうアルゴリズムを考えました。

- 品物を価値順に並べて上位 K 個を選ぶ。
- L: 選ばれている品物と同じ種類の、選ばれていない品物はすべて削除する。
- 2つ以上の品物が選ばれている種類で、最も価値が低い品物を1つ捨てる。(選ばないことにする。)
- 選んでいない種類の品物のうち、価値が最大のものを選ぶ。
- L に戻って、捨てる品物がなくなるか、選んでない品物がなくなるまで繰り返し。

これは一見、正しそうです。というのも、

- 最初に K 個選んだときの種類数を x とします。この時点でのスコアは、種類数が x 以下になる選びかたの中で最高のスコアです。というのも、他の種類の品物を選ぶと価値の総和が必ず減少するため。
- 手順 L 以降を1周した時点での選びかたは、種類数 (x + 1) での選びかたで最高のスコアになります。というのも、ほかの種類の品物を選ぶと価値の総和が減少します。また、すでに選んだ種類の品物の中で見ると、価値が上位K個のものが選ばれているので価値の合計は最大です。
- 同様に、手順 L 以降を k 周すると、種類数 (x + k) のすべての選びかたで最高のスコア、というのが見つけられています。

そういうわけで提出してみたところ WA が2個出ました。

筆者の回答 [WA]: https://atcoder.jp/contests/abc116/submissions/4057848

反例が全く思いつかないまま終了です。公式の解説を見たところ、考えかたはおおよそ同じに思えるので、おそらく実装上の不具合だと思います。(なんで Priority Queue が必要になるんだろう？)

追記: D 通りました。ある種類の品物を選んだかどうか、というのを手順 L 以降で更新するのを忘れていました。

筆者の回答 [AC]: https://atcoder.jp/contests/abc116/submissions/4059367