AtCoderBeginnerContest275 に参加してきました

数学苦手エンジニアがAtCoderBeginnerContest275に参加してみました！人生で正方形の必要十分条件を考えたことがなかったことが明るみに出ましたが、とても面白い考察体験でした！

今泉大樹

2022.10.31

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

こんにちは、AWS 事業本部コンサルティング部に所属している今泉（@bun76235104）です。

私は以前よりAtCoderのコンテストに参加しており、先日茶色コーダーと言われるレート帯に入ることができました。

現在は自分のできるペースで緑コーダーというレート帯を目指して、ゆっくり精進しています。

今回も2022/10/29（土）に開催されたAtCoderBeginnerContest275に参加してきました！

AtCoder のレートと筆者のレベル感について

筆者は茶色コーダーになったばかりで、2回に1回C問題をコンテスト中に解ける程度のレベル感です。

AtCoderにおけるレーティングの意味や筆者のレベル感などはこちらの記事を参照ください。

2022年10月31日時点の筆者のレーティングは446となっています。

atcoder_bun913_20221031_rating

筆者の結果について

コンテストは10/29の21:00 ~ 22:40までの開催でした。

私の提出履歴がこちらです。

提出日時	問題	結果
2022-10-29 21:10:32	B - ABC-DEF	AC（正解）
2022-10-29 21:06:23	B - ABC-DEF	RE（不正解）
2022-10-29 21:01:18	A - Find Takahashi	AC（正解）

今回は目標としているC問題まで解くことができず、またB問題を1回落としてしまったことでペナルティをもらってしまったのが悔やまれます。

C問題は実装の方向性としては悪くなかっただけに悔やまれる結果となりました。

A - Find Takahashi

配列から最も大きい要素のindexを算出する問題です。

問題の制約から配列の要素がすべて異なるということがわかっていたので、以下のように並び替えて最も大きい要素を求め、並び替え前の配列からindexを算出するという方法で回答しました。

N = int(input())
H = list(map(int, input().split()))
k = sorted(H, reverse=True)[0]
print(H.index(k) + 1)

しかし解説のように（値、index）というタプルを配列（リスト）に用意して、ソートするという解法が非常にスマートだと思います。

N=int(input())
A=list(map(int,input().split()))
B=[(a,i+1) for i,a in enumerate(A)]
B.sort()
print(B[-1][1])

A問題を解く時は、自分が秒速で書ける方法を書いてしまうのですが、私もこのような回答が出るようになりたいですね。（N回目の感想）

B - ABC-DEF

問題を見た瞬間「A×B×Cの結果がD×E×F以上です」という制約の怪しさを感じた問題です。

一度よく考えずに早く提出しなきゃ！と焦ってDecimalモジュールを使って提出して不正解になってしまいました。

その後、問題をよく考えて最終的に算出するのは998244353 で割った余りということを整理すると、余りの性質を使える問題だと考えました。

最終的には以下の方法で提出をしました。

a, b, c, d, e, f = list(map(int, input().split()))
mod = 998244353
left = a % mod * b % mod * c % mod
right = d % mod * e % mod * f % mod
ans = (left - right) % mod
print(ans)

公式の解説にもあるとおり、a*b*cとd*e*fの余りの差を取る際に負の値になり得ることに注意が必要です。

Pythonの場合負の値になることをあまり気にせずに良いので、素直に計算しています。

後で解説を見て納得したのですが、Pythonだと整数型のオーバーフローを気にせず以下のような素直な解法で正解できたようです。

a,b,c,d,e,f=map(int, input().split())
print((a*b*c-d*e*f)%998244353)

ただし、大きな桁数の演算により計算時間は増大してしまうため、余りの性質を理解して、計算の途中で余りを求める技術を覚えておいて損はないと思います。

C - Counting Squares

今回時間内に解けなかった問題です。

以下は実際に私がコンテスト中に書いたメモです。（字が汚くて申し訳ありませが、コンテスト中の焦りを感じていただければと思います）

abc275_problemc_bun913_summary

9*9のマスが入力として与えられ、#が書いてある任意のマス4点選んで正方形を作れる4点の組み合わせの数を求めれば良いようです。

以下のようなコードを書いていたのですが、4点が正方形になるという条件をうまくコードで表現できませんでした。

from itertools import combinations

S = [list(input()) for _ in range(9)]

# ポーンが配置されているマスの位置を配列に保持
porns = []
for x in range(9):
    for y in range(9):
        if S[x][y] == "#":
            porns.append([x, y])
# あとはこの4点が正方形か判定する
ans = 0
for pattern in combinations(porns, 4):
    # 4辺の長さが等しいのは必要
    # あとは角度が全部90度になること？
    # ベクトルとか使ってやろうとしたけど答えを出せずに終わった
print(ans)

コンテスト終了後、以下のブログを拝見して条件を整理できました。

任意の4点を結ぶとできる6つの線分のうち
- 正方形の4つの辺の長さが等しい
- 正方形の対角線の長さが2つも等しい

で十分なようです。

これを拝見したのち、正解を出せたコードが以下のようになります。

from itertools import combinations

S = [list(input()) for _ in range(9)]

# ポーンの点を抽出
porns = []
for x in range(9):
    for y in range(9):
        if S[x][y] == "#":
            porns.append([x, y])
# あとはこの4点が正方形か判定する
ans = 0
for pattern in combinations(porns, 4):
    # 4辺の長さが等しく対角線の長さも等しいと正方形
    dis_of_sides = set()
    for p1, p2 in combinations(pattern, 2):
        dis_of_sides.add((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
    if len(dis_of_sides) == 2:
        ans += 1
print(ans)

公式の解説では異なるアプローチで進めているので、読んでみると面白いと思います。