AtCoder Regular Contest 019

A - お買い物クライシス

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

私は今 ARC ゲームズという会社の Ancient Royal Coders という、冒険しながら競技プログラミングの知識が身につくロールプレイングゲームをプレーしている真っ最中である。

といってもまだゲームは始まったばかりで、これから最初のダンジョンへ向かうところだ。とりあえず薬草をいくつか購入するために街にあるショップへ行っておこう。

ショップへ到着し薬草を購入しようとして値段を確認すると、これがなんだか奇妙だ。画面には 1Z0 ゴールド と値段が表示されているが、これは本当に 120 なのだろうか……？

他のアイテムもよく見てみると、なんと一部の数字が似たようなアルファベットに置き換わっているではないか！これでは、値段が 36 進数として解釈されてしまい法外な金額を要求されかねない！

なるほどなるほど、ぼったくりを回避するためにはこの奇妙な表記を数字のみからなる正しい表記に戻すためのプログラムを書かないといけないというわけか。序盤からなかなか骨のあるゲームだ。調べてみたところ、置き換わっている文字の種類は以下のようなものがあるらしい。

O → 0
D → 0
I → 1
Z → 2
S → 5
B → 8

さて、早速そのためのプログラムを書くこととしよう。

入力

入力は以下の形式で標準入力から与えられる。

1 行目には、画面に表示されている値段 S が書かれている。
- S は 1 文字以上 8 文字以下の文字列で、 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, O, D, I, Z, S, B の 16 種類の文字からなる。
- S の先頭の文字は 0, O, D のいずれでもない。

出力

画面に表示されている値段を、数字のみからなる正しい表記に直したときの金額を 1 行に出力せよ。

出力の末尾にも改行をいれること。

入力例1

1Z0

出力例1

Z を対応する 2 に書き換えると、120 ゴールドが正しい金額であることがわかります。

この例からもわかるように、たとえば必ずしもすべての 1 が I に書き換わっているとは限りません。

入力例2

4ZD6O

出力例2

O と D はどちらも 0 に対応しています。

入力例3

BI9Z

出力例3

B - こだわりの名前

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

ゲームも中盤にさしかかり、ちょうど海に出るための船を手に入れた。早く新たなダンジョンへ挑戦したいところだが、その前に船にかっこいい名前をつけねばならない。

早く先に進みたいので船の名前はデフォルトのものでいいかと思ったが、さすがにそれでは面白くないのでデフォルトの名前から 1 文字だけ変更することにしよう。

ところで、こういう場面でプログラミングコンテストの問題文の登場人物はなぜか「名前が回文になるようにしよう」とかいう訳のわからないこだわりを発揮することが多いのだが、私はそういう普通の登場人物とは違うのだ。私に変なこだわりはないので、船の名前は 回文でない ものにしたい。

さて、デフォルトの名前を 1 文字だけ変更することで、回文でない名前は何通りぐらい作ることができるのだろうか？プログラムを書いて確かめることとしよう。ちなみに船の名前として使える文字はアルファベットの大文字だけだ。

え？「回文でない名前にしたい」というのは「変なこだわり」ではないのかって？言われてみれば確かにその通りだし、やはり私はプログラミングコンテストの登場人物としての宿命から逃れることはできないのかもしれない。しかし、私のような者がこうして変なこだわりを持つことで多くの人がプログラミングコンテストを楽しんでくれるのであれば、それはそれで良いことなのだろう。

入力

入力は以下の形式で標準入力から与えられる。

1 行目には、船のデフォルトの名前 A が書かれている。
- A は 1 文字以上 3 \times 10^5 文字以下のアルファベットの大文字のみからなる文字列である。

出力

デフォルトの名前から 1 文字を選び、その文字を別の大文字アルファベットに変更することで得られる 回文でない 文字列が何通りあるかを表す数値を 1 行に出力せよ。

なお、回文とは前から読んでも後ろから読んでも同じとなる文字列のことである。たとえば ANNA, MADAM, X は回文だが、AB, ARC は回文ではない。

出力の末尾にも改行をいれること。

入力例1

ARC

出力例1

