Problem:


Problem E: 英語の勉強

Problem Statement

会津合宿に参加予定の高槻さんは勉強熱心で、最近は英語の勉強をがんばっている。彼女は、携帯を使って次のようなゲームをプレイすることで、少しでも多く英単語を覚えようとしている。彼女が持っている携帯は、指で画面を操作するタッチパネル式である。

携帯の画面には、4 * 4のマス目が描かれており、各マスにはアルファベット大文字が書かれている。このゲームは、制限時間T秒の間に、マス目の中に隠されている英単語をたくさん見つけ、発見できた英単語の種類により点数を競うものである。

1つの単語を見つける手順は、次のようになる。まず、単語の1文字目に対応する開始マスを決めて、そこに指を置く。そして、今指を置いているマス目から、上下左右・斜めの、隣接する8方向のマスのいずれかに向かって、指でなぞっていく。ただし、開始マスから現在のマスまですでに辿ったことがあるマスは、通ることができない。単語の終了マスに達したら、そこで指を離す。その瞬間、開始マスから終了マスまで指でなぞった単語1つの点数が加点される。x文字の単語1つをなぞるためには、x秒の時間がかかる。ある単語をなぞってから、次の単語をなぞるための指の移動時間は無視してよい。

入力では、加点対象となる単語の辞書も入力される。この辞書の各単語には、点数が振られている。辞書の中に書かれている単語を指でなぞると、その単語に対応する点数が加算される。ただし、開始マスから終了マスまで、全く同じ指のなぞり方をした単語は、最初の1回しか点数加算されない。辞書に書かれていない単語を指でなぞっても加点はされない。

辞書とゲームの盤面が与えられるので、制限時間内に得られる最大の点数を出力せよ。

Input

各データセットは、以下の形式で入力される。

N
word1 score1
word2 score2
...
wordN scoreN
line1
line2
line3
line4
T

Nは、辞書に含まれる単語の数を表わす整数である。続いてN行にわたって、辞書が入力される。wordiは1つの単語を表わすアルファベット大文字で構成される文字列、scoreiはwordiの単語を指でなぞったときに得られる点数を表わす整数である。辞書の中に、同じ単語が2回以上現れることはない。

続いて4行にわたって、各マス目の文字が入力される。lineiは、4文字のアルファベット大文字だけで構成される文字列である。lineiの左からj文字目は、i行目の左からj番目の文字に対応する。

一番最後に、制限時間を表わす整数Tが入力される。

Constraints

1 



Sample input:
6
AIZU 10
LINER 6
LINE 4
ALL 2
AS 1
CIEL 10
ASLA
CILI
IRZN
ELEU
21


Sample output:
40

Submission status: Time Limit Exceeded

Solution code:
def main():
  n = int(input())
  words = []
  scores = []
  for _ in range(n):
    word, score = input().split()
    words.append(word)
    scores.append(int(score))
  mp = ["#" * 6] + ["#" + input() + "#" for _ in range(4)] + ["#" * 6]
  t = int(input())
  
  def search(word):
    used = [[False] * 6 for _ in range(6)]
    vec = ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1))
    
    def _search(word, pos, x, y):
      if pos == len(word) - 1:return 1
      used[y][x] = True
      ret = 0
      for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if not used[ny][nx] and mp[ny][nx] == word[pos + 1]:
          ret += _search(word, pos + 1, nx, ny)
      used[y][x] = False
      return ret
    
    ret = 0
    for y in range(1, 5):
      for x in range(1, 5):
        if mp[y][x] == word[0]:ret += _search(word, 0, x, y)  
    return ret
  
  values = []
  weights = []
  for word, score in zip(words, scores):
    cnt = search(word)
    for _ in range(cnt):
      values.append(score)
      weights.append(len(word))
  
  dp = [0] * (t + 1)
  for v, w in zip(values, weights):
    for x in range(max(-1, t - w), -1, -1):
      dp[x + w] = max(dp[x + w], dp[x] + v)
  print(max(dp)) 

