【AtCoder】【C#】DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 の反省
ここでは、DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選(以下、DDCC)のコンテンストに参加して、どのように考え解いたのか、なぜ解けたのか、なぜ解けなかったのかを反省として書き残しておきたいと思います。
はじめに
問題へのリンク
解いた問題
A,B,Cを解きました。ただ、Cはコンテスト時間中にACできず、コンテスト終了後にあらためてACしたので、そのあたりの反省についても書きたいと思います。
解答説明
A問題
これはあまり難しく考えず、与えられた条件についてif文で分岐を書きました。悩むところもなかったです。
実装 AtCoder/A.cs at master · chittai/AtCoder · GitHub
B問題
これは、あるk番目までの長さを足したものをL、kからN番目までの長さを足したものをRとして、L=R にする必要があるのだなと考えました。
そうすると、この時点で累積和を使えばL,Rは求められるとわかったのですが、今回は指定の操作に1円かかり、このL=Rにするための最小金額を求める必要があります。
ここは単純に、|L-R|を引いた値が必要な操作回数になるので、(要はLとRの朝が3だった場合、操作によって3の差を埋める必要があります。長さの増減の単位は1なので3回の操作が必要です)
以上から、累積和で求めた値から、各iにおけるLとRの差を求め、最小となるものが答えです。
実装 AtCoder/B.cs at master · chittai/AtCoder · GitHub
C問題
これがACできませんでした。ただ、振り返ると考え方自体は間違っていない(スマートかどうかは別の話)ので、実装力の問題かなと思います。
まず問題をみて、イチゴがある行はその行において長方形を完結させれば良いと考えました。たとえば、最後の行はイチゴが2つあるのですが、その2つを個別に含むように長方形を設定すれば要件は満たせます。
ただ、これは行にイチゴが一つ以上ある場合にのみ有効で、イチゴが一つもない行については別の処理を考えなければなりません。(今回はここの実装がうまくいかなかくてACできませんでした、、、、、)
基本方針としては、イチゴが一つもない行は上か下にあるイチゴがある行と同じならびにすれば問題ないです。下記のような感じです。
今回の実装は、1行目にイチゴがない場合は、2行目、3行目とイチゴがある行を探していき、最初に見つけた行と同じ並びにしています。2行目以降でイチゴがない行は一つ上の行と同じ並びにしています。最初の行だけ処理を別にしているのは、最初の行を埋めてさえしまえば残りのイチゴがない行の一つ上の行は並びが確定していることが保証されるためです。
実装 AtCoder/C.cs at master · chittai/AtCoder · GitHub
感想
解法などはわかったのはいいことですが、時間内にアルゴリズム考えて実装することができなかった点は駄目。慌てずに、アルゴリズムをちゃんと考えて実装することが大事。この時は、目の前の課題にしか目がいかずNGとなるテストケースを見落としていたので。。
