Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
あなたは3Dゲームの当たり判定を実装しようとしています。
3 次元空間内の直方体であって、2 点 (a,b,c),(d,e,f) を結ぶ線分を対角線とし、全ての面が xy 平面、yz 平面、zx 平面のいずれかに平行なものを C(a,b,c,d,e,f) と表します。
(この定義により C(a,b,c,d,e,f) は一意に定まります)
2 つの直方体 C(a,b,c,d,e,f) と C(g,h,i,j,k,l) が与えられるので、これらの共通部分の体積が正かどうか判定してください。
制約
- 0 \leq a < d \leq 1000
- 0 \leq b < e \leq 1000
- 0 \leq c < f \leq 1000
- 0 \leq g < j \leq 1000
- 0 \leq h < k \leq 1000
- 0 \leq i < l \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
a b c d e f g h i j k l
出力
2 つの直方体の共通部分の体積が正なら Yes、そうでなければ No を出力せよ。
入力例 1
0 0 0 4 5 6 2 3 4 5 6 7
出力例 1
Yes
2 つの直方体の位置関係は下図のようになっており、共通部分の体積は 8 です。

入力例 2
0 0 0 2 2 2 0 0 2 2 2 4
出力例 2
No
2 つの直方体は面で接していますが、共通部分の体積は 0 です。
入力例 3
0 0 0 1000 1000 1000 10 10 10 100 100 100
出力例 3
Yes
Score : 250 points
Problem Statement
You are trying to implement collision detection in a 3D game.
In a 3-dimensional space, let C(a,b,c,d,e,f) denote the cuboid with a diagonal connecting (a,b,c) and (d,e,f), and with all faces parallel to the xy-plane, yz-plane, or zx-plane.
(This definition uniquely determines C(a,b,c,d,e,f).)
Given two cuboids C(a,b,c,d,e,f) and C(g,h,i,j,k,l), determine whether their intersection has a positive volume.
Constraints
- 0 \leq a < d \leq 1000
- 0 \leq b < e \leq 1000
- 0 \leq c < f \leq 1000
- 0 \leq g < j \leq 1000
- 0 \leq h < k \leq 1000
- 0 \leq i < l \leq 1000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
a b c d e f g h i j k l
Output
Print Yes if the intersection of the two cuboids has a positive volume, and No otherwise.
Sample Input 1
0 0 0 4 5 6 2 3 4 5 6 7
Sample Output 1
Yes
The positional relationship of the two cuboids is shown in the figure below, and their intersection has a volume of 8.

