マークル木でデータを検証しよう
(paizaランク A 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
ハッシュ関数は様々なデータの要約・検証に使うことができます。そのうちのひとつがマークル木（マークルツリー）です。マークル木とは、ノードにハッシュ値をもつ二分木で、それぞれ親ノードには子ノードのハッシュ値を結合したものを入力として得られるハッシュ値が割り当てられています。特に、木構造の根の部分のハッシュ値をルートハッシュと呼びます。以下の例を参考にしてください。
本問では、マークル木におけるデータの検証をおこなってみましょう。
整数 N とルートハッシュ h が与えられます。その後、木構造の位置を表す b_i (1 ≦ i ≦ N) とその位置 b_i のハッシュ値 hb_i が与えられます。最後に、 b_{N+1} とその位置のデータ d が与えられます。データ d はハッシュ値ではないことに注意してください。以下のハッシュ関数 H を用いて、データ d とハッシュ値 hb_i から得られるルートハッシュ h' を求め、h' が初めに与えられたルートハッシュ h と一致するならば Yes、そうでないならば No と出力してください。なお、親ノードのハッシュ値 hb を計算する際は、上の画像のように、隣同士の子ノードのハッシュ値 hb0 と hb1 を順番に文字列として結合させて得た新たな文字列を入力として計算してください。
文字列 s の長さを m として、
H(s) = (s の 1 文字目の文字コード * B1 + s の 2 文字目の文字コード * B2 + ... + s の m 文字目の文字コード * Bm) % mod
ただし、B = 108+7, mod = 109+7 とし、文字コードは ASCII に従って変換してください。
位置 b_i については上の画像を参考にしてください。例えば、01 の子を表すノードは、010 と 011 というように表されます。
このようにマークル木を使うと、元のデータを一つ一つチェックすることなく、少ない情報で元のデータが全て正しいかどうかを検証することができます。
- 入力される値
-
N
h
b_1 hb_1
b_2 hb_2
...
b_N hb_N
b_{N+1} d- 1 行目に、初めに与えられるハッシュ値の数を表す整数 N が与えられます。
- 2 行目に、ルートハッシュを表す整数 h が与えられます。
- i + 2 行目に、木構造の位置を表す文字列 b_i と その位置のハッシュ値を表す整数 hb_i が与えられます。(1 ≦ i ≦ N)
- N + 3 行目に、木構造の位置を表す文字列 b_{N+1} と初期データを表す文字列 d が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
h' が h と一致するならば
Yes、そうでないならばNoと一行で出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
- 0 ≦ N ≦ 10
- 0 ≦ h ≦ 1,000,000,006
- b_i は 0 と 1 で構成される文字列 (1 ≦ i ≦ N+1)
- b_i の長さ = i (1 ≦ i ≦ N)
- b_{N+1} の長さ = N
- 0 ≦ hb_i ≦ 1,000,000,006 (1 ≦ i ≦ N)
- d は半角英数字で構成される長さ 1 以上 10 以下の文字列
与えられた入力からルートハッシュ h' を求められることが保証されています。
- 入力例1
-
2
796394619
1 724134430
01 988302243
00 apple
- 出力例1
-
Yes
- 入力例2
-
2
111111111
0 541278416
11 459428080
10 chocolate
- 出力例2
-
No
- 入力例3
-
10
143632914
0 723005018
11 419474906
100 539509504
1010 831802410
10110 77116613
101111 854499537
1011100 17807669
10111011 309861176
101110101 504344288
1011101000 238555247
1011101001 paiza
- 出力例3
-
Yes
