Ccmmutty logo
Commutty IT
14 min read

緑コーダーがABC257のA~Eまで

https://cdn.magicode.io/media/notebox/blob_I7CRSPd

AtCoder Beginner Contest 257

ABC257のA~Eに関する解説(という名の自分用メモ書き)です。
本番ではCまでの3完で止まりました…うう…悔しい…。
DもEも理解はできたなぁ…100分で走りきれる実装力が課題…。

2022/6/28 02:15追記

  • D問題の解法を修正致しました
    • グラフ生成部分、BFS部分をそれぞれ別々に関数として切り出しました
    • 結果、高橋君のジャンプ力が決まった時点でグラフを生成し、ジャンプ力が変わるまでは同じグラフを再利用することになりました
  • D問題のワ―シャルフロイド解法を追記致しました

A - A to Z String 2

問題文

ANN個、BNN個、…、ZNN個この順番につなげて得られる文字列の先頭からX番目の文字を求めてください。

制約

  • 1N1001 \leq N \leq 100
  • 1XN×261 \leq X \leq N \times 26
  • 入力は全て整数

考察

  • いわゆる「やるだけ」問題
  • 問われている点としては、2点
    • 最大2600文字の指定された文字列が生成できますか?
    • また、指定された文字列の中でX番目の文字が抽出できますか?
  • 愚直にAAからZZまでNN個ずつ並んだ文字列を重ループで作っても良し
python
# 入力
N,X = map(int,input().split())

chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" # 文字列一覧

S_L = [] # S_L:文字列を保管するためのリスト(末尾に結合するためリスト形式)

# AからZまでの文字列
for char in chars:    
    for j in range(N):
        S_L.append(char)

# 配列のX文字目を取り出す時は、0-indexのため-1を忘れずに
print(S_L[X-1])
  • 少しだけスタイリッシュにしてみると、
  • A...AB...BC...CD...XZ...ZA...AB...BC...CD...XZ...Z
    • この文字列を作る時に、1文字ずつ足さなくても良いのでは?
      • AANN個連なった塊、BBNN個連なった塊…を、一気に纏めてみる
python
# 入力
N,X = map(int,input().split())

chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" # 文字列一覧

S_L = [] # S_L:文字列を保管するためのリスト(末尾に結合するためリスト形式)

# AからZまでの文字列
for char in chars:    
    S_L.append(char*N)

# 文字毎に半端に固まった配列なので、文字列として全部一纏めにしてあげる
S = ''.join(S_L)
    
# 文字列のX文字目を取り出す時も、0-indexのため-1を忘れずに
print(S[X-1])
  • どうせ配列から文字列に直すのであれば、
  • ABC...XYZABC...XYZの塊をN個引っ付けて、ソートしてあげても良いね?
    • 実際ソートしてるので時間は若干掛かるけども、こっちの方が綺麗で好きかもしれない…
    • 本番にascii_uppercaseをさっと使えるかは別問題
      • A~Zの文字列…なんだっけ…って調べてる間にABC...XYZで入力したほうが早そう
python
import string

# 入力
N, X = map(int, input().split())

# ABC...XYZをN回繰り返したものを、ソートして配列形式にしてあげる
ans_L = sorted(string.ascii_uppercase * N)

# 0-indexでX番目の文字を取り出してあげる
print(ans_L[X - 1])

B - 1D Pawn

問題文

NN個のますが左右一列に並んでおり、左から順にマス11、マス、…、マスNNと番号づけられています。
また、KK個のコマがあり、最初左からii番目のコマはマスAiA_iに置かれています。
これらに対して、QQ回の操作を行います。ii回目の操作では次の操作を行います。
  • 左からLiL_i番目のコマが一番右のマスにあるならば何も行わない。
  • そうでない時、左からLiL_i番目のコマがあるマスの11つ右のマスにコマが無いならば、左からLiL_i番目のコマを11つ右のマスに移動させる。11つ右のマスにコマがあるならば、何も行わない。
QQ回の操作が終了した後の状態について、i=1,2,,Ki=1,2,…,Kに対して左からii番目の駒があるマスの番号を出力してください。

制約

  • 1KN2001 \leq K \leq N \leq 200
  • 1A1<A2<<AKN1 \leq A_1 < A_2 < … < A_K \leq N
  • 1Q1000 1 \leq Q \leq 1000
  • 1LiK 1 \leq L_i \leq K
  • 入力は全て整数

考察

  • いわゆる「愚直シミュレート」するような問題
  • Q回の操作で、
    • それぞれ指定された番号のコマが移動できますか?
    • 出来るなら、1つ右に移動してください
  • 上記を丁寧に条件分けしてあげれば大丈夫
  • in listの形で右のマスが埋まってるかどうかを判定しているのは若干要領が悪い部分…
