Time Limit: 3 sec / Memory Limit: 256 MiB
配点 : 100 点
問題文
JOI 市では公共交通機関が発達している.特に,バス専用道路が碁盤目状に敷き詰められているので,バスは交通状況の影響を受けることなく,一定の速度で運行することができる.南北方向のバス専用道路は 1km 間隔で W 本あり,東西方向のバス専用道路は 1km 間隔で H 本ある.すべてのバスは,長方形の形をした経路上を時計回りに 1 分あたり 1km の速度走る.また,バス専用道路が交わる点にバス停が設置されている.
JOI 君は今日,クリケットの試合を観戦しに行く予定であったが,寝坊してしまった.もう試合開始には間に合わないかもしれないが,JOI 君はできるだけ長い間試合を観戦していたいので,できるだけ早く試合会場に到着したい.
課題
JOI 君は,バスの運行情報を事前に調べていたので,バスの現在地と,それぞれのバスの運行経路はわかっている.今すぐ出発して,バスを乗り継いでいったとき,会場に到着するまでにかかる最短時間を求めるプログラムを書け.ただし,移動はバスを使ってのみ行うものとし,バスからバスへの乗り継ぎには時間がかかるので,バスを降りた瞬間に同じ交差点にいるバスに即座に乗り換えることはできず,降りてから 1 分後以降に到着したバスに乗ることのみできるとする.また,JOI 君がバスのみをつかって会場までたどり着けることは保証されている.
入力
標準入力から以下の入力を読み込め.
- 1 行目には 6 つの整数 W, H, S_{X}, S_{Y}, G_{X}, G_{Y} (1 \leqq S_{X} \leqq W かつ 1 \leqq S_{Y} \leqq H かつ 1 \leqq G_{X} \leqq W かつ 1 \leqq G_{Y} \leqq H) がこの順に空白で区切られて書かれている.これは,南北方向のバス専用道路が W 本通っており,それに直交する東西方向のバス専用道路が H 本通っていることを意味する.また,JOI 君ははじめ,西から S_{X} 番目のバス専用道路と,北から S_{Y} 番目のバス専用道路の交差する場所に居て,JOI 君の目的地である試合会場は,西から G_{X} 番目のバス専用道路と,北から G_{Y} 番目のバス専用道路の交差する場所にある.JOI 君の初期位置は,JOI 君の目的地とは異なる.また,JOI 君が出発した瞬間には,JOI 君の初期位置にバスがあることはない.
- 2 行目には JOI 市で運行されているバスの本数を表す 1 つの整数 N が書かれている.
- 続く N 行には,バスの情報が書かれている.N 行のうちの i 行目には,5 つの整数 X_{1i}, Y_{1i}, X_{2i}, Y_{2i}, T_{i} (1 \leqq X_{1i} < X_{2i} \leqq W かつ 1 \leqq Y_{1i} \leqq Y_{2i} \leqq H かつ 0 \leqq T < 2 \times (X_{2i} - X_{1i} + Y_{2i} - Y_{1i})) が書かれている.これは,i 番目のバスの経路の北西端は,西から X_{1i} 番目のバス専用道路と,北から Y_{1i} 番目のバス専用道路の交差するところであり,i 番目のバスの経路の南東端は,西から X_{2i} 番目のバス専用道路と,北から Y_{2i} 番目のバス専用道路の交差するところであることを表している.また,JOI 君が出発した時点で,i 番目のバスは,その経路上を北西端から時計回りに T_{i} km だけ進んだ位置にいる.
出力
JOI 君が出発してから,試合会場に到着するまでにかかる時間の最小値を 1 行で出力せよ.
制約
すべての入力データは以下の条件を満たす.
- 2 \leqq W \leqq 1\,000.
- 2 \leqq H \leqq 1\,000.
- 1 \leqq N \leqq 1\,000.
小課題
小課題 1 [30 点]
以下の条件を満たす.
- W \leqq 30.
- H \leqq 30.
- N \leqq 30.
小課題 2 [50 点]
以下の条件を満たす.
- W \leqq 300.
- H \leqq 300.
- N \leqq 300.
小課題 3 [20 点]
追加の制限はない.
入出力例
入力例 1
10 10 1 3 10 1 3 1 3 5 6 4 5 5 7 10 1 7 1 10 5 9
出力例 1
50

