塩見周子の徒然日記

自分のことを塩見周子と思い込んでいるオタクです

3/31 AtCoder（半分全列挙、二分探索）

精進(python3)

こんばんは。1ACするのが重くなってきてだんだん競プロモチベが下がっているとーです。

ABC018D

問題が長くて怠い

女子N,男子M人がいる中から女子P,男子Q人を選ぶ。女子x_iと男子y_i一人ずつの組に対してz_iというパラメータがいくつか与えられており、男子と女子を適切にP,Q人選ぶことによってこのパラメータの合計を最大化しましょうねという趣旨の問題

N,Mが小さければ、男子女子の選び方はNCP*MCQだから全列挙するのもありかもしれないけどそれが厳しそう　　というわけで女子だけ全列挙する方針をとる（半分全列挙という）

女子だけ列挙した場合（最悪2**18だから大体10**7くらい　ギリギリ）、
①女子を列挙
②男子全員分の長さを持った0埋めリストをつくる
③パラメータに対し、女子が列挙した中に入っていれば（x_iがあれば）それに対応する男子y_iの所にz_iを足す
④これをR回やって、男子のリストを降順にソート→上からQ人とる　この合計値を更新していく

というアルゴリズムで何とかなる
（最初、パラメータを大きい方から見ていって、男子がQ人になるまで足す方針をとっていたが、それだと後ろの方にめっちゃ小さい値を持っているけど合計的には他よりも大きくなりうるケースを省いてしまっていたのでこれは通らなかった　貪欲に取ると言っても一回全部確かめてみないとね）
制約がN<=18とかの時はこれを疑ってみるとよいかもしれない

以下はpython3による答えのコード

N,M,P,Q,R = map(int,input().split())
L = []
for i in range(R):
  L.append(list(map(int,input().split())))
L = sorted(L, key = lambda x:x[2])
L.reverse()
def Base_10_to_n(X,n):
  if (int(X/n)):
    return Base_10_to_n(int(X/n),n)+str(X%n)
  return str(X%n)
ans = 0
for X in range(2**N):
  n = 2
  STR = Base_10_to_n(X,n).zfill(N)
  cnt = 0
  for i in range(N):
    if STR[i] == '1':
      cnt += 1
  if cnt == P:
    cur = 0
    jyoshi = []
    for j in range(N):
      if STR[j] == '1':
        jyoshi.append(j+1)
    danshi = [0]*M
    for k in range(R):
      if L[k][0] in jyoshi:
        danshi[L[k][1]-1] += L[k][2]
    danshi.sort()
    danshi.reverse()
    for l in range(Q):
      cur += danshi[l]
    if cur >= ans:
      ans = cur
print(ans)


ARC017C

これも半分全列挙が使える問題
重さの合計がXになればよいので、品物を前後半に分けて、前半で作れる重さを全列挙し、後半で作れる重さpに対して前半で作れるX-pがいくつあるかを二分探索で求めれば行ける

以下はpython3による答えのコード

import bisect
N,T = map(int,input().split())
L = []
for i in range(N):
  L.append(int(input()))
zen = []
def Base_10_to_n(X,n):
  if (int(X/n)):
    return Base_10_to_n(int(X/n),n)+str(X%n)
  return str(X%n)
