既存投稿一覧ページへのリンク
Before
Next
雑記
解けそうな問題は積極的にWAを出して、どのようなテストケースのときにエラーが出るか検証する方針で進めて見ようかな。
AtCoderの問題は、勉強のやり方を試行錯誤していて、どの方式でやっても壁にぶつかってしまい、結局は一番最初にやって、面倒くさくてやめた勉強法が一番良いという結論に至りつつある・・・
C問題
入力例01
input
2 3 5
1 1 2
3 1 1
3 1 2
2 2
3 2 3
input_python
def io_func():
# 最初の1行目を取得し、n, m, qを整数として取得
n, m, q = map(int, input().split())
queries = []
# q回分の入力行をリストとして取得
for _ in range(q):
queries.append([int(x) for x in input().split()])
# 変数をまとめて返す
return n, m, q, queries
output
No
Yes
Yes
WA(ac->2, ac->25, wa -> 18)
時間の余裕ではなく、精神的な余裕があるときにWAとなるテストパターンを生成して検証してみることにしよう。
入力例はACしたものの、テストケースを出したらWA出現。
TLEはきついけど、WAはウェルカ～ム。
def io_func():
# 最初の1行目を取得し、n, m, qを整数として取得
n, m, q = map(int, input().split())
queries = []
# q回分の入力行をリストとして取得
for _ in range(q):
queries.append([int(x) for x in input().split()])
# 変数をまとめて返す
return n, m, q, queries
from sortedcontainers import SortedList
def solve(n, m, q, queries):
sl = [SortedList() for _ in range(m+1)]
for query in queries:
if query[0] == 2:
sl[m].add(query[1])
elif query[0] == 1:
sl[query[2]].add(query[1])
else:
if query[1] in sl[m]:
print("Yes")
elif query[1] in sl[query[2]]:
print("Yes")
else:
print("No")
if __name__=="__main__":
n, m, q, queries = io_func()
solve(n, m, q, queries)
D問題
解法 ver.250906
整数列Aを昇順に整列し、二分探索かな・・・
入力例01
長さ 5 の整数列
$A = (3, 1, 4, 1, 5)$
と、非負整数 D = 2 が与えられます。
この整数列 A の要素をいくつか削除して、以下の条件を満たす数列 B を作りたいです。
- すべての $1 \leq i < j \leq |B|$ について、 $|B_i - B_j| \neq 2$ である。
すなわち、作りたい数列 B の中では、どの 2 つの要素を比べても「差がちょうど 2」になるような組が存在してはいけません。
最小でいくつの要素を削除すればよいか求めてください。
input
5 2
3 1 4 1 5
input_python
def io_func():
# 標準入力からN, Dを整数として取得
n, d = map(int, input().split())
# 標準入力からリストAを整数リストとして取得
a = list(map(int, input().split()))
# 取得した値を戻り値として返す
return n, d, a
output
1
入力例03
長さ 10 の整数列
$A = (1, 6, 2, 10, 2, 3, 2, 10, 6, 4)$
と、非負整数 D = 3 が与えられます。
この整数列 A の要素をいくつか削除して、以下の条件を満たす数列 B を作りたいです。
- すべての $1 \leq i < j \leq |B|$ について、$|B_i - B_j| \neq 3$ である。
すなわち、作りたい数列 B の中では、どの 2 つの要素を比べても「差がちょうど 3」になるような組が存在してはいけません。
最小でいくつの要素を削除すればよいか求めてください。
input
10 3
1 6 2 10 2 3 2 10 6 4
output
2
E問題
入力例01
はじめ、文字列の多重集合 $X, Y$ はどちらも空です。
次の 4 個のクエリを順に処理してください。
-
クエリ: 「1 at」
- $T=1$ なので、文字列 "at" を多重集合 $X$ に追加する。
-
クエリ: 「2 watcoder」
- $T=2$ なので、文字列 "watcoder" を多重集合 $Y$ に追加する。
-
クエリ: 「2 atcoder」
- $T=2$ なので、文字列 "atcoder" を多重集合 $Y$ に追加する。
-
クエリ: 「1 wa」
- $T=1$ なので、文字列 "wa" を多重集合 $X$ に追加する。
各クエリの処理後に、次の値を出力してください：
- 多重集合 $Y$ に含まれる文字列のうち、
多重集合 $X$ のどの要素も接頭辞（prefix）として持たないものの個数。
-
クエリ後: X = "at", Y = {}
- $Y$ が空なので答えは 0
-
クエリ後: X = { "at" }, Y = { "watcoder" }
- "watcoder" の接頭辞は "w", "wa", "wat" ... などであり、$X$ の "at" は一致しない。
- よって答えは 1
-
クエリ後: X = { "at" }, Y = { "watcoder", "atcoder" }
- "watcoder": 接頭辞に "at" は含まれない → OK
- "atcoder": 接頭辞に "at" が含まれる → NG
- よって答えは 1
-
クエリ後: X = { "at", "wa" }, Y = { "watcoder", "atcoder" }
- "watcoder": 接頭辞 "wa" が $X$ にあるので NG
- "atcoder": 接頭辞 "at" が $X$ にあるので NG
- よって答えは 0
input
4
1 at
2 watcoder
2 atcoder
1 wa
input_python
def io_func():
# クエリ数を標準入力から取得
n = int(input())
# クエリ情報（タプルのリスト）の初期化
q = []
for _ in range(n):
# 1行分を取得して、分割（タイプと文字列）
ty, s = input().split()
# クエリとしてタプルで追加
q.append((ty, s))
# すべてのクエリを戻り値として返す
return q
output
0
1
1
0
WA(ac->2, ac->9, wa->3, tle->32, re->13) --- ver. 2025'09/09
正直、TLEするのは提出前にわかっていたけれど、waとかreとか出てくるのは想定外だった…
少し前までは、なんでACしねーんだよっ！って嘆いていたけれど、気持ちに余裕が出来た今、どういうケースでwaやreが起きるか発掘作業が楽しみになっているんだ。
tleは、まぁ当面放置しておこう。
今は効率の良いアルゴリズムより、効率が悪くてもACを取れるコードを思いつくようになることを優先にしたいんだ。
class TrieNode:
# Trie木の各ノードを表すクラス
def __init__(self):
# 子ノードを格納する辞書
self.children = {}
# このノードが単語の終端かどうかを記録
self.is_end = False
class Trie:
# Trie木全体を表すクラス
def __init__(self):
# 木構造の根ノードを初期化
self.root = TrieNode()
def insert(self, word):
# 単語wordをTrieに挿入するメソッド
node = self.root # 根ノードから始める
for char in word:
# 各文字について、子ノードがなければ新規作成
if char not in node.children:
node.children[char] = TrieNode()
# 子ノードに移動
node = node.children[char]
# 最後のノードを単語終端とする
node.is_end = True
def display(self, node=None, prefix=""):
# Trieに格納された全ての単語を列挙するメソッド
if node is None:
node = self.root # 初期は根ノード
result = []
# 単語の終端ならプレフィックスを結果に追加
if node.is_end:
result.append(prefix)
# 全ての子ノードを再帰的に探索
for char, child in node.children.items():
result.extend(self.display(child, prefix + char))
return result
def count_prefix(self, prefix):
# prefix（例: "ac"）までノードを辿る
node = self.root
for char in prefix:
if char not in node.children:
return 0 # 該当する接頭辞がない場合
node = node.children[char]
# 以降のノードに格納された単語終端数を数える
def dfs_count(n):
c = 1 if n.is_end else 0
for child in n.children.values():
c += dfs_count(child)
return c
return dfs_count(node)
def delete_prefix(self, prefix):
node = self.root
parent = None
char_to_delete = None
for char in prefix:
if char not in node.children:
return # そのprefixの単語がない場合は何もしない
parent = node
char_to_delete = char
node = node.children[char]
# prefix直前の親ノードから、prefix部の子ノードを削除
if parent and char_to_delete in parent.children:
del parent.children[char_to_delete]
def size(self):
def dfs(node):
count = 1 if node.is_end else 0
for child in node.children.values():
count += dfs(child)
return count
return dfs(self.root)
def io_func():
# クエリ数を標準入力から取得
n = int(input())
# クエリ情報（タプルのリスト）の初期化
q = []
for _ in range(n):
# 1行分を取得して、分割（タイプと文字列）
ty, s = input().split()
# クエリとしてタプルで追加
q.append((int(ty), s))
# すべてのクエリを戻り値として返す
return q
def solve(q):
trie = Trie()
stack_counter = 0
temp_ans = 0
chk_list = []
for v, query in q:
if v==1:
chk_list.append(query)
chk_list = list(set(chk_list))
for del_v in chk_list:
trie.delete_prefix(del_v)
ans = trie.size()
print(ans)
elif v==2:
trie.insert(query)
# v==1で追加したスタックの情報を削除する
for del_v in chk_list:
trie.delete_prefix(del_v)
ans = trie.size()
print(ans)
if __name__=="__main__":
q = io_func()
solve(q)
F問題
入力例01
以下は <expr> シンボルに従う有効な数式の例です。
-
1111+111: 1111 + 111 を表します。 -
(1+1)*(1+1): (1+1) × (1+1) を表します。 -
(11+(1+1)*(1+1))+1: (11+(1+1)×(1+1))+1 を表します。
一方、次の文字列は <expr> に従わないため不正です：
(1+1)(1+1)1+21-11/1)1(1++1+1(+1)1*+1
9になる文字列のうち長さが最小のものを出力してください。
input
9
input_python
def io_func():
n = int(input()) # 標準入力から整数Nを取得
return n # 整数Nを戻り値として返す
output
(1+1+1)*(1+1+1)