サクっと解けたものの、自分の読解力がなすぎるのか、解説の言ってることが全く分からず・・・まさか嘘回答？

方針としてはこう

まず正しい括弧列は消えるイメージとする（ぷよぷよ的な）
与えられたSで消えるものは全部消しきるまで、走査を繰り返す。文字数短いので
消えるものが消え切った後の状態は、もう消えうるカッコがない。すなわち、以下の3パターンの組み合わせからしか成立しない
1. 左から始まり、右まで続くかもしれない)))...
2. 右から始まり、左まで続くかもしれない(((...
3. これらの中間に一度だけありうる)(
よって、以下をやればOK
1. 左から走査して、)の数だけ(を答えの左にくっつける
2. 右から走査して（これが苦手なので、反転した文字列を左から走査している）、(の数だけ)を答えの右にくっつける

・・・これで通ったんだけど、解説が理解できないだけに、嘘回答じゃないか若干不安。いや、合ってるよな・・・

def resolve():
  N=int(input())
  S=input()
 
  Temp=S
  while True:
    Temp=Temp.replace("()","")
    if not "()" in Temp:
      break
 
  ans=S
 
  for t in Temp:
    if t==")":
      ans="("+ans
    else:
      break
 
  for t in Temp[::-1]:
    if t=="(":
      ans=ans+")"
    else:
      break
    
  print(ans)

2021-03-04

ABC085 D - Katana Thrower

atcoder.jp

最近は緑Diffを解いてみてる。この問題、サクっと考察・実装できたものの、1WAが全然取れず苦戦した。

どこかというと if(H>0):がなかったわけだけど、こうするとb（投げつける）で削りきったのに、 a（切り付ける）を処理してしまうので、NG。ただし、bでちょうど削りきる場合は、残Hが0なので、これでもバグらない。

それもあって、テストケースにNG例が1つしか含まれていなくて、大枠はあってそうなので、コーナーケース？と混乱したりした。 WAが少ないからと言って、コーナーケースばかり疑ってはいけないという教訓。。。

def resolve():
  N,H=map(int,input().split())

  ans=0

  a=[0]*N
  b=[0]*N
  
  for i in range(N):
    a[i],b[i]=map(int,input().split())

  a=sorted(a,reverse=True)
  b=sorted(b,reverse=True)

  for i in range(N):
    if(H<=0):
      break
    if(a[0]<b[i]):
      H-=b[i]
      ans+=1
    
  if(H>0):
    ans+=math.ceil(H/a[0])

  print(ans)

2021-02-08

ABC054 B - Template Matching

atcoder.jp

緑Diffひたすら解いて精進中。。。

この問題自体はあまりハマるところはなかったけど、Yes/Noの出力が何とかならんかなあと思い、今更、三項演算子の使い方を知る。毎回書いてもいいレベルかもしれない。関数内にいろいろ隠ぺいしようと思ったけど、論理を投げ込む方が、呼び出し元から分かりやすい気もして、行数は変わらないけど、この辺が落としどころかなあと。

def yn(isYes):
  print("Yes") if isYes else print("No")
  return

def resolve():
  N,M=map(int,(input().split()))
  A=[""]*N
  B=[""]*M

  for i in range(N):
    A[i]=input()

  for i in range(M):
    B[i]=input()

  found=False
  for ii in range(N-M+1):
    for jj in range(N-M+1):
      isOK=True
      for i in range(M):
        for j in range(M):
          if(A[ii+i][jj+j]!=B[i][j]):
            isOK=False
      if(isOK):
        found=True

  yn(found)

2021-02-04

ARC080 D - Grid Coloring

atcoder.jp

解説（右左に1段ずつ下がりながら塗っていく）を見た今となっては何故・・・という解法だけど、「外周を（まだ塗ってないマスを探し）ぐるぐる回りながら塗っていく」という、最初に閃いたネタに固執してしまい、やたら苦労した。ちょっと面白いコードになった気がするので、掲載。

現在地と盤面のサイズから、外周をなぞるために次に行くべき方向を計算（check関数）
１マスごとに塗るべき色リストを作成（colors）
あとは画素数（画像処理のイメージでやっている…）でループを回し、初期位置(0,0)から、1処理ごとに現在地を塗って、進むべき方向に進んで、を繰り返す。
⇒ 外周を回り込むタイプの出力ができる

1 2 2 3 3
5 5 5 5 3
5 4 4 4 4

#  1
#4 # 2
#  3
def check(HW,h,w,H,W):
  if w<W and HW[h][w+1]==0:
    return 2
  if h<H and HW[h+1][w]==0:
    return 3
  if w>0 and HW[h][w-1]==0:
    return 4
  if h>0 and HW[h-1][w]==0:
    return 1
    

def resolve():
  H,W=map(int,input().split())
  N=int(input())
  A=list(map(int,input().split()))

  colors=[]
  for i in range(N):
    for j in range(A[i]):
      colors.append(i+1)

  ans = [[0 for j in range(W)] for i in range(H)]
  curH=0
  curW=0

  for i in range(H*W):
    checkres=check(ans,curH,curW,H-1,W-1)
    ans[curH][curW]=colors[i]
    if(checkres==2):
      curW+=1
    elif(checkres==3):
      curH+=1
    elif(checkres==4):
      curW-=1
    elif(checkres==1):
      curH-=1
      
  for i in range(H):
    for j in range(W):
      print(ans[i][j],end=" ")
    print("")

2021-02-01

ABC129 C - Typical Stairs

atcoder.jp

地味にまともなDP解いたのは初かもしれない。 DP典型を逃しまくってるので、まだまだ強化必要だなあ。

dpの状態数は開始位置を含むN+1とした（遷移先がN段目まである）
壊れてる階段の数はMだけど、最大でたかだかN-1なので、-1（存在しない段）のN+1個で雑に初期化
壊れてる段は集合にして、存在確認することとした
- けど、解説にある通り、該当位置が壊れているか、のテーブル持つ方が賢い気もする。今回の制約（壊れてる段はそれぞれユニーク）だと集合でも問題なさそうか・・・
遷移は、①1段前から登ってくる＋②2段前から登ってくる　の単に合計。ただし壊れてる段（壊れてる段集合にヒット）の場合は0、とした

def resolve():
  N,M=map(int,input().split())
  A=[-1]*(N+1)
  dp=[0]*(N+1)
  MOD=10**9+7

  if(M!=0):
    for i in range(M):
      A[i]=int(input())

  A=set(A)
  dp[0]=1
  dp[1]=1
  if(1 in A):
    dp[1]=0

  for i in range(2,N+1):
    if(i in A):
      dp[i]=0
    else:
      dp[i]=(dp[i-1]%MOD+dp[i-2]%MOD)%MOD

  print(dp[N])

こんだけで解けてちょっと感動。実は事前に「2つ破損が続いたら答えは0」みたいな条件たくさん作らんといかんと思っていたけど、dpで全部辻褄あっててキレイ。dpはうつくしい。

2021-02-01

ABC076 C - Dubious Document 2

atcoder.jp

そもそも全パターン試さないといけないことに気づかず、WA連発していたが、気づいたところで、なかなか実装し切れなかった。意外とPythonでの文字列の置換や結合でハマったのでメモ。

文字列に対して、部分の置き換えはできない
- replaceを使えばできるが、開始位置の指定はできない
文字列のままでも、スライスを使って
　①置換対象の前＋②置換後文字列＋③置換対象の後
と組み合わせてあげればよいが、添え字で混乱するので苦手
一度リストにして、置換後文字列を投げ込んで、また文字列に戻すのが、可読性いい気がする（個人の好みです）
（同じ長さの）複数文字列から１文字ずつ取り出して、それぞれ突き合わせるようなときは、for in にzip組み合わせると便利

def resolve():
  S=input()
  T=input()

  cand=[]
  for i in range(len(S)-len(T)+1):
    temp=S[i:i+len(T)]
    isMatch=True
    for (s,t) in zip(temp,T):
      if(s!=t and s!="?"):
        isMatch=False
    if isMatch:
      tempS=list(S)
      tempS[i:i+len(T)]=T
      tempS="".join(tempS)
      tempS=tempS.replace("?","a")
      cand.append(tempS)

  if len(cand)==0:
    print("UNRESTORABLE")  
  else:
    cand.sort()
    print(cand[0])

2021-01-17

ABC167 D - Teleporter

atcoder.jp

Pythonです。精進しててえらいハマったので、なるべく分かりやすいソースにしてみたつもり。ループしてなければ何事もなく終わるし、ループを検知したら、ループに戻る前にループサイクルを加味して、あと何移動すべきか決めたうえでループに飛び込んで終わる、、、ような感じ。 0-indexedに直すとそれはそれで混乱するし、悩ましい。

def resolve():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))

    checked= [0]*N

    Cur=1
    Next=0
    LoopDetect=False
    for i in range(K):
        if(checked[Cur-1]==0):
            checked[Cur-1]+=i
        Next=A[Cur-1]
        if(checked[Next-1]!=0):
            LoopDetect=True
            break
        Cur=Next


    if(LoopDetect):
        Cycle=i-checked[Next-1]+1
        amari=(K-i)%Cycle

        for i in range(amari):
            Next=A[Cur-1]
            Cur=Next

    print(Cur)

resolve()

いむらや競プロ雑記

キーワード：競プロ、育児、石川県

ABC064 D - Insertion

ABC085 D - Katana Thrower

ABC054 B - Template Matching

ARC080 D - Grid Coloring

ABC129 C - Typical Stairs

ABC076 C - Dubious Document 2

ABC167 D - Teleporter