n = 2
P = []
Q = []
ans = 0
for i in range(N//2):
  P.append(L[i])
for j in range(N//2,N):
  Q.append(L[j])
if N%2 == 0:
  for X in range(n**(N//2)):
    STR = Base_10_to_n(X,n).zfill(N//2)
    cur = 0
    for i in range(N//2):
      if STR[i] == '1':
        cur += P[i]
    zen.append(cur)
  zen.sort()
  for X in range(n**(N//2)):
    STR = Base_10_to_n(X,n).zfill(N//2)
    sub = 0
    for i in range(N//2):
      if STR[i] == '1':
        sub += Q[i]
    k = bisect.bisect_left(zen,T-sub)
    l = bisect.bisect_right(zen,T-sub)
    ans += l-k
else:
  for X in range(n**(N//2)):
    STR = Base_10_to_n(X,n).zfill(N//2)
    cur = 0
    for i in range(N//2):
      if STR[i] == '1':
        cur += P[i]
    zen.append(cur)
  zen.sort()
  for X in range(n**(N//2+1)):
    STR = Base_10_to_n(X,n).zfill(N//2+1)
    sub = 0
    for i in range(N//2+1):
      if STR[i] == '1':
        sub += Q[i]
    k = bisect.bisect_left(zen,T-sub)
    l = bisect.bisect_right(zen,T-sub)
    ans += l-k
print(ans)

ABC079D

0~9までの10個の数字を選び、それをi,jとしたとき、iからjに変換するコストが与えられる
何回か操作を行って、入力された数字をすべて1に変換するのに必要な最小コストはなんぼ？という問題

高々100通りの組合せなので、ここは0~10を頂点に持ち、辺の数が100本あるグラフと考えて、ワーシャルフロイドで最短経路を出すという方針で行けば簡単に求まる
ただしいつもの最短経路問題のように往復するコストが等しいわけではないことに注意

以下はpython3による答えのコード

from scipy.sparse.csgraph import floyd_warshall
h,w = map(int,input().split())
cost = []
for i in range(10):
  sub = list(map(int,input().split()))
  cost.append(sub)
d = [[float("inf")]*10 for i in range(10)]
L = []
for i in range(10):
    d[i][i] = 0
for i in range(10):
    for j in range(10):
        d[i][j] = cost[i][j]
        d[j][i] = cost[j][i]
d = floyd_warshall(d)
wall = []
for i in range(h):
    cur = list(map(int,input().split()))
    wall.append(cur)
ans = 0
for i in range(h):
    for j in range(w):
        if wall[i][j] != -1:
            ans += d[wall[i][j],1]
print(int(ans))

ABC122D

本番中にACできなかったやつ　やっとACしました

dpを使います
T,A,G,Cをそれぞれ0,1,2,3に対応させ、N文字目までOK、かつ末尾の3文字がa,b,cであるような文字列のパターン数をdp[N][a][b][c]とします
dp[N+1][b][c][d]に遷移させたいわけですが、遷移できるものを考えるより遷移できないものを考えた方がよいです（まあそれはそう）

ダメなパターンは、
①abcにdをくっつけたとき、bcd（新たな末尾）がAGC,ACG,GACのいずれかになる場合
②abcにdをくっつけたとき、abcdがA〇GC,AG〇Cのいずれか（〇はT,A,G,Cのいずれか）になる場合
の二パターンなので、これを除くようにして遷移させていけばよい
直近の4文字についてのみ考えればよいと分かれば楽です

初期状態の置き方がめちゃくちゃ困るのですが、これは「後に適当につけていってもアウトにならない」=='TTT'の形であればよいので、dp[0][0][0][0]=1としてスタートしてあげればよい

解き方さえわかれば実装が楽......かと思いきや普通にdpのリストを組むのに苦労しました

atcoder.jp



エクサウィザーズ C

本番中にACできなかったので直し

ゴーレム同士の相対的な位置の変化はない（あるゴーレムがほかのゴーレムと同じ位置に来ることはあっても、ほかのゴーレムを追い越すことはない）ということを利用し、

「左側に落ちるゴーレムで最も右側にいるやつを見つければ、それより左側にいるやつはみんな左側に落ちる」
と考えられれば、あとは右側にも同じ考え方を適用してあげればよい

それを発見するのが二分探索で、ライブラリにあるものではないやつで運用する
書いてみたはいいもののなんもわかんないので練習が必要

N,Q = map(int,input().split())
s = input()
L = []
for i in range(Q):
  L.append(list(input().split()))
def judge_left(x):  #左に落ちるものを判定する xは位置を表す
  for i in range(Q):
    if L[i][0] == s[x]:
      if L[i][1] == 'L':
        x -= 1
      else:
        x += 1
    if x == -1:  #左端まで到達すれば
      return True
    if x == N:  #逆に右端に到達してしまった場合は
      return False
  return False  #いずれでもなければ
def judge_right(x):  #右でも同じことをします
  for i in range(Q):
    if L[i][0] == s[x]:
      if L[i][1] == 'L':
        x -= 1
      else:
        x += 1
    if x == -1:
      return False
    if x == N:
      return True
  return False

ok = -1  #左端で「ここまでのゴーレムは確実に落ちる」というのを決める
ng = N  #右端はN
while ng-ok > 1:  #ng-okの間が1より大きいなら
  mid = (ng+ok)//2  #半分の所を見る
  if judge_left(mid):  #それが左端に落ちるかどうかをみて
    ok = mid  #落ちるなら、okのラインを右側に進める
  else:
    ng = mid
left = ok+1

ok = N
ng = -1
while ok-ng > 1:
  mid = (ng+ok)//2
  if judge_right(mid):
    ok = mid
  else:
    ng = mid
right = N-ok
print(max(N-left-right,0))  #left+right>Nとなったときを回避

こちらの記事を参考にさせていただきました　ありがとうございました
juppy.hatenablog.com