F - タイピング大会 (Typing Contest) 解説 /

実行時間制限: 2.5 sec / メモリ制限: 1024 MB

配点： 100 点

問題文

JOIG 国では JOIG 語が使用されており，JOIG 語では文字 A, B, C, D, E, F, G, H, I, J, K, L, M, N, O の 15 種類の文字が用いられる．

来月 JOIG 国で開催されるタイピング大会では，JOIG 語で用いられる 15 種類の文字からなる長さ N の文字列 S を入力するのにかかる時間を競う．この大会では，参加者は以下の条件でタイピングを行う．

  • 参加者は，1 本の指を使ってタイピングをする．
  • 参加者は，15 種類の文字のキー 1 つずつを 1 列に並べた，左右に細長いキーボードを使用する．なお，どの位置にどの文字のキーを配置するかは，各参加者が自由に決めることができる．
  • 参加者は，文字列 S の 1, 2, \dots, N 文字目のキーをこの順に打つことによって文字列 S を入力する．

この大会には Q 人が参加する予定である．参加者によってタイピングの能力は様々である．i 番目 (1 \leqq i \leqq Q) の参加者は，タイピングに際して以下のような時間がかかる．

  • 指の真下にあるキーを 1 回打つのに A_i ミリ秒かかる．
  • 指を 1 つ左のキーの上に移動させるのに L_i ミリ秒かかる．
  • 指を 1 つ右のキーの上に移動させるのに R_i ミリ秒かかる．

文字列 S および各参加者の情報が与えられるので，各参加者に対して，文字列 S の最初の文字を打ち始めてから最後の文字を打ち終わるまでに最短何ミリ秒かかるかを求めるプログラムを作成せよ．

制約

  • 1 \leqq N \leqq 1\,000\,000．
  • S は長さ N の文字列である．
  • S の各文字は A, B, C, D, E, F, G, H, I, J, K, L, M, N, O のいずれかである．
  • 1 \leqq Q \leqq 150\,000．
  • 1 \leqq A_i \leqq 10^{11} (1 \leqq i \leqq Q)．
  • 1 \leqq L_i \leqq 10^{11} (1 \leqq i \leqq Q)．
  • 1 \leqq R_i \leqq 10^{11} (1 \leqq i \leqq Q)．
  • N, Q, A_i, L_i, R_i は整数である．

小課題

  1. (2 点) S の各文字は A である，Q = 1．
  2. (3 点) S の各文字は A, B のいずれかである，Q = 1．
  3. (4 点) S の各文字は A, B, C のいずれかである，Q = 1．
  4. (9 点) S の各文字は A, B, C, D, E, F, G, H のいずれかである，Q = 1，N \leqq 100．
  5. (14 点) S の各文字は A, B, C, D, E, F, G, H のいずれかである，Q = 1．
  6. (26 点) S の各文字は A, B, C, D, E, F, G, H のいずれかである．
  7. (23 点) Q = 1．
  8. (7 点) L_i = R_i (1 \leqq i \leqq Q)．
  9. (12 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．

N
S
Q
A_1 L_1 R_1
A_2 L_2 R_2
\vdots
A_Q L_Q R_Q

出力

Q 行出力せよ．i 行目 (1 \leqq i \leqq Q) には，参加者 i が文字列 S の最初の文字を打ち始めてから最後の文字を打ち終わるまでに最短何ミリ秒かかるかを出力せよ．

入力例 1

6
ABAABB
1
100 150 210

出力例 1

1110

例えば，キーボードの配列を左から順に ONMLKJIHGFEDCBA とすることを考える．このとき，以下の表のような動作を行うことで， 1\,110 ミリ秒で文字列 ABAABB を入力できる．

手順 動作 指の真下にあるキー 時間（ミリ秒）
1 A のキーを打つ A 100
2 指を 1 つ左のキーの上に移動させる A → B 150
3 B のキーを打つ B 100
4 指を 1 つ右のキーの上に移動させる B → A 210
5 A のキーを打つ A 100
6 A のキーを打つ A 100
7 指を 1 つ左のキーの上に移動させる A → B 150
8 B のキーを打つ B 100
9 B のキーを打つ B 100

上に挙げたキーボードの配列以外にも，文字列 ABAABB を同じ時間で入力できるものはあるが，より短い時間で入力することはできない．よって 1\,110 を出力する．

この入力例は小課題 2, 3, 4, 5, 6, 7, 9 の制約を満たす．

入力例 2

6
CBACAB
1
150 240 220

出力例 2

2260

例えば，キーボードの配列を左から順に CABDEFGHIJKLMNO とすることを考える．このとき，以下の表のような動作を行うことで，2\,260 ミリ秒で文字列 CBACAB を入力できる．

手順 動作 指の真下にあるキー 時間（ミリ秒）
1 C のキーを打つ C 150
2 指を 1 つ右のキーの上に移動させる C → A 220
3 指を 1 つ右のキーの上に移動させる A → B 220
4 B のキーを打つ B 150
5 指を 1 つ左のキーの上に移動させる B → A 240
6 A のキーを打つ A 150
7 指を 1 つ左のキーの上に移動させる A → C 240
8 C のキーを打つ C 150
9 指を 1 つ右のキーの上に移動させる C → A 220
10 A のキーを打つ A 150
11 指を 1 つ右のキーの上に移動させる A → B 220
12 B のキーを打つ B 150

上に挙げたキーボードの配列以外でも，文字列 CBACAB を同じ時間で入力できるものはあるが，より短い時間で入力することはできない．よって 2\,260 を出力する．

この入力例は小課題 3, 4, 5, 6, 7, 9 の制約を満たす．

入力例 3

20
AAAAAAAAAAAAAAAAAAAA
1
230000000 80000000 80000000

出力例 3

4600000000

A を 20 回打つことになるので，キーボードの配列にかかわらず，入力し終わるまでに最短で 230\,000\,000 \times 20 = 4\,600\,000\,000 ミリ秒かかる．よって 4\,600\,000\,000 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 4

7
EACHBAG
5
130 104 162
107 219 45
144 168 157
213 79 257
100000000000 100000000000 100000000000

出力例 4

2078
1766
2465
2894
1600000000000

この入力例は小課題 6, 9 の制約を満たす．

入力例 5

19
JOIGCODINGCHALLENGE
5
1 1 1
100 200 200
225 111 111
123456789 987654321 987654321
31415926535 27182818284 27182818284

出力例 5

48
7700
7494
30987654300
1385204334401

この入力例は小課題 8, 9 の制約を満たす．