白駿9184号「ワクワクする関数を実行する」


質問する


白準9184回興奮関数の実行

に答える


問題には似たようなコードが書かれていて、難題ではありません.
ただし、類似コードに従ってコードを実装すると無条件のタイムアウトが発生するので、コメントバージョンを使用しましょう.
注釈
  • と同じ計算を繰り返す必要がある場合は、計算結果をメモリに保存し、
  • を取り出して書き込みます.
  • DPのコア!
  • Pythonコード

    import sys
    
    input = sys.stdin.readline
    
    arr = [[[0]*21 for i in range(21)] for j in range(21)]
    
    
    def w(a, b, c):
      if a<=0 or b<=0 or c<=0:
        return 1
      elif a>20 or b>20 or c>20:
        return w(20,20,20)
      elif arr[a][b][c]:
        return arr[a][b][c]
      elif a<b<c:
        arr[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return arr[a][b][c]
      else:
        arr[a][b][c] = w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)
        return arr[a][b][c]
    
    while 1:
      a,b,c=map(int, input().split())
    
      if (a,b,c)==(-1,-1,-1):
        break
    
      print(f'w({a}, {b}, {c}) = {w(a, b, c)}')