1. 前書き
AtCoderBeginnerContest(ABC)の参加結果と内容の整理、および外部の解説記事を参考にした上で、自分なりに解法を整理していきます。
使用言語はPythonで行きます。本業ではJavaかRubyonRailsユーザーですが、計算速度の問題であったり、トレンドに乗っておくという意味でも(こちらが大きい)、Pythonに慣れていきたいと思います。
2. コンテスト内容
- コンテスト名
- AtCoder Beginner Contest 275
- 開催日時
- 2022/10/29(土) 21:00 - 22:40
- 実施区分
- バーチャル参加
- 2022/11/2(水)
3. 結果
区分 | 結果 | 所要時間 | 実行時間 |
---|---|---|---|
A問題 | AC | 9:42 | 24ms |
B問題 | AC | 12:55 | 24ms |
C問題 | 未提出 | - | - |
4. 解説
4-1. A問題
4-1-1. 問題文
AtCoder村にはN本の橋があり、i本目(iは1以上N以下の整数)の橋の高さは Hiです。
ここで、AtCoder村にあるN本の橋のうち、どの相異なる2本の橋も高さが異なります。
AtCoder村で最も高い橋は何本目の橋か出力してください。
4-1-2. 入力形式
N
H1 H2 ... HN
4-1-3. 解説
H1~HNを配列に格納して、最大値のインデックスを求めるだけの問題ですね。
pythonでは、配列に対して、要素内の最大値を求めるmax関数、特定の値を持つ要素のインデックスを求めるindex関数があるので、それを適用するだけです。
4-1-4. ソースコード
n = int(input())
h = list(map(int, input().split()))
print(h.index(max(h))+1)
4-1-5. python文法の整理
配列の最大値を検索 max()
配列オブジェクトに対して、構成要素の中から最大の要素を出力する。
配列オブジェクトにメソッドを適用するのではなく、メソッドの引数に配列オブジェクトを与える点に注意。
#使用法
max([配列オブジェクト])
指定値が存在するインデックスを検索 .index()
配列オブジェクトに対して適用し、指定した値が存在するインデックスを検索して出力する。
一点、配列オブジェクトの中に指定値が複数含まれる時は、インデックスの最小値が出力される点に注意が必要。
また、第二引数と第三引数に、検索開始/終了位置を指定することもできる。
#使用法
[配列オブジェクト].index([指定値])
#使用例
array = [1,2,3,2,1]
print(array.index(1)) -> 0 #最小のインデックスが出力される
print(array.index(1,2)) -> 4 #インデックスが2~末尾の中で、1が含まれる要素の最小のインデックスが出力される
4-2. B問題
4-2-1. 問題文
非負整数 A,B,C,D,E,F があり、A×B×C≥D×E×F をみたしています。
(A×B×C)−(D×E×F) の値を 998244353 で割った余りを求めてください。
4-2-2. 入力形式
A B C D E F
4-2-3. 解説
問題文に書いてある文言を、そのまま数式に起こすだけですね。
pythonでは特に工夫する必要はありません。
4-2-4. ソースコード
a,b,c,d,e,f = map(int, input().split())
print(((a*b*c)-(d*e*f))%998244353)
4-3. C問題
4-3-1. 問題文
二次元平面があります。1以上9以下の整数r,cについて、
Srのc番目の文字が「#」であるとき座標(r,c)にポーンが置いてあり、
Srのc番目の文字が「.」であるとき座標(r,c)に何も置かれていません。
この平面上の正方形であって、4頂点全てにポーンが置いてあるものの個数を求めてください。
4-3-2. 入力形式
S1
S2
...
S9
4-3-3. 解説
[筆者の思考]
まず2つのポーンを正方形の1辺として固定し、その1辺を基準とした正方形を考えます。
それによって、残りの2つのポーンの条件が導かれるので、その座標にポーンがあるかどうかを検索する。
という流れで考えました。
ただ当然ですが、これだと正方形の候補が2パターンできてしまい、ロジックが複雑化してしまい、ギブアップとなりました。
[他解説記事における解法]
先程の考え方でも、3点目の取り方を工夫することでダブルカウントを防ぐことはできそうですが、他の方の解説に全探索で解くもっと単純な方法があったので、そちらを参考に解説したいと思います。
4つのポーンを全探索
全座標数でも、9×9=81個なので、81C4 ≒ 2×10^6となるため、間に合いそうです。
大きなロジックの流れは以下の通りです。
- 入力値を9×9の2次元配列に格納する。
- 上記の2次元配列を2重ループで捜査し、座標を[x,y]の配列の形式で、ポーンの数の分の座標の集合として配列に格納する。
- 4重ループで座標の集合配列から4点を全捜査する。
- 4点から2点をピックアップして、距離の2乗を計算する。
- 全8通りについて計算し、その比が1:1:1:1:2:2であれば答えとしてカウントを1追加する。
[参考URL]
4-3-4. ソースコード
全探索の解法を見た上で、ソースコードを書いてみました。
from itertools import combinations
#入力を2次元配列に格納
s = [list(input()) for _ in range(9)]
#pair:ポーンの座標の一覧
pair=[]
for i in range(9):
for j in range(9):
if s[i][j]=="#":
pair.append((i,j))
#N:ポーンの数
N=len(pair)
#答えの個数
ans=0
#4点取得
for one in range(N):
for two in range(one+1,N):
for three in range(two+1,N):
for four in range(three+1,N):
#tmp:取得した4点
tmp = [pair[one],pair[two],pair[three],pair[four]]
#dist:4点中各2点の距離の配列
dist=[]
for i in combinations(range(4),2):
a,b = i
dist.append((tmp[a][0]-tmp[b][0])**2+(tmp[a][1]-tmp[b][1])**2)
dist.sort()
flg = True
for j,n in enumerate([1,1,1,1,2,2]):
if dist[0]*n!=dist[j]:
flg = False
break
if flg == True:
ans += 1
print(ans)
4-3-5. python文法の整理
配列の長さを求める len()
配列オブジェクトに対して、配列長を出力する。
max()と同様、配列オブジェクトにメソッドを適用するのではなく、メソッドの引数に配列オブジェクトを与える点に注意。
#使用法
len([配列オブジェクト])
組み合わせ combination()
高校数学で習った、組み合わせの結果をタプル列のイテレータで出力する。
イテレータを生成する関数を集めたitertoolsモジュールに含まれ、AtCoder上で使用するためにimport文が必要。
#使用方法
combinations([イテレータ], [数値])
#使用例
from itertools import combinations
for elem in combinations(range(4),2):
print(elem)
-> (0,1), (0,2), (0,3), (1,2), (1,3), (2,3)