京都大学プログラミングコンテスト2015

B - GUARDIANS


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

あなたは幾多の試練を乗り越えた凄腕の冒険者であり,冒険で数々の宝物を手にした.これらを隠しダンジョンの奥にある宝物庫に保管し,番犬と妖怪鎖頭に守ってもらうことにした.隠しダンジョンは以下のような 10 \times 10 の空間であり,一番左の 10 マス全てがダンジョンの入り口とつながっていて,一番右の 10 マス全てが宝物庫へとつながっている.

..........
..........
..........
..........
..........
..........
..........
..........
..........
..........

現在,隠しダンジョンには何も置かれていない.宝を狙う命知らずな侵入者は一番左のいずれかのマスから侵入し,一番右のいずれかのマスを目指す. 侵入者が隠しダンジョンに入ると同時に番犬が左から侵入者を追いかけるので,侵入者は右上,右,右下のいずれかのマスにしか移動できない. また, 10 \times 10 の空間の外に出ることもできない. あなたは隠しダンジョンに鎖頭をたくさん配置して侵入者を阻むことにした.鎖頭は以下の特徴をもつ.

  • 鎖頭は移動することができない.
  • 鎖頭は縦横斜めの好きな方向に自分がいるマスから2マス先まで頭を投げつける一撃必殺の攻撃を放つ.
鎖頭がいる場所を C とすると,その 鎖頭 の攻撃可能な範囲は以下の X で表される.侵入者は以下のC, Xが書かれた範囲に立ち入ると,再起不能となる.
.......
.X.X.X.
..XXX..
.XXCXX.
..XXX..
.X.X.X.
.......

隠しダンジョンを鎖頭で埋め尽くしてしまうと全ての侵入者を排除できるが,それでは面白くないと感じたあなたは,侵入者が鎖頭に攻撃されずにスタートからゴールへたどり着けるルートがただひとつだけ存在するように鎖頭を配置し,見事突破した侵入者にはその知略を称えて宝物の一部を差し出すことにした.

鎖頭を雇うには大金がかかる.あなたは倹約家でもあり,雇う鎖頭の数はなるべく少ないほうが良い.多くても誤答とはならないが,満点が得られるとは限らない.詳しくは部分点の制約を確認してほしい.経路が一通りに定まる配置をひとつ出力せよ.


入力

この問題に入力は存在しない.

出力

10 \times 10 の隠しダンジョンの盤面を出力せよ.Cはそこに鎖頭が配置されることを表し,.はそこには何もないことを表す.追記: Cは大文字であることに注意せよ. 出力にこれら2種類の文字と改行以外が含まれている場合,出力は問題の条件を満たしていないものとみなされるので注意せよ.

部分点

この問題には部分点が存在する.配点は以下の通りである.
  • 盤面が問題文中の左端から右端への経路をただ一通りに定める場合,Accepted と判定され, N 体の鎖頭 を配置した時,floor(400 (max(4, N-1))) 点が与えられる.
  • そうでない場合,Wrong Answer と判定され,点数は得られない.
  • システムの都合上,Accepted X 点を獲得した場合,それまでに提出した Accepted な解法のうち, X 点 未満のものは全て誤答としてカウントされ,ペナルティが発生するので注意すること.

ヒント

  • N = 5 の解でも満点が得られるが, N = 4 の解も存在する.

出力例1

CCCCCCCCCC
CCCCCCCCCC
..........
..........
..........
..........
..........
CCCCCCCCCC
CCCCCCCCCC
CCCCCCCCCC

左端から右端までの経路が一通りのみ存在し,配置した鎖頭50 体である.この盤面を提出した場合, 8 点が得られる.


出力例2

CCCCC.C...
CCCC.C....
CCC.C.....
CC.C.....C
C.C.....C.
.C.....C.C
C.....C.CC
.....C.CCC
....C.CCCC
...C.CCCCC

左端から右端までの経路が一通りのみ存在し,配置した鎖頭44 体である.この盤面を提出した場合, 9 点が得られる.


出力例3

CCCCCCCCCC
CCCCCCCCCC
..........
..........
..........
..........
..........
CC.....CCC
CCCCCCCCCC
CCCCCCCCCC

この盤面では,左端から右端への道がただ一通りに定まらない.左から右へ直進するルートと,一度右下に移動した後に右上に移動するルートがある.提出した場合, Wrong Answer と判定され,点は得られない.


出力例4

CCCCCCCCCC
..........
..........
..........
.C........
..........
..........
.C........
..........
..........

この盤面では,左端から右端への道が存在しない.侵入者はCのマスにも立ち入れず, 10 \times 10 の空間の外に出ることもできない点に注意せよ.提出した場合, Wrong Answer と判定され,点は得られない.


また、全ての出力例に対する、鎖頭による攻撃範囲をXで埋めた盤面は以下の通りである.
CCCCCCCCCC
CCCCCCCCCC
XXXXXXXXXX
XXXXXXXXXX
..........
XXXXXXXXXX
XXXXXXXXXX
CCCCCCCCCC
CCCCCCCCCC
CCCCCCCCCC
CCCCCXCXX.
CCCCXCXX.X
CCCXCXX.XX
CCXCXX.XXC
CXCXX.XXCX
XCXX.XXCXC
CXX.XXCXCC
XX.XXCXCCC
X.XXCXCCCC
.XXCXCCCCC
CCCCCCCCCC
CCCCCCCCCC
XXXXXXXXXX
XXXXXXXXXX
..........
XXXX.XXXXX
XXXXXXXXXX
CCXXXXXCCC
CCCCCCCCCC
CCCCCCCCCC
CCCCCCCCCC
XXXXXXXXXX
XXXXXXXXXX
XXX.......
XCXX......
XXXX......
XXXX......
XCXX......
XXX.......
.X.X......

Source name

京都大学プログラミングコンテスト2015

Submit提出する