上の図はこの入力例において JOI 市を上空から見た図である.丸印は,バスの現在地を表している.矢印が,そのバスの経路を表している.JOI 君の現在地は三角形で示されており,目的地である試合会場は四角形で示されている.
JOI 君は,1 番のバスが来るまで待たなければいけない.10 分後に 1 番のバスに乗り込んだとすると,11 分後の状態は次のようになる.

続いて,JOI 君は 1 番のバスから 2 番のバスへ乗り換える必要がある.出発から 16 分後に JOI 君がバスを下車したとすると,19 分後の状態は次のようになる.

2 番のバスに乗ったあと,3 番のバスに乗り換える.出発から 29 分後,JOI 君が 2 番のバスを下車したとすると,そのとき,同じ交差点に 3 番のバスが停車している.しかし,乗り換えには 1 分の時間を要するので,このバスに乗ることはできない.
出発から 43 分後,JOI 君が 3 番のバスに乗ったとすると,試合会場に到着する直前の 49 分後の様子は次のようになる.

この 1 分後,JOI 君は試合会場に到着する.これよりも早く到着することはできないので,プログラムは 50 を出力する.
入力例 2
4 3 2 1 4 3 3 1 1 4 2 0 1 1 2 2 3 2 2 4 3 3
出力例 2
6
Source Name
JOI 2012/2013 春季トレーニング合宿 Contest Day1Time Limit: 5 sec / Memory Limit: 256 MiB
配点 : 100 点
問題文
JOI 君は画像をたくさん集めることが大好きで,多くの画像を持っている.最近になって JOI 君は,画像を集めすぎてしまったせいでハードディスクの容量が不足気味になっていることに気がついた.新しくハードディスクを購入するお金はないが,JOI 君にとって持っている画像を削除することはこの上ない苦痛であるため,画像をうまく圧縮して容量を削減することにした.
画像は縦 2^{N} 行,横 2^{N} 列の正方形状に並んだ合計 2^{N} \times 2^{N} 個の画素で表される.それぞれの画素は白か黒のいずれかである.
このような画像を JOI 君は次の方法で圧縮することにした.
- 画像内の画素がすべて同じ色ならば,その色だけを記録する.このとき圧縮後のデータの大きさは 1 である.
- そうでなければ,画像を 4 つのより小さな画像に分ける.画像が縦 2^{k} 行,横 2^{k} 列であるとすると,縦と横それぞれ中心で画像を分割し,縦 2^{k - 1} 行,横 2^{k - 1} 列の画像 4 つを得る.これら 4 つの小さくなった画像を同じ方法で圧縮する.このとき圧縮後のデータの大きさは,4 つの小さい画像の圧縮後のデータの大きさの和に,さらに 1 を加えたものであるとする.
JOI 君はこの方法で本当に画像が圧縮できるのか不安になったため,さまざまな画像に対して実験をしてみることにした.実験の方法は次のようなものである.
- まずすべての画素が白であるような画像を用意する.
- i = 1, \cdot \cdot \cdot , Q について,「T_{i} = 0 ならば上から数えて X_{i} 行目の 2^{N} 個の画素,T_{i} = 1 ならば左から数えて X_{i} 列目の 2^{N} 個の画素の,白黒をそれぞれ反転させる」という操作を行う.すなわち,上から a 行目で左から b 列目にあるカードを (a, b) と書いたとき,各 i について,T_{i} = 0 ならば 1 \leqq b \leqq 2^{N} をみたす画素 (X_{i}, b) に,T_{i} = 1 ならば 1 \leqq a \leqq 2^{N} をみたす画素 (a, X_{i}) に対し,画素が白ならば黒に,黒ならば白に変える操作を行う.
- 各 i について,i 回目の操作が終わったあとの画像を JOI 君の方法で圧縮したときの,圧縮後のデータの大きさを調べる.
実験では操作をできるだけ多く行うために,圧縮後のデータの大きさを高速に調べる必要がある.
課題
画像の大きさを表す整数 N,操作の回数 Q および Q 回の操作の指示が与えられたとき,それぞれの操作が終わった後の画像を JOI 君の方法で圧縮したときの,圧縮後のデータの大きさを求めるプログラムを作成せよ.
入力
標準入力から以下の入力を読み込め.
- 1 行目には 2 つの整数 N, Q が空白を区切りとして書かれており,画像が 2^{N} 行 2^{N} 列の大きさであることと,操作を行う回数が Q 回であることを表す.
- 続く Q 行には操作の指示が書かれている.Q 行のうちの i 行目 (1 \leqq i \leqq Q) には 2 つの整数 T_{i}, X_{i} (0 \leqq T_{i} \leqq 1 かつ 1 \leqq X_{i} \leqq 2^{N}) が空白を区切りとして書かれており,i 回目の操作は T_{i} = 0 なら上から X_{i} 行目,T_{i} = 1 なら左から X_{i} 列目の画素の白黒を全て反転することを表す.
出力
標準出力に Q 行出力せよ.i 行目 (1 \leqq i \leqq Q) には,i 回目の操作が終わった後の画像を JOI 君の方法で圧縮したときの,圧縮後のデータの大きさを表す 1 つの整数を出力せよ.
制約
すべての入力データは以下の条件を満たす.
- 1 \leqq N \leqq 20.
- 1 \leqq Q \leqq 2\,000\,000.
小課題
小課題 1 [10 点]
以下の条件を満たす.
- N \leqq 6.
- Q \leqq 128.
小課題 2 [20 点]
以下の条件を満たす.
- N \leqq 10.
- Q \leqq 2\,048.
小課題 3 [70 点]
- 追加の制限はない.
入出力例
入力例 1
2 3 0 1 1 2 0 3
出力例 1
13 17 21
この例では,Q = 3 回の操作は以下のように行われる.
初期状態
| □ | □ | □ | □ |
| □ | □ | □ | □ |
| □ | □ | □ | □ |
| □ | □ | □ | □ |
↓
| ■ | ■ | ■ | ■ |
| □ | □ | □ | □ |
| □ | □ | □ | □ |
| □ | □ | □ | □ |
↓
| ■ | □ | ■ | ■ |
| □ | ■ | □ | □ |
| □ | ■ | □ | □ |
| □ | ■ | □ | □ |
↓
| ■ | □ | ■ | ■ |
| □ | ■ | □ | □ |
| ■ | □ | ■ | ■ |
| □ | ■ | □ | □ |
Source Name
JOI 2012/2013 春季トレーニング合宿 Contest Day1Time Limit: 2 sec / Memory Limit: 256 MiB
配点 : 100 点
問題文
JOI 国は平面上に存在する.N 個の村があり,村には 1 から N までの番号がついている.村 i は座標 (i, 0) に存在する点とみなす.現在,JOI 国では村を接続する通信回線を整備しようとしている.障害に備え,通信回線は二系統整備される予定である.これらを系統 1 と系統 2 と呼ぶ.
系統 k には,ハブが M_{k} 個存在し,回線が N + M_{k} - 1 本ある.系統 k のハブには 1 から M_{k} までの番号がついており,ハブ j は座標 (X_{k j}, Y_{k j}) に存在する点とみなす.系統 k の各回線は,村と系統 k のハブ,または系統 k のハブ同士を接続する.各回線は,両端を結ぶ線分とみなす.任意の 2 つの回線は端点同士以外で共有点を持たないようになっていることが保証されている.系統 1 のハブ j の y 座標 Y_{1j} は 0 より大きい.また,系統 2 のハブ j の y 座標 Y_{2j} は 0 より小さい.
ある 2 つの地点が通信できるとは,それらの地点が回線により間接的に接続されていることとする.すなわち,回線に沿った移動を繰り返して,片方の地点からもう片方の地点へ移動できるならば,その 2 つの地点は通信ができる.系統 1 の回線のみを考えても,系統 2 の回線のみを考えても,任意の 2 つの村及びハブは通信可能である.
下図は通信回線の例である.灰色の円は系統 1 のハブ,黒い円は系統 2 のハブ,白い円は村を表す.

