LoginSignup
8
3

ABC355 C問題復習

Last updated at Posted at 2024-05-28

はじめに

ABC355(2024年5月25日開催)にてC問題がAC出来なかったので、立てた方針と目指すべきだった解答を整理する。
アウトプットが目的のため最低限の記述のみを行う。
使用言語:Python

対象の問題

試験時間に試したこと、思ったこと

・とりあえずN=5で数字を並べてみる

5×5
1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

・規則的に並んでいることは分かった
・「ビンゴを達成」をうまく言い換えることができない(入力値をそのままリストに格納してどうにか~とか考えていた)
・斜めの値はどうやって判定するんだろう

気づくべきだった点

・座標平面を考える

入力値(以下Aとする)に対して、x座標はAをNで割ったあまりを、y座標はA/Nの整数部分をそれぞれ求めることで算出できる。
式としては
x = A % N
y= A // N
とすることでx,y座標を識別することができる。
N=5のときは入力値AをNで割ったときの余りが0,1,2,3,4の列、A/Nの整数部分が0,1,2,3,4個の行といった次第である。
これを後述のリストに都度格納することで判定を行う。

・1始まりではなく0始まりのマス目を考える

簡単のため、便宜的に入力値を-1 してx,y座標を考える。つまり以下のようなマス目と考える。

5×5
0  1  2  3  4
5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

こうすることにより、右端の列の整数部分が異なって煩雑になることを回避できる。

・「ビンゴを達成」は、縦・横・斜めのリストをそれぞれ作成していずれかのリストの要素がNに達したとき、と言い換えることができる

縦横について、
X=[0,0,0,0,0](Nで割った余りが0,1,2,3,4)
Y=[0,0,0,0,0](A/Nの整数部分が0,1,2,3,4)
斜めについて、
Z=[0,0](左上→右下,左下→右上)こと
のリストを用意しておく。入力値を受けとった後にこのリストの該当するインデックスの要素に+1し、いずれかの要素がNになったとき「ビンゴを達成」といえる。
例えば入力値が16,17,18,3,19,13,20であったときに、リストの要素は以下のように変化する。

入力
16:X[0,1,0,0,0],Y[0,0,0,1,0],Z[0,0]
17:X[0,1,1,0,0],Y[0,0,0,2,0],Z[0,1]
18:X[0,1,1,1,0],Y[0,0,0,3,0],Z[0,1]
 3:X[0,1,1,2,0],Y[1,0,0,3,0],Z[0,1]
19:X[0,1,1,2,1],Y[1,0,0,4,0],Z[0,1]
13:X[0,1,1,3,1],Y[1,0,1,4,0],Z[1,2]
20:X[1,1,1,3,1],Y[1,0,1,5,0],Z[1,2]

この時Y[3]の要素がN(今回は5)に達しているため、7回目の入力で「ビンゴを達成」と判定できる。

実装

・先述の縦横それぞれN個の要素を持つリストを、斜めは左上→右下、左下→右上の2個のリストをそれぞれ作成しておく。入力値の数だけループを行う。
・(入力された値-1)についてx,y座標を算出し、x,y座標に応じてまず縦のリスト(x座標)の該当インデックスの要素に +1 する。要素が N になっていればそれが解答になる。同様に横のリスト(y座標)の該当インデックスに+1して、要素が N か判定を行う。斜めのリストについては、先述の条件を満たすときのみ +1 して要素がNかの判定を行う。
・本問は入力値が重複なしのため要素の重複を気にする必要がない。
・解答が出た時点でexitする。またT個の入力を受け付けてもどのリストもNにならないときは -1 を出力する。

この4点が実装の肝要な点である。

おわりに

文章書くと冗長になってしまいがちなので、短くすることを意識してみた。
人に読ませるためではなく、自分のアウトプットのための記事はこれが良いのだと思う。

8
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
8
3