AtCoder ProblemsのRecommendation(Moderate)を解く
- AtCoder Beginner Contest 157 C - Guess The Number
- NOMURA プログラミングコンテスト 2021 (AtCoder Regular Contest 121) A - 2nd Greatest Distance
AtCoder Beginner Contest 157 C - Guess The Number
diff = 456
リンク：C - Guess The Number (atcoder.jp)
概要：桁の数字の各桁について
個の指示が矛盾しない最小の数字を出力してね
最大3桁、条件数最大5回なので0~999の順に全探索してもいいような気がしますがうまい方法が思いつきませんでした。
なので各桁を-1で初期化した配列を用意して、指示の通り数字を置き換える方針としました。
最終的に-1を0もしくは1に置き換えて出力しています。
この問題で-1を出力すべきは以下の2通りです。
条件1：同じ桁に違う数字を入れようとしたとき
条件2：2桁以上の数字で一番大きい位が0のとき
条件1は配列操作の段階で排除しています。
（として識別しています）
条件2はのときのみ0が許容されるので面倒です。
なので配列が完成した後にかどうか、違う場合は一番左の桁に0が入っていないか判定を入れました。
N, M = map(int, input().split())
ans = [-1] * N
flag = True
for _ in range(M): #桁の指定条件受け取りと条件1の判定
s, c = map(int, input().split())
if ans[s-1] == c: #すでに書き換え済の桁に同じ数字を受け取った場合は処理を行わず流す
continue
if ans[s-1] == -1: #書き換え前の場合はcに書き換える
ans[s-1] = c
else: #書き換え済かつ違う数字を受け取ったときはNG判定
flag = False
break
if flag == True: #条件1をクリアした場合
if N == 1: #1桁で数字指定が無い場合は0を出力
if ans[0] == -1:
print(0)
else:
print(ans[0])
else: #2桁以上の時
if ans[0] == 0: #1番大きい桁が0のときNG判定
print(-1)
else:
for i in range(N):
if i == 0 and ans[i] == -1: #最大の桁が書き換えされていなければ1にする
ans[i] = 1
else:
if ans[i] == -1: #他の桁は0にする
ans[i] = 0
print(*ans, sep = '')
else:
print(-1) #条件1を満足しなかった場合は-1を出力 提出リンク：提出 #50639848 - AtCoder Beginner Contest 157
NOMURA プログラミングコンテスト 2021 (AtCoder Regular Contest 121) A - 2nd Greatest Distance
diff = 459
リンク：A - 2nd Greatest Distance (atcoder.jp)
概要：個ある家同士の距離を定義に沿って計算して2番目に遠い距離の値を出力してね
、問題文にある通り組み合わせは
通りなので愚直に全探索した場合
でTLEになります。
何とかして計算量をや
などに落とせないか考えます。
問題文から座標の絶対値が大きいものだけ見ればいいことがわかるので探索する対象を絞ることができ、ソートによる計算量
まで落とせそうです。
具体的には座標の大きいもの2軒＋小さいもの2軒、
座標の大きいもの2軒＋小さいもの2軒で合計8軒程度を見れば答えが出せます。
家の座標リストを座標と
座標でソートしたいので、
座標でソートしやすいように
の順で記録していく配列
と、
座標でソートしやすいように
の順で記録していく配列
の2つを作りました。
別々のリストで管理するため同じ座標を格納した際に同じ家なのか違う家なのか判断できるように、のように座標と家の番号(座標を受け取った順)の3つの情報を保持するようにしました。
あとはそれぞれのリストで距離を計算して配列にメモするのですが、
座標から取り出した配列
と
座標から取り出した配列
とで同じ家同士の距離を計算しては不正解になりますので重複しないように配列
で管理しました。
計算量はソート部分に最も時間がかかるのでで十分高速です。
4軒の家同士の組み合わせ数は高々6通り、その家が探索済みかをかかるin演算子で探してますがここでの
は高々4なので探索対象の家を正しく取り出した後は少々ガバってもTLEにはならないと思います。
N = int(input())
xd = []
yd = []
for i in range(N):
x, y = map(int, input().split())
xd.append((x, y, i))
yd.append((y, x, i))
xd = sorted(xd)
yd = sorted(yd)
xdd = sorted(xd[:2] + xd[-2:]) #x座標でソートして上から2つ、下から2つを取り出し
ydd = sorted(yd[:2] + yd[-2:]) #y座標でソートして上から2つ、下から2つを取り出し
#print(xdd, ydd)
seen = []
dist = []
for i in range(len(xdd)):
for j in range(i, len(xdd)):
if xdd[i] == xdd[j]: #N=3のとき家の重複が出るので計算から除外
continue
else:
d = max(abs(xdd[i][0] - xdd[j][0]), abs(xdd[i][1] - xdd[j][1]))
dist.append(d)
seen.append((xdd[i][1], xdd[i][0], xdd[i][2])) #yddの計算で同じ家同士を計算しないように参照した家をメモ
seen.append((xdd[j][1], xdd[j][0], xdd[j][2]))
for i in range(len(ydd)):
for j in range(i, len(ydd)):
if ydd[i] == ydd[j]:
continue
if ydd[i] in seen and ydd[j] in seen: #xddで見た家同士の計算を除外
continue
else:
d = max(abs(ydd[i][0] - ydd[j][0]), abs(ydd[i][1] - ydd[j][1]))
dist.append(d)
dist = sorted(dist, reverse=True)
print(dist[1]) #距離大きい順に2番目を出力提出リンク：提出 #50640693 - NOMURA プログラミングコンテスト 2021 (AtCoder Regular Contest 121)