python
# 入力
N, K, Q = map(int, input().split())
A_L = list(map(int, input().split()))
L = list(map(int, input().split()))

# Q回のクエリを処理する部分
for q in L:
    
    # Li番目のコマを0-indexに戻す
    q -= 1
    
    # もしLi番目のコマが一番右のマスにあるなら何もしない
    if A_L[q] == N:
        continue
    
    # もしLi番目のコマが存在するマスの、右隣にコマが存在するなら、何もしない
    if A_L[q] + 1 in A_L:
        continue

    # q番目のコマを1つ右のマスに動かすよ
    A_L[q] += 1

# 全部のコマの存在するマスを出力して終了
print(*A_L)

C - Robot Takahashi

問題文

子供と大人があわせてNN人います。ii番目の人の体重はWiW_iです。
それぞれの人が子供か大人かは、01からなる長さNNの文字列SSによって表され、
SSii文字目が0であるときii番目の人が子供であることを、1であるときii番目の人が大人であることをさします。
ロボットである高橋君に対して実数XXを設定すると、高橋君はそれぞれの人に対して、体重がXX未満なら子供、XX以上なら大人と判定します。
実数XXに対してf(X)f(X)を、高橋君にXXを設定したときにNN人のうち子供化大人かを正しく判定できる人数で定めます。
XXが実数全体を動くとき、f(X)f(X)の最大値を求めてください。

制約

  • 1N2×1051 \leq N \leq 2\times10^5
  • SS01からなる長さNNの文字列
  • 1Wi109 1 \leq W_i \leq 10^9
  • N,WiN,W_iは全て整数

考察

  • 問題文を噛み砕くと、
    • 適切な境界の値を決めて、「体重が境界値より大きい大人」と、「体重が境界値未満の子供」の数を最大化したい
  • 大人の中で、AさんとBさんは特に区別していない
    • 60kgの大人が2人と、40kgの大人が1人…其々の名前は気にしてない
    • 子供も同様
      • とりあえず、W1,W2,WNW_1,W_2,…W_Nを、大人と子供に仕分けしたい
      • その後ソートもしてみたい
      • サンプル1で実験実験!
  • 大人と子供で分けてソートしたものを一直線に並べるとこうなった。
  • Xを適当に、とりあえず0で決めてみると…
  • 青色のエリアに含まれた男性と、黄色のエリアに含まれた子供の人数がf(X)f(X)になる
    • この人数を最大化したい
  • 見た限り、X=0X=0の時f(X)=3f(X) = 3X=10X=10の時もf(X)=3f(X) = 3
  • f(X)f(X)の値が変わるまでXを動かしてみる
  • X=31X=31の時、f(X)=2f(X)=2になった。減ってしまった。
    • 目的はf(X)f(X)の最大化
    • とりあえず減ってしまった点は置いておいて、一旦最後の変動まで動かしてみる
  • 上記の実験から、下記のような結果が得られた | X | f(X)| |:-:|:-:| |030|3| |3140|2| |4145|3| |4660|4| |6180|3| |81|2|
  • ここまでで分かったこととして、
    • X=0X=0の時のf(X)f(X)は、大人の人数
    • X=109+1X=10^9+1の時のf(X)f(X)は、子供の数
    • 0から増やしていった時に、XXが大人の体重を超えた時、f(X)f(X)が減る
    • XXが子供の体重を超えた時、f(X)f(X)が増える
      • 同じ体重の大人と子供が存在する時、
      • その値を超えた瞬間のf(X)f(X)は-1+1で相殺される
  • 後は、XXを増やしていってf(X)f(X)の増減を見てあげて、Xの最大値を保持していけばそれが答え
python
from collections import defaultdict

N = int(input())
S = input()
W_L = list(map(int, input().split()))

d = defaultdict(int)

# 前処理:大人と子供で辞書に纏める
# Xを0から増やしていった際に、特定の値を超えた時のスコアの変動を値ごとに纏める
# ついでにX=0の時のf(X):大人の人数をカウントしておく
adult_cnt = 0
for i, w in enumerate(W_L):

    # wが大人の体重の場合
    if S[i] == '1':
        d[w] -= 1
        adult_cnt += 1

    # wが子供の体重の場合
    else:
        d[w] += 1

# スコアが変動する時の値順に並べたいのでリスト化してソート
L = list(d.items())
L.sort()

# scoreの変動と最大値を保持して順に変動を見ていく
score = adult_cnt
ans = adult_cnt

for k, v in L:
    score += v
    ans = max(ans, score)
print(ans)

D - Jumping Takahashi 2

問題文

