ABC184の感想
AtCoder Beginner Contest184に参加しました。
問題はこちらから。
結果はこんな感じでした。
順位： 3311 / 7822
パフォーマンス：970
のabcの3完でした。昨日は少しへこんでいたので、まあほどほどに解けて一安心です。今回のコンテストの難易度が少し変なことになっていて、Cがぼちぼち難しく、d e fは同じような感じでした。そのため、Cを解いた人数よりも順位が低くなっています。解く問題は適切に選びましょうという感じですね。
感想書いていきます。
A 問題
行列の行列式を解く問題。ad-bcでおしまいです。
もうちょっと書きます。問題名が「determinant」ですので、代数学を履修していれば問題名を見ただけでわかったかもしれません。高校生のときは、ケーリーハミルトンで使いましたね。3次元デターミナントはサラスの公式で知られています。
話を膨らませてみましたがこれが限界です。あとは、、、今の高校生って行列をやらないのでしたっけ？
B 問題
クイズの得点を求める問題。x 点持っていて正解なら +1, 不正解なら -1とします。ただし、得点は負になりません。負にならないようにシミュレートしてあげれば終わりです。
もうちょっと書きます。c++って変数の上下限を設定する機能ってあるのでしょうか？以前、Unity,c#にてどちらの機能か覚えていないのですが、値の範囲を設定するということをした記憶があります。これを使えば簡単に実装できますね。
C 問題
将棋の王+角+αみたいな駒があります。この駒は(x1,y1)にあって、(x2,y2)に移動したいです。さて、最小で何手で行けますか。
という問題です。この問題は非常に難しかったです。コンテスト時間100分に対して、70分以上この問題に費やしました。それで、300点ですので、おとなしく、飛ばした方が賢いのかもしれません。と思いましたが、思ったより解かれていて驚きでした。
試験中の考察を書いていきます。
まず、手数は0~3手のいずれかになることはすぐにわかりました。
0手：始点と終点が一致
１手：王移動、+α移動を全部（29通り）行って、終点に一致するか。角移動の一致は「始点と終点のx座標の差＝y座標の差」で取りました。この中で、1つでも一致してたらOKです。
２手：こいつが曲者でした。まず終点にもこの駒を置きます。角移動を除いた、29通りのマスの座標を両方の駒にて取得します。この座標が一つでも一致していたらOKです。一致してなくても、まだあきらめません。始点の角移動が終点の王範囲と一致してるか見ました。これは、ｘ座標の変位分、y座標を動かして、王範囲の上限＋４と下限ー４に入っているか見ました。最後に角移動同士を見ました、始点と終点のx, yの差の和が偶数になってればよいです。
以上のいずれかを満たせば、2手で移動できます。
３手：それ以外
なかなかに実装が大変でした。解説を読んでスマートなやり方を勉強しておきます。
Ｄ 問題
期待値を計算する問題。dp[i][j][k]として、いずれかが100の要素を見ていけば、答えになるかなと考えましたが、実装まで至りませんでした。
Ｅ問題
幅優先探索で始点から計算をしていけば答えになりそうだなと考えましたが、こちらも時間が足りませんでした。
今回はＣ問題がなかなかに鬼門でした。コンテスト後もtwitterにて、少々議論になるぐらいには一筋ではいかない問題でした。それを解けたことは素直に嬉しいですが、コンテストであることを考えると、飛ばす判断をしたかったなと思いました。
また、今回からBeginner Contestの結果を用いたトーナメント戦が開始されました。私はすぐさま敗退してしまったのですが、どうやら敗退者は順位決定のリーグ戦に回されるようです。そのため、そちらの方で頑張りたいと思います。
私を倒した方にはぜひとも優勝していただきたいですね。
この記事が気に入ったらサポートをしてみませんか？