ABC414を振り返ります
今回はABまで2問解答でした。
C問題が回文の問題だったので苦手意識があり、飛ばしてD問題に取り掛かったのだけど結局わからずでした。
(C,Dはコンテスト後に復習してACしたコードを載せています)
直近の３回連続でレーティングがマイナスになってまして、今回はとうとう緑色→茶色になってしまいました...。
週末のコンテストに参加するだけだと、良くて現状維持ですね...。ちょっと過去問を解くなりしないと、現状維持も厳しいなあといった感じです。
A - Streamer Takahashi
与えられた条件を満たすリスナー数をカウントします。
（動画配信を見る人は、なぜリスナーと呼ばれるのか、以前からの不思議...ラジオの影響が大きいのでしょうか）
N, L, R = map(int, input().split())
answer = 0
for i in range(N):
X, Y = map(int, input().split())
if X <= L and R <= Y:
answer += 1
print(answer)
B - String Too Long
文字列を連結していきます。ただし、入力例2にあるように、「a 1000000000000000000」みたいな文字列を連結してしまうと、処理が固まってしまいます。
そのため、復元する文字列の長さを min(101, int(l)) として、101文字以上の文字列は復元しないようにしました。
N = int(input())
answer = ""
# 文字列を復元していく
for i in range(N):
c, l = input().split()
# 長過ぎる文字列は101文字まで復元
length = min(101, int(l))
for j in range(length):
answer += c
# 100文字を超えたらToo Long
if len(answer) > 100:
print("Too Long")
else:
print(answer)
C - Palindromic in Both Bases (解説AC)
問題文を見て、回避した問題です(回文に苦手意識がある)。
N<=12 という条件を見て、「10^12 の回文を一つ一つ求めていたらTLEだな...」と考えてしまったのが良くなかった。
実際は半分だけのパターンを作れば、その反転で回文がつくれるので、10^6だけ調べれば良いのでした。
例: 前半部分を123とすると、反転してくっつければ 123321 と 12321 という回文を作れる
以下のソースコードは、公式解説のYouTubeを見て書きました。
https://www.youtube.com/watch?v=rLoeRm2BXDk&t=2820s
A = int(input())
N = int(input())
# 10進数からA進数に変換する関数
def dec_to_n(num:int, base:int) -> str:
s = ''
while num > 0:
s += str(num % base)
num //= base
return s[::-1]
# 問題の条件を満たすか判定する
def is_ok(kaibun:int, base:int) -> bool:
# N以下の条件
if kaibun > N:
return False
# A進数に変換する
kaibun_a_str = dec_to_n(kaibun, base)
# 変換後も回分なら、答えに加算する
return kaibun_a_str == kaibun_a_str[::-1]
answer = 0
for i in range(1, 10**6):
# 回文を生成する
# i=12 なら、1221 と 121 を作る
str_i = str(i)
kaibun_a = int(str_i + str_i[::-1])
kaibun_b = int(str_i[:-1] + str_i[::-1])
# 条件を満たすなら、答えを追加
if is_ok(kaibun_a, A):
answer += kaibun_a
if is_ok(kaibun_b, A):
answer += kaibun_b
print(answer)
D - Relative Position (解説AC)
この問題、有名な「羊羹を切る問題(001 - Yokan Party（★4）)」の類題かと思って解いていたのですが、思ったように解けず...
「羊羹を切る問題」の解法(すべてのグループが長さnに収まるか？を2分探索する)だと、以下のようなケースでWAになってしまいます。
4 3
1 2 3 4
↓
[1 2] [3 4] = 2 のように、基地局2個でやってしまう
[1 2] [3] [4] = 1 と、基地局を使い切るのが正解
ではどうすればいいか。
解説を読むと「家をM個のグループに分ける」「グループ間の間隔が最大になるようにわける」と良いことがわかります。
そんな簡単な考え方で良かったのか...。
5 8 10 14 15 20 ← 家の位置(sort済)
3 2 4 1 5 ← 家の間隔
↓
[5,8,10] [14,15] [20] と分けると、電波が届く区間の長さが(20-5)-5-4=6 となり、最小になる。
N, M = map(int, input().split())
X = list(map(int, input().split()))
# 重複を除去してソート
set_x = set(X)
X = list(set_x)
X.sort()
# 家と家の間の距離を求める
diffs = []
for i in range(1, len(X)):
diffs.append(X[i] - X[i-1])
diffs.sort(reverse=True)
# すべての家に基地局を設置できる場合
if len(diffs) < M:
print(0)
exit()
# 最も左の家のから、最も右の家までの距離
home_distance = X[-1] - X[0]
# M個の基地局を設置するので、M-1個の電波が届かない区間がある
# 電波が届かない区間を、なるべく大きい区間から選ぶ
diff_distance = 0
for i in range(M-1):
diff_distance += diffs[i]
# 全体から電波が届かない区間を引く
print(home_distance - diff_distance)