以下是来自日本的官方新闻原版PDF,已经完整保存和染色。



可复制的 PDF 提取文本
Japanese Olympiad In Informatics 2009/2010
Spring Training Camp
March 19 - 25, 2010, Komaba/Yoyogi, Tokyo
Contest day 3 - Hide-and-seek
かくれんぼ(Hide-and-seek)
あなたは,JOI 社が発売したテレビゲームソフトを手に入れた.なかなか良くできたゲームであり,そ
れなりに楽しみながら毎日プレイしていた.
ある日,ゲーマーの中で「かくれんぼ」と呼称されるステージが出現した.どうやらそのステージには
バグがあり,優れたゲーマーでさえもほんのわずかな確率でしかクリアできない物であるらしい.
何度もそのステージに挑戦する中であなたは,とても高速な判断を行うことでクリアできる可能性が有
ることに気づき,プログラムを作成して対処出来るのではないかと考えた.
かくれんぼステージは,多数の障害物が配置された場所が舞台となっている.舞台は長方形で1 × 1 の正
方形のマスに分かれており,各マスは1 ≦x ≦100, 000 ,1 ≦y ≦1, 000, 000, 000 を満たす整数x, y によっ
て(x, y) と表現される.(1, 1) は左上隅のマスであり,(x + 1, y + 1) は(1, 1) から右にx,下にy 進んだマス
を表現する.
各障害物はy 座標が同じ連続したw 個のマスに置かれる.つまり,障害物はw × 1 個のマスを占める長
方形の形に見える.その中のx 座標が一番小さいマスの座標(x, y) と,長さw の組で1 つの障害物が表現
されている.障害物は2 ≦y のマスに配置される.障害物同士が重なることはない.
ステージが始まるとプレーヤーは舞台を動き回る.プレーヤーは障害物のあるマスを含めた任意のマス
に移動できる.
一定の時間が経過すると敵が出現し攻撃を行う.プレーヤーはこの時必ず障害物の中に隠れる必要があ
る.障害物の中に隠れるには,障害物のあるマスに居ればよい.適切な障害物の中に隠れることでプレー
ヤーは攻撃を受けずに済み,敵に反撃するチャンスを得ることが出来る.チャンスを利用することでステー
ジがクリアできる.
敵はM 種類の武器(例えば,拳銃,ライフル,無反動砲,電磁投射砲などなど)を所持している.武器
には1 からM の固有の番号がつけられており,i 番の武器には攻撃力ai が設定されている.攻撃力は,そ
の数値の分だけ障害物を破壊出来ることを表している.
破壊された障害物の中にプレーヤーが隠れている場合,プレーヤーはダメージを受けることになる.
敵はランダムに選ばれたx を使い,(x, 1) に出現し,下方向に向かってランダムに選択した武器を使い攻
撃する予定だった.ところが,ゲームのバグによって,敵は必ずプレーヤーのいるx 座標を選択し,プレー
ヤーに向けて攻撃してしまう事となった.
あなたは自作のプログラムを使い,敵からどの武器を使って攻撃されても良いように,武器毎に攻撃を
受けずに済む最適な隠れ場所を探すことにした.攻撃を受けずに済む最適な隠れ場所は,プレーヤーが反
撃を行いやすいように,もっともy 座標が小さい所である.また,そのような場所が複数存在する場合に
は,その中でもっともx 座標が小さい所が最適である.
課題(TASK)
障害物の情報と各武器の攻撃力が与えられたとき,敵が所持する武器毎に最適な隠れ場所を求めるプロ
グラムを作成せよ.ただし,どのように隠れても攻撃を受けてしまう場合には,隠れる場所がないという
意味で(-1,-1) を出力せよ.
Page 1 of 3
Japanese Olympiad In Informatics 2009/2010
Spring Training Camp
March 19 - 25, 2010, Komaba/Yoyogi, Tokyo
Contest day 3 - Hide-and-seek
図1: 攻撃力が4 である武器に対応する隠れ方
制限(CONSTRAINTS)
1 ≦N ≦50, 000 障害物の数
1 ≦M ≦50, 000 武器の種類
1 ≦xi ≦100, 000 障害物i が配置されるマスの中でもっとも小さいx 座標
2 ≦yi ≦1, 000, 000, 000 障害物i のy 座標
1 ≦wi + xi −1 ≦100, 000 wi は障害物i の長さ
1 ≦a j ≦N 武器j の攻撃力
入力(INPUT)
標準入力から以下の入力を読み込め.
• 1 行目には整数N とM が空白を区切りとして書かれている.
• 続くN 行のうちi 行目には整数xi,yi,wi が空白を区切りとして書かれている.
• 続くM 行のうちj 行目には整数aj が書かれている.
出力(OUTPUT)
標準出力に以下のデータを出力せよ.
• データはM 行からなる.j 行目は2 つの整数x j とy j が空白区切りで書かれており,j 番目の武器に
対応する最適な隠れ場所の座標が(x j, yj) である事を表す.どのように隠れてもj 番目の武器の攻撃
を受けてしまう場合はx j = y j = −1 とせよ.
Page 2 of 3
Japanese Olympiad In Informatics 2009/2010
Spring Training Camp
March 19 - 25, 2010, Komaba/Yoyogi, Tokyo
Contest day 3 - Hide-and-seek
採点基準(GRADING)
30 点分のテストグループにおいて,xi + wi −1 ≦10, 000 かつN ≦1, 000 である.
入出力例(EXAMPLE)
入力例(Sample Input) 出力例(Sample Output)
13 2 15 10
2 2 10 -1 -1
14 3 9
15 6 12
3 7 5
16 8 9
15 10 3
4 13 10
11 11 11
5 4 11
11 14 12
6 9 7
20 4 8
13 5 5
4
7
この例は図1 と対応する.攻撃力が7 の場合は隠れる場所が無いため,-1 -1 を出力する.
Page 3 of 3