マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）の感想
マイナビプログラミングコンテスト2021に参加してきました。B問題でWAが出た瞬間、プログラミング自体が2週間ぶりだったことを言い訳にしようとかアホなことを考えていましたが気合で3完。以下簡単にコメントしていきます。
A - Tiny Arithmetic Sequence
長さ３の数列を等差数列にできますかという問題。等差数列は後ろの項の方が大きいので、まず小さい順にソート。そして1項目と3項目の和が2項目の2倍に等しいかで等差数列かどうかの判定をしました。
最初は問題文の「数列を並びかえて」の部分を読み飛ばしており、ソートを忘れて少し時間をロスしてしまいました。急がば～って感じです。
B - Do you know the second highest mountain?
二次元配列のうち、2つ目の要素が二番目に大きい要素を出力せよという問題。2次元配列を2つ目の要素で小さい順にソート（pythonではkeyとlambda式）して後ろから2番目の要素を出力しました。
コンテスト開始5分で提出したところまさかのWA。原因が全く分からなかったので一旦C問題を先に取り掛かりました。どうやら数字を文字列として受け取ってソートしたことが原因だったみたいです。
strでの大小は辞書式順序での大小になるので, '123'<'23' になってしまい, 希望通りになりません.
— Kazun ◢͟⁴⁶ (@Kazun_kyopro) 2021年5月15日
C - Secret Number
４桁の暗証番号を作成する。0-9までの数字がそれぞれ「絶対に使う数字」「使わない数字」「使ってもよい数字」に分類されているとき、4桁の暗証番号のパターン数を求めよという問題。
最初は「絶対に使う数字」を先に配置し、その後に「使ってもよい数字」を残った場所に並び替える方法を考えました。しかし、どうやっても1個目のサンプルが合わず数学で求めるのを諦めました。
今回の問題のポイントは「暗証番号が４桁」というところで、全パターンを試しても10^4通りしかないんですよね。そこで全パターンを試して、
- 「絶対に使う数字」の集合が「暗証番号に使った数字」の集合に包含されるか
- 上の2つの差集合が「使ってもよい数字」の集合に含まれるか
の2つの条件を満したパターンを数えました。Pythonのsetを使うと集合の管理が楽でした。
D - Game in Momotetsu World
+マスと-マスが設置してある2次元平面上のコマを2人で交互に最善手で操作するとき、どっちが勝つか求めよという問題。ただし、コマは左上からスタートし、右or下にしか移動できない。
最善手をどうやって求めるのかがわからず終了。こういった問題にも対応できるようになりたい。
まとめ
今回はCの全探索に気づくのに時間がかかってしまいパフォーマンスがあまり伸びませんでしたが、気づいてからはノーペナで実装できたのはよかったと思います。もう少し自分の使える手法を増やしていくともっと対応できる範囲が増えそうだなーと感じたABCでした。
