C - Robot Takahashi
from collections import defaultdict
def main():
"""解答方針
①体重Wを軽い順にソート
②まずX=0とした時の正解の数=大人の数をcorrectとして記録
③次にXをWの中で一番小さな値wよりわずかに大きな値とする
- 重さwにいる人を”子供"と判定するようになる
- その人が子供なら、正解が1つ増えるのでcorrectを1増やす(correct += 1)
- その人が大人なら、正解が1つ減るのでcorrectを1減らす(correct -= 1)
④XをWの中で次に小さい数にして同様に判定、これをソートしたW全てで行う
その中でcorrectの最大値を答えansとして保存する
同じ重さwに複数の人がいる場合、重さwに大人がx人、子供がy人いるのであれば
正解数は(y-x)増えるので、それぞれの重さwについて、
正解の増減を先に計算しd[w]として記録しておく
"""
_ = int(input())
S = [int(c) for c in input()]
W = list(map(int, input().split()))
# ある重さw以下を"子供"と判定した時に正解がいくつ増えるかをd[w]で記録
# d[w]>0の時、正解数は増える。d[w]<0の時、正解数は減る
d = defaultdict(int)
# X=0の時は全ての人を"大人"と判定するので、正解数correct=大人の数
correct = 0
for w, s in zip(W, S):
# 子供であれば、正解数が1増えるのでd[w]に1を足す
if s == 0:
d[w] += 1
# 大人であれば、正解数が1減るのでd[w]から1を引く
else:
d[w] -= 1
correct += 1
# ansの初期値はX=0の時の正解数
ans = correct
# 重さを軽い順にソートし順番に処理
for w in sorted(d.keys()):
# 重さw以下の人を"子供"と判定した時の正解数の増減d[w]を正解数correctに加算
correct += d[w]
# correctの最大値を答えとして記録
ans = max(ans, correct)
print(ans)
if __name__ == "__main__":
main()
D - Jumping Takahashi 2
BFSであればPython3でも600msほどでACできました。
参考：めぐる式二分探索
Pythonでの実装
本家
from collections import deque
def main():
"""解答方針
条件を満たす最小のSの値を二分探索する
条件：
高橋君のジャンプ力Sについて
- あるジャンプ台i(xi, yi, パワーPi)と他のjump台j(xj, yj)の
距離distance=abs(xi-xj)+abs(yi-yj)が
S*Pi以下であればi->jに有向辺を張る
- 有向辺を貼り終わった時にいずれかのジャンプ台から
他の全てのジャンプ台へ有向辺を辿って移動できる
条件の探索には幅優先探索BFSを用いる
二分探索にはめぐる式二分探索を用いる
"""
N = int(input())
pos = []
P = []
# それぞれのジャンプ台の場所pos(x, y)とパワーPを入力から受け取る
for _ in range(N):
x, y, p = map(int, input().split())
pos.append((x, y))
P.append(p)
# ジャンプ台iからジャンプ台jへの距離を
# distance[i][j]として記録して取り出しやすくする
distance = [[0] * (N) for _ in range(N)]
for i, (xi, yi) in enumerate(pos[:-1]):
for j, (xj, yj) in enumerate(pos[i + 1 :], start=i + 1):
tmp = abs(xi - xj) + abs(yi - yj)
distance[i][j] = tmp
distance[j][i] = tmp
def is_ok(S):
"""二分探索に用いる条件式
①S*Pi<=distance[i][j]となる場合にi->jに有向辺を張る
②スタート地点を決める
③スタート地点から行ける範囲をBFSで探索し、
全ての地点に行けるならTrue
行けないならFalse
Args:
S (int): 高橋君のジャンプ力
Returns:
bool: いずれかのジャンプ台から、全てのジャンプ台に移動できるか否か
"""
# あるジャンプ台iからジャンプ台jへ移動できるならi->jの有向辺を張る
# ついでに逆方向のj->iについても検証し移動できるなら有向辺を張る
edge = [[] for _ in range(N)]
for i in range(N - 1):
for j in range(i + 1, N):
if P[i] * S >= distance[i][j]:
edge[i].append(j)
if P[j] * S >= distance[i][j]:
edge[j].append(i)
# スタート地点として全てのジャンプ台を全探索する
for start in range(N):
que = deque()
# 既に到達しているか否かをsetで管理
visited = set()
# 初期地点としてスタート地点のジャンプ台を設定
que.append(start)
visited.add(start)
# 幅優先探索
while que:
# キューの左端から値を取り出す
crr = que.popleft()
# そのジャンプ台から到達可能なジャンプ台を調べる
for nxt in edge[crr]:
# 既に到達しているなら何もしない
if nxt in visited:
continue
# まだ到達していなければ、そこを到達済みvisitedに追加
visited.add(nxt)
# 次のジャンプ台をキューの右端に追加
que.append(nxt)
# 全ての範囲を探索し終わった後、
# 全てのジャンプ台に到達しているか=visitedに全ての地点が追加されているか
if len(visited) == N:
# いずれかのスタート地点から全てのジャンプ台に到達できたらTrueを返す
return True
# どのスタート地点からも全てのジャンプ台に移動できなかった場合、Falseを返す
return False
def meguru_bisect(ng, ok):
"""
初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
まずis_okを定義すべし
ng ok は とり得る最小の値-1 とり得る最大の値+1
最大最小が逆の場合はよしなにひっくり返す
"""
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
return ok
# Sを二分探索し答えを返す
# Sの最小値は0, 最大値は対角線に存在する場合の
# i(-10^9, -10^9)とj(10^9, 10^9)なので4*10^9
print(meguru_bisect(-1, 4 * 10 ** 9 + 1))
if __name__ == "__main__":
main()
E - Addition and Multiplication 2
def main():
"""解答方針
①最もコストの低い数字min_cost_numを使い、
可能な限り長い数列(長さ=N//min_cost)を作成する
予算Nからコストを引く(N %= min_cost)
②数iを大きな数から順に(9,8,7,...,1)使用し
min_cost_numと置き換えることができるかを検証していく
- 置き換え可能か？
->残りの予算Nが、iのコストcost[i]とmin_costの差以上であれば
置き換えることができる(N >= cost[i] - min_cost)
- いくつ置き換えるか？
->残りの予算Nをiのコストとmin_costの差分で割った個数分置き換えることができる
(change_num = N // (cost[i] - min_cost))
③iが最もコストの低い数字と同じになれば終了。
それ以上は数字は小さくなることはあっても大きくなることはない
配列の管理について
長さが(N//min_cost)の数列を実際に書き換えていくと計算がかさむので、
"ある数字iがcnt個ある"という情報を
2次元リスト[[i1,cnt1], [i2, cnt2], ...]で記録する
[[5, 2]] -> 5が2個の配列=55
[[9, 1], [5, 1]] -> 9が1個, 5が1個の配列=95
"""
N = int(input())
# 数字iのコストを辞書型で記録、リストでもOK
cost = dict()
# コストが最も小さい数字min_cost_numと、そのコストmin_costを記録
# min_costの初期値は大きな値を入れておく
min_cost = 10 ** 7
min_cost_num = 0
for i, c in enumerate(map(int, input().split()), start=1):
cost[i] = c
# 数字iのコストcが、現在の最小コストmin_cost以下であれば更新する
# 数字iは1,2,3,...,9と昇順なので、
# コストが同じであれば数字iが大きな数字が採用される
if c <= min_cost:
min_cost = c
min_cost_num = i
# ①初期配列として最もコストの低い数字min_cost_numを使用した
# できるだけ長い配列を作る
# 配列の長さはN//min_cost
ans = [[min_cost_num, N // min_cost]]
# 初期配列を作るのに使用した分のコストを予算Nから引く
# 残り予算はNをmin_costで割った余りとなる
N %= min_cost
# ②iを(9,8,7,...)と降順で検証、min_cost_numより1大きい数字まで検証し、
# 置き換えることができれば置き換える
for i in range(9, min_cost_num, -1):
# 数字iでmin_cost_numを置き換えることができるか？
# 残りの予算Nがcost[i]とmin_costの差分より小さければ
# 1つも置き換えることができない
if N < cost[i] - min_cost:
continue
# いくつ置き換えるか？
# 残りの予算Nをcost[i]とmin_costの差分で割った数
change_num = N // (cost[i] - min_cost)
# 置き換えを行う。置き換える数だけmin_cost_numの個数を減らす
ans[0][1] -= change_num
# 置き換えた数字iとその個数を解答に加える
ans.append([i, change_num])
# 置き換えたコスト分、予算から引く
N %= cost[i] - min_cost
# 大きな数字から使用するようにソートする
ans.sort(reverse=True)
# 数字iを文字列に変換しcnt数繰り返した文字列をansに含まれるiの数だけ結合する
print("".join([str(i) * cnt for i, cnt in ans]))
if __name__ == "__main__":
main()