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




可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 1 – Solitaire
ソリティア(Solitaire)
JOI 君は,縦に3 マス,横にN マスの方眼状のボードと,いくつかのコマを使ってゲームをしている.
ゲームの初期状態において,1 個以上のマスにはコマが置かれており,また,1 個以上のマスにはコマが置
かれていない.
このゲームの目的は,コマの置かれていないマスにコマを1 個ずつ置いていくことで,ボード上のすべ
てのマスにコマが置かれた状態にすることである.ただし,あるマスにコマを置ける条件は,以下のいず
れかが満たされることである.
• そのマスの一つ上のマスと一つ下のマスの両方にコマが置かれている.
• そのマスの一つ左のマスと一つ右のマスの両方にコマが置かれている.
JOI 君はゲームの初期状態から始めて,目的を達成するまでにコマを置いていく順番が全部で何通りあ
るのかが気になった.ただしこの値は非常に大きくなることがある.
あなたの課題は,JOI 君の代わりに,ゲームの初期状態から目的を達成するまでにコマを置いていく順
番の個数を1 000 000 007 で割った余りを求めることである.
課題
ゲームの初期状態が与えられたとき,目的を達成するまでにコマを置いていく順番の個数を1 000 000 007
で割った余りを求めるプログラムを作成せよ.
入力
標準入力から以下のデータを読み込め.
• 1 行目には,整数N が書かれている.これは,ゲームで使うボードの大きさが,縦に3 マス,横に
N マスであることを表す.
• 続く3 行のそれぞれには,N 文字からなる文字列が書かれている.各文字は‘o’ もしくは‘x’ である.
この3 行のうちのi 行目(1 ≦i ≦3) の左からj 文字目(1 ≦j ≦N) は,ボードの上からi 行目,左か
らj 列目のマスの初期状態を表す.この文字が‘o’ のときは,ゲームの初期状態においてそのマスに
コマが置かれていることを表す.また,‘x’ のときは,ゲームの初期状態においてそのマスにコマが
置かれていないことを表す.
出力
標準出力に,目的を達成するまでにコマを置いていく順番の個数を1 000 000 007 で割った余りを1 行で
出力せよ.
ソリティア– 1 / 4
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 1 – Solitaire
制限
すべての入力データは以下の条件を満たす.
• 1 ≦N ≦2 000.
小課題
小課題1 [10 点]
以下の条件を満たす.
• ゲームの初期状態において,コマの置かれていないマスの個数は16 個以下である.
• N ≦30.
小課題2 [12 点]
• ゲームの初期状態において,コマの置かれていない各マスについて,そのマスに上下左右に隣り合う
マスのうちコマの置かれていないマスの個数が2 個以下である.
小課題3 [20 点]
以下の条件を満たす.
• ゲームの初期状態において,コマの置かれていないマスが縦に3 個連続して並ぶことはない.
• N ≦30.
小課題4 [38 点]
• N ≦300 を満たす.
小課題5 [20 点]
追加の制約はない.
ソリティア– 2 / 4
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 1 – Solitaire
入出力例
入力例1 出力例1
3 14
oxo
xxo
oxo
この入力例では,ゲームの初期状態は以下の通りである(コマの置かれたマスを○で表す).
○ ○
○
○ ○
次のいずれかの表に従ってコマを置いていくことで,目的を達成することができる(番号はコマを置い
ていく順番を表す).
○ 1 ○ ○ 1 ○ ○ 1 ○ ○ 1 ○ ○ 2 ○
2 3 ○ 2 4 ○ 3 4 ○ 4 3 ○ 1 3 ○
○ 4 ○ ○ 3 ○ ○ 2 ○ ○ 2 ○ ○ 4 ○
○ 2 ○ ○ 3 ○ ○ 4 ○ ○ 3 ○ ○ 4 ○
1 4 ○ 1 2 ○ 1 2 ○ 1 4 ○ 1 3 ○
○ 3 ○ ○ 4 ○ ○ 3 ○ ○ 2 ○ ○ 2 ○
○ 2 ○ ○ 2 ○ ○ 3 ○ ○ 4 ○
3 4 ○ 4 3 ○ 2 4 ○ 2 3 ○
○ 1 ○ ○ 1 ○ ○ 1 ○ ○ 1 ○
目的を達成する順番はこれらの14 通りのみであるので,14 を出力する.
入力例2 出力例2
10 149022720
ooxooxoxoo
xooxxxoxxx
oxoxoooooo
入力例2 はすべての小課題の制約を満たす.
ソリティア– 3 / 4
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 1 – Solitaire
入力例3 出力例3
10 0
ooxoxxoxoo
oxxxxxoxxx
oxooxoxoxo
ゲームの初期状態によっては,目的を達成できないこともある.
入力例4 出力例4
20 228518545
oxooxoxooxoxooxoxoxo
oxxxoxoxxxooxxxxxoox
oxooxoxooxooxooxoxoo
ソリティア– 4 / 4