1 文字目の A を他の文字に変更する場合
- C に変更すると CRC は回文となってしまいます。
- それ以外の 24 通り(たとえば BRC, XRC など)はいずれも回文ではありません。
2 文字目の R を他の文字に変更する場合
- どの文字に変更しても回文にはならないので 25 通りが考えられます。
3 文字目の C を他の文字に変更する場合
- A に変更すると ARA は回文となってしまいます。
- それ以外の 24 通りはいずれも回文ではありません。

したがって、答えは 24 + 25 + 24 = 73 通りとなります。

どれか 1 つの文字を変更したもののみを考えること、すなわちどの文字も変更していない ARC という名前については数えないことにも注意してください。

入力例2

出力例2

1 文字の文字列はすべて回文になります。

入力例3

NOLEMONNOMELON

出力例3

C - 最後の森

実行時間制限: 2 sec / メモリ制限: 256 MB

長い冒険もようやく終盤を迎え、あとは魔王の城に突入するのみとなった。

魔王の城は「最後の森」と呼ばれる場所にある。最後の森は縦 R 行、横 C 列のマス目で構成されており、それぞれのマスは以下のいずれかである。

平地……平地のマスは自由に通行できる。
木……木のあるマスは通行できない。
強敵のいるマス……凶暴な強敵のいるマスである。後述の条件を満たさなければ通行できない。
プレイヤーの村……プレイヤーの初期位置である。このマスは自由に通行できる。
ほこら……伝説の剣 Link-Cut Sword があるほこらである。このマスは自由に通行できる。
魔王の城……魔王の城があるマスである。このマスは自由に通行できる。

村のあるマス、ほこらのあるマス、魔王の城があるマスはちょうど 1 つずつである。

以下、i 行 j 列 (1 ≦ i ≦ R,1 ≦ j ≦ C)にあるマスのことをマス (i,j) と呼ぶことにする。2 つの異なるマス (i,j),(k,l) (i と k は1 ≦ i,k ≦ R を、j と l は 1 ≦ j,l ≦ C を満たし、(i,j) ≠ (k,l) であるとする) が辺を共有しているとき、つまり以下の条件をみたす場合に隣接していると定義する。

i = k かつ j と l との差の絶対値が 1 である。
j = l かつ i と k との差の絶対値が 1 である。

プレイヤーは最初村のあるマスにいる。プレイヤーは以下の動作を行うことができる。

プレイヤーのいるマスと隣接しているマスに移動する。このとき移動先のマスが自由に通行できるマスでなければならない。
プレイヤーのいるマスと隣接しているマスにいる強敵と戦闘を行う。戦闘を行った強敵は取り除かれ、以降そのマスは自由に通行可能になる。

魔王との戦いでは高難易度のプログラミングスキルが要求されることだろう。魔王に対向するためには手持ちの装備（ライブラリ）を強化させなければならない。特に、ほこらにある伝説の剣を入手しなければ魔王に勝つことが出来ないだろう。そのためほこらに寄って伝説の剣を入手してから魔王の城に行きたい。伝説の剣を入手していない状態で魔王の城のあるマスを通行することは許される。

また、最後の森に生息する強敵との戦いは大変なので、伝説の剣を入手する前後合わせて K 回以内の戦闘に抑えたい。

最後の森には魔王が発する猛毒の霧が立ち込めているため、出来る限り移動にかかる時間を短くしなければならない。最後まで手強いゲームだ。そこでプログラムを用いて、上記の条件を満たす移動経路として考えられるものの中で、移動回数が最小となるものの移動回数が知る必要が出てきた。

入力

入力は以下の形式で標準入力から与えられる。

R C K
s_{(1,1)} s_{(1,2)}  … s_{(1,C)}
s_{(2,1)} s_{(2,2)}  … s_{(2,C)}
:
s_{(R,1)} s_{(R,2)}  … s_{(R,C)}

1 行目には、3 つの整数 R,C,K(R と C は 1 ≦ R,C ≦ 50 を、K は 0 ≦ K ≦ 100 をみたす) が空白を区切りとして与えられる。
2 行目から R 回、長さ C の文字列が 1 行ずつ与えられる。各文字は .,T,E,S,C,G のいずれかであり，i 回目 (1 ≦ i ≦ R) に与えられられる文字列のうち j 文字目 (1 ≦ j ≦ C) について、
- その文字が . なら、マス (i,j) が平地のマスであること
- その文字が T なら、マス (i,j) が木があるマスであること
- その文字が E なら、マス (i,j) が強敵のいるマスであること
- その文字が S なら、マス (i,j) が村のあるマスであること
- その文字が C なら、マス (i,j) がほこらのあるマスであること
- その文字が G なら、マス (i,j) が魔王の城があるマスであること
をあらわす。村のあるマス、ほこらのあるマス、魔王の城があるマスはちょうど 1 つずつである。