main()

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  words = []
  scores = []
  for _ in range(n):
    word, score = input().split()
    words.append(word)
    scores.append(int(score))
  mp = ["#" * 6] + ["#" + input() + "#" for _ in range(4)] + ["#" * 6]
  t = int(input())
  
  def search(word):
    used = [[False] * 6 for _ in range(6)]
    vec = ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1))
    
    def _search(word, pos, x, y):
      if pos == len(word) - 1:return 1
      used[y][x] = True
      ret = 0
      for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if not used[ny][nx] and mp[ny][nx] == word[pos + 1]:
          ret += _search(word, pos + 1, nx, ny)
      used[y][x] = False
      return ret
    
    ret = 0
    for y in range(1, 5):
      for x in range(1, 5):
        if mp[y][x] == word[0]:ret += _search(word, 0, x, y)  
    return ret
  
  values = []
  weights = []
  for word, score in zip(words, scores):
    cnt = search(word)
    acc = 1
    while cnt >= acc:
      cnt -= acc
      values.append(score * acc)
      weights.append(len(word) * acc)
      acc *= 2
    if cnt:
      values.append(score * cnt)
      weights.append(len(word) * cnt)
  
  dp = [0] * (t + 1)
  for v, w in zip(values, weights):
    for x in range(max(-1, t - w), -1, -1):
      dp[x + w] = max(dp[x + w], dp[x] + v)
  print(max(dp)) 

main()

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  lst = []
  for _ in range(n):
    word, score = input().split()
    lst.append((word, int(score)))
  mp = ["#" * 6] + ["#" + input() + "#" for _ in range(4)] + ["#" * 6]
  t = int(input())
  
  def search(word):
    used = [[False] * 6 for _ in range(6)]
    vec = ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1))
    
    def _search(word, pos, x, y):
      if pos == len(word) - 1:return 1
      used[y][x] = True
      ret = 0
      for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if not used[ny][nx] and mp[ny][nx] == word[pos + 1]:
          ret += _search(word, pos + 1, nx, ny)
      used[y][x] = False
      return ret
    
    ret = 0
    for y in range(1, 5):
      for x in range(1, 5):
        if mp[y][x] == word[0]:ret += _search(word, 0, x, y)  
    return ret
  
  items = []
  for word, score in lst:
    cnt = search(word)
    acc = 1
    weight = len(word)
    while cnt >= acc:
      cnt -= acc
      items.append((score * acc, weight * acc))
      acc *= 2
    if cnt:
      items.append((score * cnt, weight * cnt))
  
  dp = [0] * (t + 1)
  for v, w in items:
    for x in range(t - w, -1, -1):
      if dp[x + w] < dp[x] + v:dp[x + w] = dp[x] + v
  print(max(dp)) 

main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict,deque
def dfs(d,f,y,x):
    if d == len(w):
        m[k] += 1
    else:
        for dy,dx in move:
            y_ = y+dy
            x_ = x+dx
            if 0 <= y_ < 4 and 0 <= x_ < 4:
                if f[y_][x_]:
                    if s[y_][x_] == w[d]:
                        f[y_][x_] = 0
                        dfs(d+1,f,y_,x_)
                        f[y_][x_]= 1
move = [(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]
n = int(sys.stdin.readline())
word = [sys.stdin.readline().split() for i in range(n)]
s = [sys.stdin.readline()[:-1] for i in range(4)]
W = int(sys.stdin.readline())
m = [0]*n
q = deque()
k = 0
for w,p in word:
    for b in range(4):
        for a in range(4):
            if s[b][a] == w[0]:
                f = [[1]*4 for i in range(4)]
                f[b][a] = 0
                dfs(1,f,b,a)
    k += 1

w = [len(word[i][0]) for i in range(n)]
v = [int(word[i][1]) for i in range(n)]
dp = [0]*(W+1)
deq = [0]*(W+1)
deqv = [0]*(W+1)
for i in range(n):
    for a in range(w[i]):
        s = 0
        t = 0
        j = 0
        while j*w[i]+a <= W:
            val = dp[j*w[i]+a]-j*v[i]
            while s < t and deqv[t-1] <= val:t -= 1
            deq[t] = j
            deqv[t] = val
            t += 1
            dp[j*w[i]+a] = deqv[s]+j*v[i]
            if deq[s] == j-m[i]:
                s += 1
            j += 1
print(dp[W])