ビーズを一列に通す図案がある。 ビーズの色は英小文字一文字で書く。 図案は、部品を一つ以上、空白なしで続けて書いたものだ。 部品はビーズ一つか、まとまりだ。 まとまりは k(図案) の形で書き、かっこの中の図案を k 回くり返して通すという意味だ。 たとえば a2(bc) のとおりに通すと abcbc になり、2(a2(b)) のとおりに通すと abbabb になる。 図案ごとに二文字 xy がいっしょに与えられる。 図案のとおりに通し終えた列で、x 色のビーズのすぐ次に y 色のビーズが来る場所が何か所あるかを求める。 一行目に図案の数 t が与えられる。 続く t 行に、一行に一つずつ、二文字 xy と図案が空白一つで区切って与えられる。 図案ごとに、場所の数を一行に一つずつ出力する。
入力
1 ≤ t ≤ 20。 x と y は英小文字で、同じこともある。 図案の長さの合計は 100,000 以下。 k は 1 以上 10^9 以下の整数で、0 で始まらない。 かっこの中の図案は空ではない。 まとまりの入れ子の深さは 3,000 以下。 通し終えた列のビーズは 10^15 個以下
出力
図案ごとに、x のすぐ次に y が来る場所の数を一行に一つずつ
例 1 · stdin
5
ba 3(ab)
ab a2(b)
ab 2(ca)b
ba 2(3(a)b)
aa 12(a)
stdout
2
1
1
1
11
例 2 · stdin
2
ab 1000000(1000000(ab))
xy 3(x2(y))
stdout
1000000000000
3
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
通し終えた列のビーズは 10^15 個まであるので、図案を実際に広げて数えるのはどの言語でも終わりません。 代わりに、まとまりごとに三つだけ覚えます。 中で数えた場所の数、最初のビーズ、最後のビーズです。 ( に出会ったらそこまで読んだものをスタックに積んで新しく始め、) に出会ったらスタックから取り出して合わせます。 内側のまとまりが k 回くり返されると場所の数は k 倍になり、最後のビーズが x で最初のビーズが y なら、くり返しの間のつなぎ目 k - 1 か所が加わります。 スタックは、Python はリストにタプルを append・pop し、JS は配列に push・pop します。 TS は stack.pop() の型が Frame | undefined なので、そのまま使うと型エラー（TS18048）になり、as Frame と知らせる必要があります。 Java は ArrayDeque<long[]> の push・pop、C# はタプルを入れた Stack<...> の Push・Pop を使います。 C は構造体の配列といちばん上の番号 top で自分で作ります。 C++ の std::stack は pop() が値を返さないので、先に top() で読んでから pop() します。 Craykon は四つのリストに 追加 で積み、最後の値を読んでから 位置で取り除く で取り除きます。 答えは 10^15 近くになることがあるので、Java・C# は long、C・C++ は long long に入れます。 JS・TS の number と Craykon の数はこの範囲で正確で、Python の整数には大きさの制限がありません。 罠その一：くり返しの間のつなぎ目を忘れてはいけません。 ba 3(ab) は ababab なので 2 ですが、0 が出ます。 罠その二：まとまりのすぐ前のビーズと、まとまりの最初のビーズも隣どうしです。 ab a2(b) は abb なので 1 ですが、数えないと 0 が出ます。 罠その三：まとまりを閉じたら、最後のビーズはそのまとまりの最後のビーズになります。 変えないと ab 2(ca)b（cacab）が 1 ではなく 0 になります。 罠その四：まとまりがまとまりで始まるなら、内側のまとまりの最初のビーズが外側のまとまりの最初のビーズです。 渡さないと ba 2(3(a)b)（aaabaaab）が 1 ではなく 0 になります。 罠その五：回数は何桁もあることがあります。 最後の数字だけを残すと aa 12(a) が 11 ではなく 1 になります。 罠その六：Java で場所の数を int に入れると、二つ目の例の一行目が 1000000000000 ではなく -727379968 になります。 罠その七：Python でスタックの代わりにまとまりごとに関数を呼び直すと、3,000 重に入れ子になった図案で RecursionError で止まります。 例には現れません。 罠その八：Craykon でまとまりを回数だけ実際にくり返して読むと、二つ目の例の一行目で「時間がかかりすぎます」という知らせとともに止まります。
Pythonmain.py · 46 行
import sysdef count_pairs(x, y, design): """다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수""" stack = [] # 바깥 묶음들: (자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수) count, first, last = 0, "", "" # 지금 읽고 있는 묶음. 구슬이 아직 없으면 "" times = 0 for ch in design: if ch.isdigit(): times = times * 10 + int(ch) elif ch == "(": stack.append((count, first, last, times)) count, first, last, times = 0, "", "", 0 elif ch == ")": in_count, in_first, in_last = count, first, last count, first, last, k = stack.pop() total = in_count * k if in_last == x and in_first == y: # 되풀이 사이의 이음매 k - 1곳 total += k - 1 if last == x and in_first == y: # 묶음 앞 구슬과 묶음의 첫 구슬 사이 total += 1 count += total if first == "": first = in_first last = in_last else: if last == x and ch == y: count += 1 if first == "": first = ch last = ch return countdef main(): lines = sys.stdin.read().split("\n") t = int(lines[0]) out = [] for line in lines[1:t + 1]: pair, design = line.split() out.append(str(count_pairs(pair[0], pair[1], design))) print("\n".join(out))main()
JavaScriptmain.js · 40 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");// 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수function countPairs(x, y, design) { const stack = []; // 바깥 묶음들: [자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수] let count = 0, first = "", last = ""; // 지금 읽고 있는 묶음. 구슬이 아직 없으면 "" let times = 0; for (const ch of design) { if (ch >= "0" && ch <= "9") { times = times * 10 + Number(ch); } else if (ch === "(") { stack.push([count, first, last, times]); count = 0; first = ""; last = ""; times = 0; } else if (ch === ")") { const inCount = count, inFirst = first, inLast = last; const outer = stack.pop(); count = outer[0]; first = outer[1]; last = outer[2]; const k = outer[3]; let total = inCount * k; // 10^15 이하라서 number로 정확하다 if (inLast === x && inFirst === y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last === x && inFirst === y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first === "") first = inFirst; last = inLast; } else { if (last === x && ch === y) count += 1; if (first === "") first = ch; last = ch; } } return count;}const t = Number(lines[0]);const out = [];for (let i = 1; i <= t; i++) { const [pair, design] = lines[i].trim().split(" "); out.push(countPairs(pair[0], pair[1], design));}console.log(out.join("\n"));
TypeScriptmain.ts · 49 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");// 바깥 묶음 하나: 자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수interface Frame { count: number; first: string; last: string; times: number;}// 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수function countPairs(x: string, y: string, design: string): number { const stack: Frame[] = []; let count = 0, first = "", last = ""; // 지금 읽고 있는 묶음. 구슬이 아직 없으면 "" let times = 0; for (const ch of design) { if (ch >= "0" && ch <= "9") { times = times * 10 + Number(ch); } else if (ch === "(") { stack.push({ count, first, last, times }); count = 0; first = ""; last = ""; times = 0; } else if (ch === ")") { const inCount = count, inFirst = first, inLast = last; const outer = stack.pop() as Frame; // 도안이 올바르므로 스택은 비어 있지 않다 count = outer.count; first = outer.first; last = outer.last; const k = outer.times; let total = inCount * k; // 10^15 이하라서 number로 정확하다 if (inLast === x && inFirst === y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last === x && inFirst === y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first === "") first = inFirst; last = inLast; } else { if (last === x && ch === y) count += 1; if (first === "") first = ch; last = ch; } } return count;}const t = Number(lines[0]);const out: number[] = [];for (let i = 1; i <= t; i++) { const [pair, design] = lines[i].trim().split(" "); out.push(countPairs(pair[0], pair[1], design));}console.log(out.join("\n"));
JavaMain.java · 49 行
import java.io.*;import java.util.*;public class Main { // 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수 static long countPairs(char x, char y, String design) { // 바깥 묶음들을 쌓아 두는 스택. 구슬이 아직 없으면 첫 구슬과 끝 구슬은 0 ArrayDeque<long[]> stack = new ArrayDeque<>(); // {자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수} long count = 0, times = 0; char first = 0, last = 0; for (int i = 0; i < design.length(); i++) { char ch = design.charAt(i); if (Character.isDigit(ch)) { times = times * 10 + (ch - '0'); } else if (ch == '(') { stack.push(new long[]{count, first, last, times}); count = 0; first = 0; last = 0; times = 0; } else if (ch == ')') { long inCount = count; char inFirst = first, inLast = last; long[] outer = stack.pop(); count = outer[0]; first = (char) outer[1]; last = (char) outer[2]; long k = outer[3]; long total = inCount * k; // int로는 넘친다 if (inLast == x && inFirst == y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last == x && inFirst == y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first == 0) first = inFirst; last = inLast; } else { if (last == x && ch == y) count += 1; if (first == 0) first = ch; last = ch; } } return count; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine().trim()); StringBuilder sb = new StringBuilder(); for (int i = 0; i < t; i++) { String[] parts = br.readLine().trim().split(" "); sb.append(countPairs(parts[0].charAt(0), parts[0].charAt(1), parts[1])).append('\n'); } System.out.print(sb); }}
C#Main.cs · 59 行
using System;using System.Collections.Generic;using System.Text;class Program{ // 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수 static long CountPairs(char x, char y, string design) { // 바깥 묶음들을 쌓아 두는 스택. 구슬이 아직 없으면 첫 구슬과 끝 구슬은 '\0' var stack = new Stack<(long count, char first, char last, long times)>(); long count = 0, times = 0; char first = '\0', last = '\0'; foreach (char ch in design) { if (char.IsDigit(ch)) { times = times * 10 + (ch - '0'); } else if (ch == '(') { stack.Push((count, first, last, times)); count = 0; first = '\0'; last = '\0'; times = 0; } else if (ch == ')') { long inCount = count; char inFirst = first, inLast = last; long k; (count, first, last, k) = stack.Pop(); long total = inCount * k; // int로는 넘친다 if (inLast == x && inFirst == y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last == x && inFirst == y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first == '\0') first = inFirst; last = inLast; } else { if (last == x && ch == y) count += 1; if (first == '\0') first = ch; last = ch; } } return count; } static void Main() { int t = int.Parse(Console.ReadLine()!.Trim()); var sb = new StringBuilder(); for (int i = 0; i < t; i++) { string[] parts = Console.ReadLine()!.Trim().Split(' '); sb.Append(CountPairs(parts[0][0], parts[0][1], parts[1])).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 57 行
#include <cctype>#include <iostream>#include <stack>#include <string>// 바깥 묶음 하나. 구슬이 아직 없으면 first와 last는 0struct Frame { long long count; char first, last; long long times;};// 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수long long countPairs(char x, char y, const std::string& design) { std::stack<Frame> stack; long long count = 0, times = 0; char first = 0, last = 0; for (char ch : design) { if (std::isdigit(static_cast<unsigned char>(ch))) { times = times * 10 + (ch - '0'); } else if (ch == '(') { stack.push({count, first, last, times}); count = 0; first = 0; last = 0; times = 0; } else if (ch == ')') { long long inCount = count; char inFirst = first, inLast = last; Frame outer = stack.top(); // top()은 보기만 하고, 꺼내는 것은 pop()이다 stack.pop(); count = outer.count; first = outer.first; last = outer.last; long long k = outer.times; long long total = inCount * k; // int로는 넘친다 if (inLast == x && inFirst == y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last == x && inFirst == y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first == 0) first = inFirst; last = inLast; } else { if (last == x && ch == y) count += 1; if (first == 0) first = ch; last = ch; } } return count;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t; std::cin >> t; for (int i = 0; i < t; i++) { std::string pair, design; std::cin >> pair >> design; std::cout << countPairs(pair[0], pair[1], design) << "\n"; } return 0;}
Cmain.c · 59 行
#include <stdio.h>#include <ctype.h>#define MAX_LEN 100000#define MAX_DEPTH 3000/* 바깥 묶음 하나. 구슬이 아직 없으면 first와 last는 0 */typedef struct { long long count; char first, last; long long times;} Frame;static char design[MAX_LEN + 2];static Frame stack[MAX_DEPTH];/* 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수 */static long long count_pairs(char x, char y, const char *s) { int top = 0; long long count = 0, times = 0; char first = 0, last = 0; for (int i = 0; s[i] != '\0'; i++) { char ch = s[i]; if (isdigit((unsigned char)ch)) { times = times * 10 + (ch - '0'); } else if (ch == '(') { stack[top++] = (Frame){count, first, last, times}; count = 0; first = 0; last = 0; times = 0; } else if (ch == ')') { long long in_count = count; char in_first = first, in_last = last; Frame outer = stack[--top]; count = outer.count; first = outer.first; last = outer.last; long long k = outer.times; long long total = in_count * k; /* int로는 넘친다 */ if (in_last == x && in_first == y) total += k - 1; /* 되풀이 사이의 이음매 k - 1곳 */ if (last == x && in_first == y) total += 1; /* 묶음 앞 구슬과 묶음의 첫 구슬 사이 */ count += total; if (first == 0) first = in_first; last = in_last; } else { if (last == x && ch == y) count += 1; if (first == 0) first = ch; last = ch; } } return count;}int main(void) { int t; char pair[4]; if (scanf("%d", &t) != 1) return 1; for (int i = 0; i < t; i++) { if (scanf("%3s %100000s", pair, design) != 2) return 1; printf("%lld\n", count_pairs(pair[0], pair[1], design)); } return 0;}
Craykonmain.cray · 81 行
// 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수자리세기(x, y, 도안){ // 바깥 묶음들을 쌓아 두는 스택. 묶음마다 자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수 쌓은수 = []; 쌓은첫 = []; 쌓은끝 = []; 쌓은횟수 = []; 수 = 0; // 지금 읽고 있는 묶음. 구슬이 아직 없으면 첫과 끝은 "" 첫 = ""; 끝 = ""; 횟수 = 0; それぞれ (ch の中 도안) { もし (ch >= "0" && ch <= "9") { 횟수 = 횟수 * 10 + ch.数に(); } でなければ もし (ch == "(") { 쌓은수.追加(수); 쌓은첫.追加(첫); 쌓은끝.追加(끝); 쌓은횟수.追加(횟수); 수 = 0; 첫 = ""; 끝 = ""; 횟수 = 0; } でなければ もし (ch == ")") { 안수 = 수; 안첫 = 첫; 안끝 = 끝; 위 = 쌓은수.個数 - 1; // 스택의 맨 위에서 바깥 묶음을 꺼낸다 수 = 쌓은수[위]; 첫 = 쌓은첫[위]; 끝 = 쌓은끝[위]; k = 쌓은횟수[위]; 쌓은수.位置で取り除く(위); 쌓은첫.位置で取り除く(위); 쌓은끝.位置で取り除く(위); 쌓은횟수.位置で取り除く(위); 모두 = 안수 * k; もし (안끝 == x && 안첫 == y) { 모두 += k - 1; } もし (끝 == x && 안첫 == y) { 모두 += 1; } 수 += 모두; もし (첫 == "") { 첫 = 안첫; } 끝 = 안끝; } でなければ { もし (끝 == x && ch == y) { 수 += 1; } もし (첫 == "") { 첫 = ch; } 끝 = ch; } } 返す 수;}t = コンソール.行読み().数に();繰り返す (i = 0; i < t; i++){ parts = コンソール.行読み().空白除去().分ける(" "); コンソール.書く(자리세기(parts[0][0], parts[0][1], parts[1]));}