日本情報オリンピック第3回女性部門　問題6

日本情報オリンピック第3回女性部門

2023年1月24日
情報オリンピック日本委員会

問題６	タイピング大会 (Typing Contest)　(配点 100点) 　　時間制限 : 2.5 sec / メモリ制限 : 1024 MB

問題文

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, …, N 文字目のキーをこの順に打つことによって文字列 S を入力する．

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

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

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

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

入力は以下の形式で与えられる．
N
S
Q
A₁ L₁ R₁
A₂ L₂ R₂
:
A_Q L_Q R_Q

Q 行出力せよ．i 行目 (1 ≦ i ≦ 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 × 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 の制約を満たす．