Time Limit: 2 sec / Memory Limit: 256 MB
問題文
この問題は、講座用問題です。ページ下部に解説が掲載されています。
高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。
高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。
入力
入力は以下の形式で標準入力から与えられる。
H W
c_{0,0} c_{0,1} c_{0,W-1}
c_{1,0} c_{1,1} c_{1,W-1}
:
c_{H-1,0} c_{H-1,1} c_{H-1,W-1}
- 1 行目には、街の南北の長さとして整数 H(1≦H≦500) と東西の長さとして整数 W(1≦W≦500) が空白で区切られて与えられる。
-
2 行目からの H 行には、格子状の街の各区画における状態 c_{i,j}(0≦i≦H-1, 0≦j≦W-1) が与えられる。
-
i 行目 j 文字目の文字 c_{i,j} はそれぞれ
s,g,.,#のいずれかで与えられ、座標 (j,i) が下記のような状態であることを表す。s: その区画が家であることを表す。g: その区画が魚屋であることを表す。.: その区画が道であることを表す。#: その区画が塀であることを表す。
- 高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
- 与えられた街の外を通ることはできない。
sとgはそれぞれ 1 つずつ与えられる。
-
i 行目 j 文字目の文字 c_{i,j} はそれぞれ
出力
塀を 1 回も壊さずに、家から魚屋まで辿り着くことができる場合は Yes、辿りつけない場合は No を標準出力に 1 行で出力せよ。
解説
入力例1
4 5 s#### ....# ##### #...g
出力例1
No
高橋君は、魚屋にたどり着くことができません。
入力例2
4 4 ...s .... .... .g..
出力例2
Yes
入力例3
10 10 s......... #########. #.......#. #..####.#. ##....#.#. #####.#.#. g.#.#.#.#. #.#.#.#.#. ###.#.#.#. #.....#...
出力例3
No
入力例4
10 10 s......... #########. #.......#. #..####.#. ##....#.#. #####.#.#. g.#.#.#.#. #.#.#.#.#. #.#.#.#.#. #.....#...
出力例4
Yes
入力例5
1 10 s..####..g
出力例5
No
Time Limit: 5 sec / Memory Limit: 256 MB
問題文
この問題は、講座用問題です。ページ下部に解説が掲載されています。
N 頂点の、単純とは限らない無向グラフを考えます。 初期状態では、頂点のみが存在し、辺は全く存在せず、全ての頂点が孤立しているとします。 以下の 2 種類のクエリが、Q 回与えられます。
- 連結クエリ： 頂点 A と、頂点 B を繋ぐ辺を追加します。
- 判定クエリ： 頂点 A と、頂点 B が、連結であるかどうか判定します。連結であれば
Yes、そうでなければNoを出力します。
クエリを順番に処理し、判定クエリへの回答を出力して下さい。 この際、同じ辺が何度も追加されることや、自分自身への辺が追加されることもある事に注意してください。
連結であるとは、頂点 A から頂点 B まで辺をたどって到達可能であることを意味します。 A と B が同じ頂点の場合、連結であると定義します。 グラフは無向であるため、連結クエリによって頂点 A, B 間の辺が追加されると、A から B へも B から A へも辿れるようになります。
入力
入力は以下の形式で標準入力から与えられる。
N Q P_1 A_1 B_1 P_2 A_2 B_2 : P_Q A_Q B_Q
- 1 行目には、頂点の個数を表す整数 N (1≦N≦100,000) と、クエリの個数を表す整数 Q (1 ≦ Q ≦ 200,000) が、スペース区切りで与えられる。
-
2 行目からの Q 行のうち i 行目には、i 番目のクエリの種類を表す整数 P_i (0 ≦ P_i ≦ 1) と、クエリの対象となる頂点の番号を表す整数 A_i, B_i (0 ≦ A_i, B_i ≦ N - 1) が、 スペース区切りで与えられる。
- P_i = 0 の時、そのクエリが連結クエリであることを表す。
- P_i = 1 の時、そのクエリが判定クエリであることを表す。
出力
各判定クエリに対し、出力をおこなって下さい。 毎回の出力の後に改行を行うこと。
解説
入力例1
8 9 0 1 2 0 3 2 1 1 3 1 1 4 0 2 4 1 4 1 0 4 2 0 0 0 1 0 0
出力例1
Yes No Yes Yes
以下のような手順で実行されます。
- 1 つ目のクエリで、頂点 1 と頂点 2 を繋ぎます。
- 2 つ目のクエリで、頂点 3 と頂点 2 を繋ぎます。
- 3 つ目のクエリで、頂点 1 と頂点 3 の連結判定を行います。連結しているので、
Yesと出力します。 - 4 つ目のクエリで、頂点 1 と頂点 4 の連結判定を行います。連結していないので、
Noと出力します。 - 5 つ目のクエリで、頂点 2 と頂点 4 を繋ぎます。
- 6 つ目のクエリで、頂点 4 と頂点 1 の連結判定を行います。連結しているで、
Yesと出力します。 - 7 つ目のクエリで、頂点 4 と頂点 2 を繋ぎます。これらは既に繋がれていますが、多重辺が出来ることもあります。
- 8 つ目のクエリで、頂点 0 と頂点 0 を繋ぎます。これらは同じ頂点ですが、自己ループが出来ることもあります。
- 9 つ目のクエリで、頂点 0 と頂点 0 の連結判定を行います。同じ頂点は常に連結していると見做せるので、
Yesと出力します。
Time Limit: 5 sec / Memory Limit: 256 MB
問題文
この問題は、講座用問題です。ページ下部に解説が掲載されています。
AtCoder 食堂では、定食のメニューを検討しています。
- 主菜は、価格が i 円のものが A_i 種類あります (1 ≦ i ≦ N)。
- 副菜は、価格が i 円のものが B_i 種類あります (1 ≦ i ≦ N)。
定食は、主菜と副菜を 1 種類ずつ選んで構成します。 定食の価格は、選んだ主菜と副菜の価格の和とします。
各 k (1 ≦ k ≦ 2N) について、価格が k 円になる定食の種類の数を計算して下さい。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 : A_N B_N
- 1 行目には、整数 N (1 ≦ N ≦ 100,000) が書かれている。
- 2 行目からの N 行の i 行目には、整数 A_i, B_i (0 ≦ A_i, B_i ≦ 100) が書かれている。
出力
2N 行の出力をせよ。k 行目に価格が k 円になる定食の種類数を整数で出力せよ。
解説
入力例1
4 1 1 2 2 3 4 4 8
出力例1
0 1 4 11 26 36 40 32
- 1 円になる組合せは存在しない。
- 2 円の組み合わせは、1 円の主菜と副菜が 1 種類ずつなので 1 通り。
- 3 円の組み合わせは、1×2 + 2×1 = 4 通り。