図 1: 通信回線の例 1
図 2: 通信回線の例 2
計画を検討するにあたって,外部からの攻撃で,どの程度攻撃を受けても通信が可能であるかを調べたい.外部からの攻撃は,2 つの数 A, B (A \geqq 0,B \leqq 0) により表現され,y 座標が A より大きい全てのハブと y 座標が B より小さい全てのハブを破壊するものと想定している.ハブが破壊されると,そこを経由した通信は行えなくなる.
課題
村や各系統の情報が与えられる.また,Q 個のクエリが与えられる.各クエリ q は 1 つの整数 A_{q} で表され,y 座標が A_{q} より大きい全てのハブが破壊される場合を意味する.各クエリに対し,加えて y 座標がいくつ未満のハブまでであれば破壊されても全村間の通信が可能であるかを答えよ.すなわち,整数 B_{q} であって,y 座標が A_{q} より大きい全てのハブと y 座標が B_{q} より小さい全てのハブを破壊しても全村間の通信が可能であるような最大の B_{q} (B_{q} \leqq 0) を答えよ.
入力
標準入力から以下の入力を読み込め.
- 1 行目には 4 つの整数 N, M_{1}, M_{2}, Q が空白を区切りとして書かれている.
-
続く M_{1} + (N + M_{1} - 1) 行には,系統 1 の情報が書かれている.
- 最初の M_{1} 行の i 行目 (1 \leqq i \leqq M_{1}) には,2 つの整数 X_{1i}, Y_{1i} が書かれている.
-
続く N + M_{1} - 1 行の i 行目 (1 \leqq i \leqq N + M_{1} - 1) には,回線 i の情報を表す 3 つの整数 T_{1i},C_{1i}, D_{1i} が書かれている (T_{1i} = 1, 2).
- T_{1i} が 1 のとき,回線 i は村 C_{1i} とハブ D_{1i} を接続する (1 \leqq C_{1i} \leqq N かつ 1 \leqq D_{1i} \leqq M_{1}).
- T_{1i} が 2 のとき,回線 i はハブ C_{1i} とハブ D_{1i} を接続する (1 \leqq C_{1i}, D_{1i} \leqq M_{1} かつ C_{1i} \ne D_{1i}).
-
続く M_{2} + (N + M_{2} - 1) 行には,系統 2 の情報が書かれている.
- 最初の M_{2} 行の i 行目 (1 \leqq i \leqq M_{2}) には,2 つの整数 X_{2i}, Y_{2i} が書かれている.
-
続く N + M_{2} - 1 行の i 行目 (1 \leqq i \leqq N + M_{2} - 1) には,回線 i の情報を表す 3 つの整数 T_{2i},C_{2i}, D_{2i} が書かれている (T_{2i} = 1, 2).
- T_{2i} が 1 のとき,回線 i は村 C_{2i} とハブ D_{2i} を接続する (1 \leqq C_{2i} \leqq N かつ 1 \leqq D_{2i} \leqq M_{2}).
- T_{2i} が 2 のとき,回線 i はハブ C_{2i} とハブ D_{2i} を接続する (1 \leqq C_{2i}, D_{2i} \leqq M_{2} かつ C_{2i} \ne D_{2i}).
-
続く Q 行の i 行目 (1 \leqq i \leqq Q) には 1 つの整数 A_{i} が書かれている.
出力
標準出力に Q 行出力せよ.i 行目 (1 \leqq i \leqq Q) には,クエリ i への答えを表す整数 B_{i} を出力せよ.
答えが 0 の場合,-0 と出力してはならない.
制約
すべての入力データは以下の条件を満たす.
- 1 \leqq N, M_{1}, M_{2} \leqq 100\,000.
- -1\,000\,000\,000 \leqq X_{1i} \leqq 1\,000\,000\,000 (1 \leqq i \leqq M_{1}).
- -1\,000\,000\,000 \leqq X_{2i} \leqq 1\,000\,000\,000 (1 \leqq i \leqq M_{2}).
- 1 \leqq Y_{1i} \leqq 1\,000\,000\,000 (1 \leqq i \leqq M_{1}).
- -1\,000\,000\,000 \leqq Y_{2i} \leqq -1 (1 \leqq i \leqq M_{2}).
- X_{1i} \ne X_{1j} または Y_{1i} \ne Y_{1j} (1 \leqq i, j \leqq M_{1} かつ i \ne j).
- X_{2i} \ne X_{2j} または Y_{2i} \ne Y_{2j} (1 \leqq i, j \leqq M_{2} かつ i \ne j).
- 1 \leqq Q \leqq 100\,000.
- 0 \leqq A_{i} \leqq 1\,000\,000\,000 (1 \leqq i \leqq Q).
- 任意の 2 つの回線は端点同士以外で共有点を持たない.
- 系統 1 の回線のみを考えても,系統 2 の回線のみを考えても,任意の 2 つの村及びハブは通信可能である.
小課題
小課題 1 [20 点]
以下の条件を満たす.
- N, M_{1}, M_{2} \leqq 1\,000.
- Q \leqq 1\,000.
小課題 2 [80 点]
追加の制限はない.
入出力例
入力例 1
4 3 3 1 1 1 3 2 2 3 1 1 1 1 2 1 1 3 2 1 4 2 2 1 3 2 2 3 3 -1 2 -2 1 -3 1 1 3 1 2 2 1 3 1 1 4 1 2 1 2 2 2 3 2
出力例 1
-2
この入力例は,問題文中の例 1 に対応している.
入力例 2
6 4 5 4 2 1 4 1 3 3 5 2 1 1 1 1 2 1 1 3 2 1 4 2 2 2 4 1 5 4 1 6 4 2 1 3 2 4 3 3 -3 5 -1 2 -2 2 -1 4 -2 1 2 4 1 3 4 1 1 4 2 1 3 1 5 2 1 6 2 1 4 5 2 2 5 1 3 1 2 5 1 3 1 2 0
出力例 2
0 -2 -1 -3
この入力例は,問題文中の例 2 に対応している.
Source Name
JOI 2012/2013 春季トレーニング合宿 Contest Day1Time Limit: 1 sec / Memory Limit: 256 MiB
配点 : 100 点
問題文
K 理事長は国際情報オリンピック日本選手団を応援するポスターを 3 枚デザインしている.ポスターにはそれぞれ J,O,I の文字を 1 文字ずつ盛り込む予定である.早速文字 J と文字 I のポスターを完成させた K 理事長は,残る文字 O のポスターをオーストラリアの星空を背景にデザインしようと考えた.
ポスターは幅 W,高さ H の長方形で,左下隅の座標が (0, 0),右上隅の座標が (W, H) である.ポスター上には N 個の星が印刷されている.i 番目の星 S_{i} (1 \leqq i \leqq N) のポスター上での座標は (X_{i}, Y_{i}) であり,どの 2 つの星も同じ座標にない.
K 理事長は文字 O のデザインを作成するにあたり,以下のように考えた.N 個の星のうち,異なる 4 つの星を選びそれぞれ A, B,C, D とする.A を中心とし B を通る円を円 O_{1},C を中心とし D を通る円を円 O_{2} とする.2 つの円 O_{1}, O_{2} が以下の両方の条件を満たすとき,4 つの星 A, B,C, D は K 理事長のデザインの候補となる.
- 円 O_{1} が円 O_{2} を内部に含む.すなわち,円 O_{2} の内部または円周上の任意の点が円 O_{1} の内部 (円周上は除く) にある.
- どちらの円もポスターの長方形領域からはみ出さない.すなわち,円の内部または円周上の任意の点 (X, Y) について,0 \leqq X \leqq W かつ 0 \leqq Y \leqq H を満たす.
K 理事長のデザインの候補となるような 4 つの星 A, B,C, D の選び方は何通りあるだろうか.
課題
ポスターの大きさと星の情報が与えられたとき,K 理事長のデザインの候補となるような 4 つの星 A, B,C, D の選び方が何通り存在するかを求めるプログラムを作成せよ.
入力
標準入力から以下の入力を読み込め.
- 1 行目には整数 N, W, H が空白を区切りとして書かれており,ポスター上に印刷された星の数と,ポスターの幅と高さをそれぞれ表す.
- 続く N 行のうちの i 行目 (1 \leqq i \leqq N) には 2 つの整数 X_{i}, Y_{i} (0 \leqq X_{i} \leqq W かつ 0 \leqq Y_{i} \leqq H) が空白を区切りとして書かれており,星 S_{i} のポスター上での座標を表す.
出力
標準出力に,K 理事長のデザインの候補となるような 4 つの星 A, B,C, D の選び方が何通り存在するかを表す整数を 1 行で出力せよ.
制約
すべての入力データは以下の条件を満たす.
- 4 \leqq N \leqq 50.
- 1 \leqq W \leqq 1\,000.
- 1 \leqq H \leqq 1\,000.
- 0 \leqq X_{i} \leqq W.
- 0 \leqq Y_{i} \leqq H.
- どの 2 つの星も同じ座標にない.
小課題
小課題 1 [80 点]
- 4 つの星 A, B,C, D をどのように選んでも,円 O_{1} と円 O_{2} は接しない.
小課題 2 [20 点]
追加の制限はない.
入出力例
入力例 1
7 20 15 9 5 13 9 15 13 7 4 6 8 14 7 16 7
出力例 1
3
この入力例は以下の図に対応している.星 S_{i} を点 i で表す.

この図において K 理事長のデザインの候補となるような 4 つの星 A, B,C, D の選び方は 3 通り存在する.
それぞれの場合における円 O_1, O_2 を以下の図で示す.


3 つ目の図において,円 O_{1} と円 O_{2} は接していないことに注意せよ.
入力例 2
15 20 30 11 8 14 25 3 20 1 27 2 16 12 8 0 4 3 10 12 11 5 9 16 3 2 13 4 24 18 3 12 28
出力例 2
12