高橋くんが住んでいる二次元平面上の街にはN個のジャンプ台があります。ii番目のジャンプ台は点(xi,yi)(x_i,y_i)にあり、ジャンプ台のパワーはPiP_iです。
また、高橋君のジャンプ力はSSで表され、はじめS=0S=0です。高橋君が訓練を11回行うたびにSS11増えます。
高橋君は以下の条件を満たす場合に限り、ii番目のジャンプ台からjj番目のジャンプ台にジャンプすることができます。
  • PiSxixj+yiyjP_iS \geq |x_i - x_j| + |y_i - y_j|
高橋君の目的は、適切に始点とするジャンプ台を決めることで、そのジャンプ台からどのジャンプ台にも何回かのジャンプで移動できるようにすることです。
目的を達成するためには高橋君は最低で何回訓練を行う必要があるでしょうか?

制約

  • 2N2002 \leq N \leq 200
  • 109xi,yi109-10^9 \leq x_i,y_i \leq 10^9
  • 1Pi109 1 \leq P_i \leq 10^9
  • (xi,yi)(xj,yj)(i  j)(x_i,y_i) \neq (x_j,y_j)(i \neq j)
  • 入力は全て整数

考察

  • 街の数は最大で200個
    • 街から街への移動パターンはざっくり40000通り
    • 高橋君のジャンプ力を決めてしまえば、O(N2)O(N^2)でグラフを作って、O(N2)O(N^2)でBFSで…全然間に合いそうではある…
  • Sの値が4×1094\times 10^9なら絶対どの地点にも飛べるよねぇ…
    • Sがある値で、始点を適切に選んで全地点に到達可能だったら、それ以上のSは絶対全地点に到達可能よね…
    • 境界が知りたいんだから…
      • そうだ、二分探索しよう
  • ワ―シャルフロイドでも解けるらしい…?
    • 下記ソースで、PyPy3でも2996ms(limit:3s)だったため要改善…?
      • グラフ生成タイミングを修正する事により、大幅時間短縮(274ms)に成功しました
      • 毎回同じグラフ生成してるの、無駄が多かったなと反省…
      • ネギ坊主(twitter:@negibose2020)氏のBFS解法を参考にさせて頂きました…!!!感謝…!!!
python
from collections import deque

# 入力
N = int(input())
L = []

for i in range(N):
    x, y, P = list(map(int, input().split()))
    L.append([x, y, P])


# BFS用のグラフ生成マシーン。高橋君のジャンプ力決めたら辺を張ってくれる凄いロボだよ
def make_graph(exp):
    edge_L = [[] for _ in range(N)]

    for start in range(N - 1):
        sx, sy, sp = L[start]
        for goal in range(start + 1, N):
            gx, gy, gp = L[goal]
            length = abs(sx - gx) + abs(sy - gy)
            if exp * sp >= length:
                edge_L[start].append(goal)
            if exp * gp >= length:
                edge_L[goal].append(start)

    return edge_L


# BFS本体。グラフとスタート地点与えてあげたら、行ける場所の集合を返すよ
def bfs(start, graph):
    can_s = {start}
    que = deque([start])

    while que:
        now = que.popleft()

        for next_idx in graph[now]:
            if next_idx in can_s:
                continue
            que.append(next_idx)
            can_s.add(next_idx)

    return can_s


# めぐる式二分探索、条件判定部分
def is_ok(n):
    # チェックの最初にグラフ生成するよ
    edge_L = make_graph(n)

    # 始点全探索のBFSで、1箇所でも全地点に到達可能ならその時点でTrueなので打ち切っちゃってOK
    for s in range(N):
        if len(bfs(s, edge_L)) == N:
            return True
    return False


# めぐる式二分探索本体
ok, ng = 10 ** 10, -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
print(ok)
  • こっちはワ―シャルフロイド解法
  • PyPy3で241ms。はっやーい!
  • 気持ちとしては、
    • 前準備:各点同士、直接ジャンプする際に必要なジャンプ力を確認
    • ワ―シャルフロイド:
      • 1:「AからBまで直接移動する時に必要なジャンプ力」と、
      • 2:中点midを経由して「Aからmidまでの移動に必要なジャンプ力」と「midからBまでの移動に必要なジャンプ力」 のうち大きい方
      • 1と2の小さい方を「AからBまでの移動に必要なジャンプ力」として更新
    • これを繰り返していくので、前準備にO(N2)O(N^2)、ワ―シャルフロイド部分でO(N3)O(N^3)の計算量で行ける…!!!
python
# 入力
N = int(input())
L = []
 
for i in range(N):
    x, y, P = list(map(int, input().split()))
    L.append([x, y, P])
 