Sample Input 2
0 0 0 2 2 2 0 0 2 2 2 4
Sample Output 2
No
The two cuboids touch at a face, where the volume of the intersection is 0.
Sample Input 3
0 0 0 1000 1000 1000 10 10 10 100 100 100
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋君は RPG を作っています。高橋君は 2 枚の RPG 世界のマップが一致しているかを判定するプログラムを書くことにしました。
縦 H マス横 W マスの 2 つのグリッド A, B があります。グリッドの各マスには # と . のいずれかの文字が書かれています。
A と B の上から i 行目、左から j 列目に書かれている文字をそれぞれ A_{i, j}, B_{i, j} と呼びます。
次の 2 種類の操作をそれぞれ 縦方向のシフト, 横方向のシフト と呼びます。
- j=1, 2, \dots, W について次の操作を同時に行う。
- A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} を A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j} に同時に置き換える。
- i = 1, 2, \dots, H について次の操作を同時に行う。
- A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} を A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1} に同時に置き換える。
次の条件を満たす非負整数の組 (s, t) は存在しますか?存在する場合は Yes を、存在しない場合は No を出力してください。
- 縦方向のシフトを s 回行い、次に横方向のシフトを t 回行った時、操作後の A が B と一致する。
ここで、A と B が一致するとは、1 \leq i \leq H, 1 \leq j \leq W を満たす整数の組 (i, j) すべてに対して A_{i, j} = B_{i, j} が成り立つことを言います。
制約
- 2 \leq H, W \leq 30
- A_{i,j},B_{i,j} は
#または. - H, W は整数
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}
出力
条件を満たす整数の組 (s, t) が存在する場合は Yes を、存在しない場合は No を出力せよ。
入力例 1
4 3 ..# ... .#. ... #.. ... .#. ...
出力例 1
Yes
(s, t) = (2, 1) とすると A と B を一致させることができます。
(s, t) = (2, 1) の時の操作の手順を説明します。はじめ、A は次の通りです。
..# ... .#. ...
まず、縦方向のシフトを行います。A は次のようになります。
... .#. ... ..#
次に、再び縦方向のシフトを行います。A は次のようになります。
.#. ... ..# ...
最後に、横方向のシフトを行います。A は次のようになり、これは B と一致しています。
#.. ... .#. ...
入力例 2
3 2 ## ## #. .. #. #.
出力例 2
No
どのように (s, t) を選んでも A と B を一致させることはできません。
入力例 3
4 5 ##### .#... .##.. ..##. ...## #...# ##### ...#.
出力例 3
Yes
入力例 4
10 30 ..........##########.......... ..........####....###.....##.. .....##....##......##...#####. ....####...##..#####...##...## ...##..##..##......##..##....# #.##....##....##...##..##..... ..##....##.##..#####...##...## ..###..###..............##.##. .#..####..#..............###.. #..........##................. ................#..........##. ######....................#### ....###.....##............#### .....##...#####......##....##. .#####...##...##....####...##. .....##..##....#...##..##..##. ##...##..##.....#.##....##.... .#####...##...##..##....##.##. ..........##.##...###..###.... ...........###...#..####..#...
出力例 4
Yes
Score : 200 points
Problem Statement
Takahashi is developing an RPG. He has decided to write a code that checks whether two maps are equal.
We have grids A and B with H horizontal rows and W vertical columns. Each cell in the grid has a symbol # or . written on it.
The symbols written on the cell at the i-th row from the top and j-th column from the left in A and B are denoted by A_{i, j} and B_{i, j}, respectively.
The following two operations are called a vertical shift and horizontal shift.
- For each j=1, 2, \dots, W, simultaneously do the following:
- simultaneously replace A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} with A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}.
- For each i = 1, 2, \dots, H, simultaneously do the following:
- simultaneously replace A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} with A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}.
Is there a pair of non-negative integers (s, t) that satisfies the following condition? Print Yes if there is, and No otherwise.
- After applying a vertical shift s times and a horizontal shift t times, A is equal to B.
Here, A is said to be equal to B if and only if A_{i, j} = B_{i, j} for all integer pairs (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W.
Constraints
- 2 \leq H, W \leq 30
- A_{i,j} is
#or., and so is B_{i,j}. - H and W are integers.
Input
The input is given from Standard Input in the following format:
H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}
Output
Print Yes if there is a conforming integer pair (s, t); print No otherwise.
Sample Input 1
4 3 ..# ... .#. ... #.. ... .#. ...
Sample Output 1
Yes
By choosing (s, t) = (2, 1), the resulting A is equal to B.
We describe the procedure when (s, t) = (2, 1) is chosen. Initially, A is as follows.
..# ... .#. ...
We first apply a vertical shift to make A as follows.
... .#. ... ..#
Then we apply another vertical shift to make A as follows.
.#. ... ..# ...
Finally, we apply a horizontal shift to make A as follows, which equals B.
#.. ... .#. ...
Sample Input 2
3 2 ## ## #. .. #. #.
Sample Output 2
No
No choice of (s, t) makes A equal B.
Sample Input 3
4 5 ##### .#... .##.. ..##. ...## #...# ##### ...#.
Sample Output 3
Yes
Sample Input 4
10 30 ..........##########.......... ..........####....###.....##.. .....##....##......##...#####. ....####...##..#####...##...## ...##..##..##......##..##....# #.##....##....##...##..##..... ..##....##.##..#####...##...## ..###..###..............##.##. .#..####..#..............###.. #..........##................. ................#..........##. ######....................#### ....###.....##............#### .....##...#####......##....##. .#####...##...##....####...##. .....##..##....#...##..##..##. ##...##..##.....#.##....##.... .#####...##...##..##....##.##. ..........##.##...###..###.... ...........###...#..####..#...
Sample Output 4
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
整数の多重集合 S があります。はじめ S は空です。
Q 個のクエリが与えられるので順に処理してください。 クエリは次の 3 種類のいずれかです。
-
1 x: S に x を 1 個追加する。 -
2 x c: S から x を \mathrm{min}(c, (S に含まれる x の個数 )) 個削除する。 -
3: (S の最大値 )- (S の最小値 ) を出力する。このクエリを処理するとき、 S が空でないことが保証される。
制約
- 1 \leq Q \leq 2\times 10^5
- 0 \leq x \leq 10^9
- 1 \leq c \leq Q
3のクエリを処理するとき、S は空でない。- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
i 番目のクエリを表す \mathrm{query}_i は以下の 3 種類のいずれかである。
1 x
2 x c
3
出力
3 のクエリに対する答えを順に改行区切りで出力せよ。
入力例 1
8 1 3 1 2 3 1 2 1 7 3 2 2 3 3
出力例 1
1 5 4
多重集合 S は以下のように変化します。
- 1 番目のクエリ : S に 3 を追加する。S は \lbrace3 \rbrace となる。
- 2 番目のクエリ : S に 2 を追加する。S は \lbrace2, 3\rbrace となる。
- 3 番目のクエリ : S = \lbrace 2, 3\rbrace の最大値は 3 、最小値は 2 なので、 3-2=1 を出力する。
- 4 番目のクエリ : S に 2 を追加する。S は \lbrace2,2,3 \rbrace となる。
- 5 番目のクエリ : S に 7 を追加する。S は \lbrace2, 2,3, 7\rbrace となる。
- 6 番目のクエリ : S = \lbrace2,2,3, 7\rbrace の最大値は 7 、最小値は 2 なので、 7-2=5 を出力する。
- 7 番目のクエリ : S に含まれる 2 の個数は 2 個なので、 \mathrm{min(2,3)} = 2 個の 2 を S から削除する。S は \lbrace3, 7\rbrace となる。
- 8 番目のクエリ : S = \lbrace3, 7\rbrace の最大値は 7 、最小値は 3 なので、 7-3=4 を出力する。
入力例 2
4 1 10000 1 1000 2 100 3 1 10
出力例 2
クエリ 3 が含まれない場合、何も出力してはいけません。
Score : 300 points
Problem Statement
We have a multiset of integers S, which is initially empty.
Given Q queries, process them in order. Each query is of one of the following types.
-
1 x: Insert an x into S. -
2 x c: Remove an x from S m times, where m = \mathrm{min}(c,( the number of x's contained in S)). -
3: Print ( maximum value of S)-( minimum value of S). It is guaranteed that S is not empty when this query is given.
Constraints
- 1 \leq Q \leq 2\times 10^5
- 0 \leq x \leq 10^9
- 1 \leq c \leq Q
- When a query of type
3is given, S is not empty. - All values in input are integers.
Input
Input is given from Standard Input in the following format:
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
\mathrm{query}_i, which denotes the i-th query, is in one of the following formats:
1 x
2 x c
3
Output
Print the answers for the queries of type 3 in the given order, separated by newlines.
Sample Input 1
8 1 3 1 2 3 1 2 1 7 3 2 2 3 3
Sample Output 1
1 5 4
The multiset S transitions as follows.
- 1-st query: insert 3 into S. S is now \lbrace 3 \rbrace.
- 2-nd query: insert 2 into S. S is now \lbrace 2, 3 \rbrace.
- 3-rd query: the maximum value of S = \lbrace 2, 3\rbrace is 3 and its minimum value is 2, so print 3-2=1.
- 4-th query: insert 2 into S. S is now \lbrace 2,2,3 \rbrace.
- 5-th query: insert 7 into S. S is now \lbrace 2, 2,3, 7\rbrace.
- 6-th query: the maximum value of S = \lbrace 2,2,3, 7\rbrace is 7 and its minimum value is 2, so print 7-2=5.
- 7-th query: since there are two 2's in S and \mathrm{min(2,3)} = 2, remove 2 from S twice. S is now \lbrace 3, 7\rbrace.
- 8-th query: the maximum value of S = \lbrace 3, 7\rbrace is 7 and its minimum value is 3, so print 7-3=4.
Sample Input 2
4 1 10000 1 1000 2 100 3 1 10
Sample Output 2
If the given queries do not contain that of type 3, nothing should be printed.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
AtCoder Land には 1 から N までの番号が付けられた N 個のポップコーン売り場があります。 売られているポップコーンの味には味 1,2,\dots,M の M 種類がありますが、すべての売り場ですべての味のポップコーンを売っているわけではありません。
高橋君は、それぞれのポップコーン売り場でどの味のポップコーンを売っているかの情報を入手しました。
この情報は N 個の長さ M の文字列 S_1,S_2,\dots,S_N によって表され、S_i の j 文字目が o であるとき売り場 i が味 j のポップコーンを売っていることを、
x であるとき売っていないことを示します。
どの売り場も最低 1 種類の味のポップコーンを売っており、どの味のポップコーンも最低 1 つの売り場で売られています。
高橋君は全種類のポップコーンを食べたがっていますが、あまり何度も移動はしたくありません。 高橋君がすべての味のポップコーンを購入するためには最低何個の売り場を訪れる必要があるか求めてください。
制約
- N,M は整数
- 1\leq N,M \leq 10
- S_i は
oおよびxからなる長さ M の文字列 - すべての i\ (1\leq i\leq N) について、S_i の中には
oが 1 つ以上存在する - すべての j\ (1\leq j\leq M) について、S_i の j 文字目が
oであるような i が 1 つ以上存在する
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N
出力
高橋君がすべての味のポップコーンを購入するために訪れる必要がある売り場の個数の最小値を出力せよ。
入力例 1
3 5 oooxx xooox xxooo
出力例 1
2
1 つめの売り場と 3 つめの売り場を訪れることで、すべての味のポップコーンを購入することができます。 1 つの売り場ですべての味のポップコーンを購入することはできないので、答えは 2 です。
入力例 2
3 2 oo ox xo
出力例 2
1
入力例 3
8 6 xxoxxo xxoxxx xoxxxx xxxoxx xxoooo xxxxox xoxxox oxoxxo
出力例 3
3
Score : 300 points
Problem Statement
In AtCoder Land, there are N popcorn stands numbered 1 to N. They have M different flavors of popcorn, labeled 1, 2, \dots, M, but not every stand sells all flavors of popcorn.
Takahashi has obtained information about which flavors of popcorn are sold at each stand. This information is represented by N strings S_1, S_2, \dots, S_N of length M. If the j-th character of S_i is o, it means that stand i sells flavor j of popcorn. If it is x, it means that stand i does not sell flavor j. Each stand sells at least one flavor of popcorn, and each flavor of popcorn is sold at least at one stand.
Takahashi wants to try all the flavors of popcorn but does not want to move around too much. Determine the minimum number of stands Takahashi needs to visit to buy all the flavors of popcorn.
Constraints
- N and M are integers.
- 1 \leq N, M \leq 10
- Each S_i is a string of length M consisting of
oandx. - For every i (1 \leq i \leq N), there is at least one
oin S_i. - For every j (1 \leq j \leq M), there is at least one i such that the j-th character of S_i is
o.
Input
The input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N
Output
Print the minimum number of stands Takahashi needs to visit to buy all the flavors of popcorn.
Sample Input 1
3 5 oooxx xooox xxooo
Sample Output 1
2
By visiting the 1st and 3rd stands, you can buy all the flavors of popcorn. It is impossible to buy all the flavors from a single stand, so the answer is 2.
Sample Input 2
3 2 oo ox xo
Sample Output 2
1
Sample Input 3
8 6 xxoxxo xxoxxx xoxxxx xxxoxx xxoooo xxxxox xoxxox oxoxxo
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
N 個の頂点と M 本の辺からなる単純な(すなわち、自己ループも多重辺も含まない)無向グラフ G が与えられます。 i = 1, 2, \ldots, M について、i 番目の辺は頂点 u_i と頂点 v_i を結びます。
1 \leq u \lt v \leq N を満たす整数の組 (u, v) であって、下記の 2 つの条件をともに満たすものの個数を出力してください。
- グラフ G において、頂点 u と頂点 v を結ぶ辺は存在しない。
- グラフ G に、頂点 u と頂点 v を結ぶ辺を追加して得られるグラフは、二部グラフである。
二部グラフとは?
無向グラフが二部グラフであるとは、下記の条件を満たすように各頂点を黒または白のどちらかの色で塗ることができることを言います。
- 同じ色に塗られた頂点どうしを結ぶ辺は存在しない。
制約
- 2 \leq N \leq 2 \times 10^5
- 0 \leq M \leq \min \lbrace 2 \times 10^5, N(N-1)/2 \rbrace
- 1 \leq u_i, v_i \leq N
- グラフ G は単純
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
答えを出力せよ。
入力例 1
5 4 4 2 3 1 5 2 3 2
出力例 1
2
問題文中の条件を満たす整数の組 (u, v) は、(1, 4) と (1, 5) の 2 つです。よって、2 を出力します。
他の組については、例えば、(1, 3) はグラフ G において頂点 1 と頂点 3 を結ぶ辺が存在することから、
(4, 5) はグラフ G に頂点 4 と頂点 5 を結ぶ辺を追加して得られるグラフが二部グラフではないことから、
それぞれ問題文中の条件を満たしません。
入力例 2
4 3 3 1 3 2 1 2
出力例 2
0
与えられるグラフが二部グラフであったり連結であるとは限らないことに注意してください。
入力例 3
9 11 4 9 9 1 8 2 8 3 9 2 8 4 6 7 4 6 7 5 4 5 7 8
出力例 3
9
Score : 400 points
Problem Statement
You are given a simple undirected graph G with N vertices and M edges (a simple graph does not contain self-loops or multi-edges). For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i.
Print the number of pairs of integers (u, v) that satisfy 1 \leq u \lt v \leq N and both of the following conditions.
- The graph G does not have an edge connecting vertex u and vertex v.
- Adding an edge connecting vertex u and vertex v in the graph G results in a bipartite graph.
What is a bipartite graph?
An undirected graph is said to be bipartite if and only if one can paint each vertex black or white to satisfy the following condition.
- No edge connects vertices painted in the same color.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 0 \leq M \leq \min \lbrace 2 \times 10^5, N(N-1)/2 \rbrace
- 1 \leq u_i, v_i \leq N
- The graph G is simple.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
Output
Print the answer.
Sample Input 1
5 4 4 2 3 1 5 2 3 2
Sample Output 1
2
We have two pairs of integers (u, v) that satisfy the conditions in the problem statement: (1, 4) and (1, 5). Thus, you should print 2.
The other pairs do not satisfy the conditions. For instance, for (1, 3), the graph G has an edge connecting vertex 1 and vertex 3; for (4, 5), adding an edge connecting vertex 4 and vertex 5 in the graph G does not result in a bipartite graph.
Sample Input 2
4 3 3 1 3 2 1 2
Sample Output 2
0
Note that the given graph may not be bipartite or connected.
Sample Input 3
9 11 4 9 9 1 8 2 8 3 9 2 8 4 6 7 4 6 7 5 4 5 7 8
Sample Output 3
9