出力

移動回数の最小値を出力するプログラムを作成せよ。条件を満たす移動経路が存在しない場合は -1 を出力せよ。

なお、出力の最後には改行を入れること。

入力例 1

5 7 3
GET..ET
..T....
.TEST..
.E.T.ET
...ETC.

出力例 1

プレイヤーは最初にマス (3,4) にいる。例えば、以下のように移動する。

マス (3,4) からマス (3,6) に移動する。

移動を完了するには最小で 4 回の移動動作を行う必要がある。
移動完了時、合計移動回数は 4 回、合計戦闘回数は 0 回である。

マス (4,6) にいる強敵と戦闘を行う。

戦闘終了時、合計移動回数は 4 回、合計戦闘回数は 1 回である。

マス (3,6) からほこらのあるマス (5,6) に移動する。

移動を完了するには最小で 2 回の移動動作を行う必要がある。
移動完了時、合計移動回数は 6 回、合計戦闘回数は 1 回である。

ほこらのあるマス (5,6) からマス (3,4) に移動する。

移動を完了するには最小で 6 回の移動動作を行う必要がある。
移動完了時、合計移動回数は 12 回、合計戦闘回数は 1 回である。

マス (3,3) にいる強敵と戦闘を行う。

戦闘終了時、合計移動回数は 12 回、合計戦闘回数は 2 回である。

マス (3,4) からマス (4,3) に移動する。

移動を完了するには最小で 2 回の移動動作を行う必要がある。
移動完了時、合計移動回数は 14 回、合計戦闘回数は 2 回である。

マス (4,2) にいる強敵と戦闘を行う。

戦闘終了時、合計移動回数は 14 回、合計戦闘回数は 3 回である。

マス (4,3) から魔王の城があるマス (1,1) に移動する。

移動を完了するには最小で 5 回の移動動作を行う必要がある。
移動完了時、合計移動回数は 19 回、合計戦闘回数は 3 回である。

入力例 2

5 7 2
GET..ET
..T....
.TEST..
.E.T.ET
...ETC.

出力例 2

入力例 1 のときと比べて戦闘可能な回数が少ないため、少し遠回りする必要がある。

入力例 3

5 7 1
GET..ET
..T....
.TEST..
.E.T.ET
...ETC.

出力例 3

-1

入力例 3 において、条件を満たす経路は存在しない。

入力例 4

6 35 4
T...TT.....TT...TTT...TTT..TTG.....
..T..T.TTT.T..T..E..T..E...TTT.TTT.
.TTT.T.....E.TTTTT.TTT.TTT.TTT.....
.....T.TT.TT.TTTTT.TTT.TTT.TTTTTTT.
.TTT.T.TT..T..T..S..T..TTT.TTTTTTT.
.CTT.E.TTT.TT...TTT...TT.....E.....

出力例 4

D - ほんとうのたたかい

実行時間制限: 2 sec / メモリ制限: 256 MB

ついに魔王を倒し、世界に平和が訪れた！

しかしながら、私のたたかいはまだ終わっていない！月 1 回の高級おやつを巡って、妹との勝負が残っているのだ！

何を隠そう私の妹は競技プログラミングに長けていて、毎回私と競技プログラミングで戦っては勝利し、高級おやつは妹のものになってしまうのだ！

（まあ、私の家が競技プログラミングの家系で、高級おやつは競技プログラミングの出来具合で決まるというきまりになっているから、しょうがないね。）

毎回妹に負けてしまい、延々高級おやつにありつけず、年上としての威厳もズタズタである私は、密かに競技プログラミングのスキル上昇に精進していたのだ！その一環として先程のゲーム Ancient Royal Coders をプレイしていたのである！

そして今回も高級おやつを巡って妹と勝負をすることになっている。

今回の競技は以下の条件を満たす縦 N 行、横 N 列のマス目を作成し、提出することで勝負するらしい。