# ワ―シャルフロイド用の必要ジャンプ力テーブルを作って…
# 4*10^9あればどこへでも行ける…!ので、とりあえず余裕もって10^10で初期化
inf = 10**10
wf_L = [[inf] * N for i in range(N)]
 
# 前準備編
# スタート地点から全点に向かって直接移動するのに必要なジャンプ力を拾っていくよ
for start in range(N - 1):
    sx, sy, sp = L[start]
 
    # ここに飛ぶよ!
    for goal in range(start, N):
        
        # 同じところにとどまるだけならジャンプ力は不要なので0埋め
        if start == goal:
            wf_L[start][goal] = 0
            continue
        gx, gy, gp = L[goal]
        
        # startとgoalの間の距離を測って
        length = abs(sx - gx) + abs(sy - gy)
 
        # startからジャンプする時はこのジャンプ力が必要
        costS = -(-length // sp)
        
        # 逆にgoalからジャンプする時はこのジャンプ力が必要
        costG = -(-length // gp)
        
        # それぞれワ―シャルフロイドテーブルにメモするよ
        wf_L[start][goal] = costS
        wf_L[goal][start] = costG
 
# ワ―シャルフロイド編
# midを使ったときに…
for mid in range(N):
    
    # start→goalと、start→mid→goalで必要な最大ジャンプ力を比較してmid使った方がジャンプ力低くても移動可能ならジャンプ力メモ
    for start in range(N):
        for goal in range(N):
            wf_L[start][goal] = min(wf_L[start][goal], max(wf_L[start][mid], wf_L[mid][goal]))

# 最小値が欲しいので、大きいところから答えを更新していくよ
ans = inf
for costs in wf_L:
    # 「地点iから全頂点に移動するために必要な最大値」の最小値、が、答え!
    ans = min(ans, max(costs))
print(ans)

E - Addition and Multiplication 2

問題文

高橋君は整数xxを持っています。最初x=0x=0です。
高橋君は以下の操作を好きな回数行えます。
  • 整数i(1i9)i(1\leq i \leq 9)を選ぶ。CiC_i円払い、xx10x+i10x+iで置き換える。 高橋君の予算はNN円です。操作で支払うお金の操作が予算を超過しないように操作を行うとき、最終的に得られるxxの最大値を求めてください。

制約

  • 1N1061 \leq N \leq 10^6
  • 1CiN1 \leq C_i \leq N
  • 入力は全て整数

考察

  • 数の大小について改めて考える
    • 3桁の数字よりも4桁の数字、4桁の数字よりも5桁の数字が大きい
      • 桁数が大きい方が絶対大きい(ルール1)
    • 桁数が同じ数字の中では、辞書降順のイメージで大小が決まる
      • 先頭の数字が大きい方が絶対大きい(ルール2)
        • 8888 < 9111
  • ルール1より、一番安い整数をいっぱい並べて桁数を稼ぎたい
    • それより多い桁数には絶対出来ないはず
  • その後、先頭の数字を出来る限り貪欲に大きくしていきたい
    • できれば9を置きたいです。9が大きいので
python
# 入力
N = int(input())
C_L = list(map(int, input().split()))
 
# 一番小さいコストと、一番小さいコストの中で一番大きい値が欲しいなー。
min_cost = min(C_L)
min_num = 0
for i, n in enumerate(C_L, 1):
    if n == min_cost:
        min_num = i

# 桁数を決めるじゃないですか。桁数が多いほうが強いので。
keta = N // min_cost
 
# とりあえず一番安くて一番大きい数字で埋めて、頼む
ans_L = [min_num] * keta
 
# 使える残りのお金
amari_yosan = N - (min_cost * keta)

 
# 先頭から順に、数字増やせるかチェック
# 先頭を出来る限り大きい数字にしたほうが強いので、先頭を出来る限り大きい数字にする
# 出来る限り大きい数字にしたら、次の桁で、同じ様に出来る限り大きい数字にする
for i in range(keta):
    now_num = ans_L[i] # 今先頭に仮置されてる数字
    now_price = C_L[now_num - 1] # 今先頭に仮置されてる数字を設置するためのコスト
 
    # 9から順に設置可能か検討。
    # 今置いてる数字より小さい数字にする意味はないので、そこまでのループ
    for num in range(9, min_num, -1):
        # 新しい数字を設置するために必要なコスト
        next_price = C_L[num - 1]
        
        # もし使える残りのお金で、数字が交換できるなら交換してその桁は終了
        if amari_yosan + now_price - next_price >= 0:
            amari_yosan += now_price
            amari_yosan -= next_price
            ans_L[i] = num
            break

# 桁結合して出力!
print("".join(map(str, ans_L)))

Discussion

コメントにはログインが必要です。