第15回日本情報オリンピック　予選４

2015年12月13日
情報オリンピック日本委員会

解説

単純な解法として，1 秒ごとに国民をすべて動かして愚直にシミュレーションをするというのが挙げられる． この解法の時間計算量は O(NT) であり，入力 1 に対しては時間内に正答を得ることができる． また，入力 2 においても時間をかければ正答を得ることは可能であろう． しかし，それ以降の入力で時間内に正答を得るのは難しいだろう．

十分に長い時間が経過したとき，各国民がどのような行動をとっているかを考えてみよう． その国民が東に向かって歩き始め，かつ自分より東に西に向かって歩き始めた国民がいない場合，その国民は東向きに歩き続けている． また逆に西に向かって歩き始め，かつ自分より西に東に向かって歩き始めた国民がいない場合にも，その国民は西向きに永遠に歩き続ける．

そのどちらでもない場合，その国民の向かう方向に，その国民と向い合わせに歩いてくる国民が存在する．すなわち，いつかはその国民は世間話をする． いま見ている国民(以下国民 A とする)が東向きに歩いているとする．西向きの場合も同様なので，ここでは割愛する． 国民 A から東の方向に一番近いところにいる西向きに動き出した国民を国民 B ，B のひとつ西にいる国民をCとおくと，A は B と C が世間話を始めた座標に到達したところで，世間話を始める．

つまり，東向きに進む国民のすぐ東に西向きに進む国民がいるところが見つかったら，十分な時刻が経過した後には， そこから国民の列を西に見ていったときのそこから連続する東向きに進む国民と，同じく国民の列を東に見ていったときのそこから連続する西向きに進む国民はすべて，その 2 人が出会う場所で世間話をしている．

以上のアイデアをコードに起こすと以下のようになる．

国民の列を西から順に見ていく．東向きに進む国民のすぐ東に西向きに進む国民が見つかったら，その 2 人の座標の平均をtとして， そこから西向きの国民または列の先頭が現れるまで西向きに列を見ていき，見た国民すべてに対し t という値を覚えておく． また，そこから東向きの国民または列の末尾が現れるまで東向きに列を見ていき，見た国民すべてに対し t という値を覚えておく．

最後に，時刻 T において，その国民が覚えている座標までその国民が到達しているかどうかを判定し， 到達しているなら先ほど覚えておいた世間話をする位置を，いないなら単にその国民の進む向きに距離 T 進んだ位置を出力すればよい．

実装においては，十分西に東向きに進む国民を，また十分東に西向きに進む国民を置いておく工夫をすることで，場合分けが減り，よりバグを生みにくいコードが書けるであろう．

この解法の時間計算量は O(N) となり，満点が期待できる．入出力が 32 ビット符号付き整数の範囲には収まらないことに注意せよ．