N は 2 ≦ N ≦ 150 を満たす整数でなければならない。
各マスには 1 つの O が描かれているか、描かれていないかのいずれかである。
縦横の辺がいずれも行または列に平行な、どの長方形を取り出しても、その長方形の 4 隅のいずれか 1 つは O が描かれていないマスである。言い換えると、1 ≦ i < k ≦ N および 1 ≦ j < l ≦ N をみたす任意の 4 つの整数 i,j,k,l において、以下の条件が成立することである。

p 行 q 列にあるマスのことを (p,q) と呼ぶことにしたとき、(i,j),(i,l),(k,j),(k,l) のうち少なくとも 1 つは O が描かれていないマスである。

このような条件を満たす縦 N 行、横 N 列のマス目のうち、より多く O が含まれるものを提出したほうが勝利である。

今月のおやつはあの伝説のプリンらしい。ここ数年、このプリンを口にしていない。因みにこの数年の起点が、妹が競技プログラミングを始めた日と合致していることは内緒である。

幸い、今回はプリンという分配可能なおやつなので、今回は双方の出来具合でプリンを分配するよう提案し、可決された。これは私が妹の分のおやつを取ったことで妹が悲しまないようにするためで、別にちょっとだけでも貰おうとかいう考えじゃないぞ！

何よりも今回は負けない自信がある。さあ、今こそ Ancient Royal Coders で鍛えたプログラミングスキルを披露しようじゃないか！

入力

今回、入力は与えられない。

部分点

この問題には部分点が設定されている。

あなたが提出した出力に関して、出力が示すマス目に描かれている O の個数を S としたとき、以下の基準で得点が与えられる。

出力が条件を満たさないか、S ≦ 294 となる場合、残念ながらプリンは分けてもらえず、0 点である。
出力が条件を満たし、295 ≦ S ≦ 399 となる場合、プリンを微量分けてもらえる。このとき、5 点が得られる。
出力が条件を満たし、400 ≦ S ≦ 899 となる場合、プリンを 1 口分けてもらえる。このとき、10 点が得られる。
出力が条件を満たし、900 ≦ S ≦ 1299 となる場合、プリンを 1 口半分けてもらえる。このとき、20 点が得られる。
出力が条件を満たし、1300 ≦ S ≦ 1499 となる場合、プリンを 2 口分けてもらえる。このとき、30 点が得られる。
出力が条件を満たし、1500 ≦ S ≦ 1699 となる場合、プリンを 1/4 分けてもらえる。このとき、50 点が得られる。
出力が条件を満たし、1700 ≦ S となる場合、プリンを半分こできる。このとき、100 点が得られる。

出力

出力は以下ように記述すること。

1 行目には整数 N を出力する。N は 2 以上 150 以下なら任意に設定できる。
2 行目から N 回だけ、長さ N の文字列を出力する。各文字は O か . のいずれかであり、i 回目 (1 ≦ i ≦ N) の出力に置ける文字列の左から j 文字目 (1 ≦ j ≦ N) に関して、
- その文字が O なら、i 行 j 列のマスには O が描かれていること
- その文字が . なら、i 行 j 列のマスには O が描かれていないこと
を表す。

なお、出力の最後には改行を入れること。改行がない場合、他の部分が正しくてもWAとなってしまう点に注意。特に、出力後の結果画面に表示されるソースコード欄では最終行の改行の有無が判別しづらい場合があります。

出力について

この問題では、ソースコードのところに出力したい内容を書き、言語のところを Text (cat) を選択して提出することで、出力したい内容をそのまま出力として提出することができる。もちろん、この機能を使わずに他の言語のソースコードを提出しても構わないが、その場合はこの問題が指定する時間制限やメモリ制限等を満たさなければならない。

ジャッジの応答について

ジャッジの応答として、AC と WA の記述が表す意味がやや特殊である。

AC は、出力が条件を満たした場合に、最終的に得られる得点によらず出力される。
WA は、出力が条件を満たさない場合に出力される。

そのため、AC と出力されていても実際は 0 点であることがある。

出力例 1

5
.....
.....
..OOO
...O.
..O..

この出力の場合、出力は条件を満たす。しかしながら S = 5 となるため、この出力を提出しても 0 点である。

出力例 2

4
....
.OOO
..O.
.OO.

この出力の場合、2 行 2 列、2 行 3 列、4 行 2 列、4 行 3 列のいずれにも O が描かれているため、出力は条件を満たさない。よって、この出力を提出しても WA となり，0 点である。