実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
天下一王国のトモアキ君はある文章の校正を任されました。
その文章では天下一王国の有名人「HAGIXILE」の名前が誤表記で「HAGIYA」になってしまっています。
与えられた文字列に一つ「HAGIYA」という文字列が含まれるので「HAGIXILE」に置換して出力してください。
入力
入力は以下の形式で標準入力から与えられる。
S
- 校正の対象になる文章Sが1行に与えられる。
- Sは大文字アルファベットのみで構成される。
- S の長さ |S| は 6 \leq |S| \leq 1000 を満たす。
- S の中にはちょうど1回「HAGIYA」が出現する。
- 入力の末尾は改行で終わる。この改行は S に含まれない。
出力
変換後の文字列を1行に出力せよ。出力の末尾には改行をいれること。
入力例
MRHAGIYA
出力例
MRHAGIXILE
出典
天下一プログラマーコンテスト2014 予選B実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
トモアキ君は天下一王国流魔術の新しい呪文を習得しようと試みています。
トモアキ君は、自分が覚えているフレーズを組み合わせて呪文を詠唱します。
呪文の詠唱には同じフレーズを複数回使うことができます。
例えば aaa, bbb, ccc という 3 つのフレーズを記憶していた場合、aaaccc, aaabbb, cccaaaaaa といった呪文を詠唱することが可能です。
トモアキ君は、新しく習得しようとしている呪文を、覚えているフレーズを組み合わせて詠唱することができるか不安になりました。
トモアキ君のために、呪文を構築するためのフレーズの並べ方がどれくらいあるか数えるプログラムを作成してください。
並べ方の数は大きくなる可能性があるので、1000000007 で割った余りを出力して下さい。
入力
入力は以下の形式で標準入力から与えられる。
N S T1 T2 : TN
- 1 行目には、トモアキ君が記憶しているフレーズの数 N (1 \leq N \leq 100) が与えられる。
- 2 行目には、トモアキ君が覚えたい呪文 S が与えられる。
- S の長さ |S| は 1 \leq |S| \leq 1000 を満たす。
- S は小文字アルファベットからなる。
- 3 行目から N 行は、トモアキ君が記憶しているフレーズ Ti が与えられる。
- Ti の長さ |Ti| は 1 \leq |Ti| \leq 1000 を満たす。
- Ti は小文字アルファベットからなる。
- i \neq j ならば Ti \neq Tj を満たす。
出力
呪文を構築するためのフレーズの並べ方の数を 1000000007 で割ったあまりを 1 行で出力せよ。出力の末尾には改行をいれること。
入力例1
3 eternalstaticfinal eternal static final
出力例1
1
並べ方は 1 通りしかありません。
入力例2
5 eternalstaticfinal eternal static final fin al
出力例2
2
並べ方は下記の 2 通りがあります。
eternal + static + final eternal + static + fin + al
入力例3
5 abcdef abc def abcdef d ef
出力例3
3
並べ方は下記の 3 通りがあります。
abcdef abc + def abc + d + ef
入力例4
5 aaaa a aa aaa aaaa b
出力例4
8
並べ方は下記の 8 通りがあります。
aaaa aaa + a aa + aa aa + a + a a + aaa a + aa + a a + a + aa a + a + a + a
トモアキ君が覚えているbはこの呪文では使用しませんでした。
入力例5
10 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaaa aaaaaaaaaa
出力例5
146491918
並べ方の数は大きくなる可能性があるので、1000000007 で割った余りを出力して下さい。
出典
天下一プログラマーコンテスト2014 予選B実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
天下一王国の歴史を学んでいるトモアキ君は、王国を導いた偉大な英雄である HAGIXILE について調べています。
HAGIXILE は奇行で知られる人物でした。彼は王国の領土を N \times N のマスに分割された盤面とし、白マスと黒マスに分けて扱いました。
白マスはその年に巡遊する地域、黒マスはその年に巡遊しない地域を意味したそうです。
マスの色は年ごとに変化しました。色は前年の盤面のマスの色を元に塗り替えられます。
あるマスの上下左右に隣接するマスのうち、塗り替え前に黒だったマスの個数が偶数なら、塗り替え後のそのマスは白マス、奇数なら黒マスになります。
四隅のマスに隣接するマスは 2 つ、端のマス (四隅のマスを除く) に隣接するマスは 3 つ、端以外のマスに隣接するマスは 4 つあります。
例えば、白マスを . で、黒マスを # で表すとして、ある年の盤面が以下だった場合、
.#. .## .#.
翌年は以下のように塗り替えられます。
##. ### ##.
トモアキ君は、知られている最古の盤面が歴史書に載っているのを見付け、その盤面の塗り替え前の盤面を復元することを思い付きました。
最古の盤面が与えられるので、塗り替え前の盤面としてありうるものを 1 つ答えてください。ただし、そのような塗り替え前の盤面は必ず 1 つ以上存在するものとします。
入力
入力は以下の形式で標準入力から与えられる。
N C1,1C1,2..C1,N C2,1C2,2..C2,N : CN,1CN,2..CN,N
- 1 行目には、列数と行数を表す整数 N (1 \leq N \leq 750) が与えられる。
- 2 行目から N 行は、i 行目 j 列目のマスの色 Ci,j (1 \leq i, j \leq N) が与えられる。
- 白マスを . として表現し、黒マスを # として表現するものとする。
- 与えられる盤面には、少なくとも 1 つの塗り替え前の盤面がありうる。
部分点
- 1 \leq{} N \leq{} 3 のケースに正解した場合、部分点として25点を与える。
- 1 \leq{} N \leq{} 9 のケースに正解した場合、部分点としてさらに30点を与える。
出力
与えられた盤面の塗り替え前の色を 1 行に N 文字ずつ N 行で出力せよ。出力の末尾には改行をいれること。
入力例1
3 ##. ### ##.
出力例1
.#. .## .#.
出力の盤面の 1 行 1 列目のマスについて、上にマスはありません。左にもマスはありません。右のマスは # です。 下のマスは . です。1 行 1 列目のマスの上下左右のマスで、# マスの個数が 1 となり、奇数なので塗り替え後の色は # です。
同様に、出力の盤面の 1 行 2 列目のマスについて、上にマスはありません。左のマスは . です。 下のマスは # です。 右のマスは . です。 # マスの個数が 1 となり、奇数なので塗り替え後の色は # です。
また同様に、出力の盤面の 1 行 3 列目のマスについて、上にマスはありません。左のマスは # です。下のマスは # です。右のマスはありません。# マスの個数が 2 となり、偶数なので塗り替え後の色は . です。
すべてのマスに対してこのような塗り替えを行うと、入力の盤面と一致するため正解です。
入力例2
5 ..... ..... ..... ....# ...#.
出力例2
..... ..... ..... ..... ....#
入力例3
10 #...#.#.#. .####.#..# ##..###..# #...###... .#.#.##... ..##.##..# ######..#. .#.....#.. .#...##### ..##...###
出力例3
########## ....#.#.## #..#.#.#.# #.#..#..#. .......... ####..#.#. #.#.#.#... ....####.. ####..#.#. ##.#.#..#.
出典
天下一プログラマーコンテスト2014 予選B実行時間制限: 3 sec / メモリ制限: 256 MB
問題文
天下一王国の姫の命令で、画家でもあるトモアキ君は長方形の壁画を描くことになりました。
しかし、この仕事には困ったことが2つあります。
-
壁画を描くのに使う塗料は、姫に指定されたペンキを使わなければなりません。
- 姫に指定されたペンキはすべて異なる色です。塗った領域がそれぞれ異なる色で彩色されます。
- 各ペンキには「濃さ」があります。そのペンキよりも「濃さ」の値が低いペンキに対しては上から重ね塗りをして、そのペンキの色で上書きすることができますが、値が同じか高いペンキに対して上から重ね塗りをしてはいけません。
-
トモアキ君は天下一の不器用です。
- トモアキ君は、壁画の縦横に対して各辺が平行な長方形しか塗ることはできません。
- 1度使った色のペンキを2度使うことはできません。
トモアキ君は、なんとか壁画を完成させるためにまず壁画の設計図を作りました。
この設計図は、サイズ 1 \times 1 のマス目に分割されており各マスに番号が指定されています。
- 各マスの番号は色分けの指定をするものです。同じ番号のマスは同じ色になるように、異なる番号のマスは異なる色になるように塗られていなくてはいけません。
- マスの番号とペンキは任意の組み合わせで構いません。
- すべてのペンキを使用しなくても構いません。
- すべてのマスは、ペンキで1回以上塗らなくてはいけません。
壁画の制作を失敗できないトモアキ君は、与えられたペンキでこの設計図どおりに壁画を描くことができるか調べることにしました。
入力
N
A_1
A_2
:
A_N
H W
B_{1,1} B_{1,2} ... B_{1,W}
B_{2,1} B_{2,2} ... B_{2,W}
:
B_{H,1} B_{H,2} ... B_{H,W}
- 1行目では、使用できるペンキの数を表す整数 N (1 \leq{} N \leq{} 17) が与えられる。
- 2行目から N 行では、各ペンキの濃さを表す整数 A_i (0 \leq{} A_i \leq{} 255) が与えられる。
- N+2 行目では、設計図の高さを表す整数 H (1 \leq{} H \leq{} 200) と、設計図の幅を表す整数 W (1 \leq{} W \leq{} 200) が与えられる。
- N+3 行目から H 行は設計図の情報が与えられる。そのうちの y (1 \leq{} y \leq{} H) 行目には、各マスの番号がスペース区切りで W 個与えられる。y 行目の左側から x (1 \leq{} x \leq{} W)番目に、設計図の上から y マス、左から x マスの位置のマス目の番号、整数 B_{y,x} (0 \leq{} B_{y,x} \leq{} N - 1) が与えられる。
部分点
- 1 \leq{} N \leq{} 5 かつ 1 \leq{} H, W \leq{} 5のすべてのテストケースに正解した場合、部分点として35点を与える
- 1 \leq{} N \leq{} 9 のすべてのテストケースに正解した場合、部分点としてさらに40点を与える
出力
与えられたペンキで設計図どおりに塗ることが可能なら1、不可能なら0を1行で出力せよ。出力の末尾には改行をいれること。
入力例1
5 4 0 4 10 4 2 3 3 1 3 0 2 0
出力例1
1
与えられたペンキを上から順にA, B, C, D, Eとすると以下の順番で塗りわけることが可能です。
BBB BBB
BBB AAA
BCB AAA
BCB ADA
今回の塗り方ではEは使用しませんでした。
入力例2
5 4 0 4 10 4 2 4 3 1 2 3 0 1 2 0
出力例2
0
与えられたペンキで塗ることはできません。
入力例3
2 1 2 2 2 0 1 1 0
出力例3
0
与えられたペンキで塗ることはできません。
入力例4
5 1 1 66 30 1 5 5 3 4 4 4 2 3 4 4 0 0 3 4 4 0 0 3 3 1 0 0 3 3 1 1 2
出力例4
1
与えられたペンキを上から順にA, B, C, D, Eとすると以下の順番で塗りわけることが可能です。
A A # # # A A # # # A A # # # A A # # # A A # # #
A A B B # A A B B # A A B B # A A B B # A A B B #
A A B B E A A B B E A A B B E A A B B E A A B B E
A D D D E A D D D E A D D D E A A B B E A A B B E
A D D D E A D D C C A D D C C A A B C C A A B B E
出典
天下一プログラマーコンテスト2014 予選B実行時間制限: 4 sec / メモリ制限: 256 MB
問題文
トモアキ君は天下一王国のアイドルが大好きで、カラオケでは天下一王国のアイドルの曲しか歌いません。
天下一王国のアイドルの曲は合計で L 曲カラオケで歌うことができ、それらを曲 1、曲 2、…、曲 Lと呼びます。
トモアキ君が全力で曲 i を歌うと、カラオケの採点で毎回 K_i 点を取ることができます。
トモアキ君は天下一王国のアイドルの曲を侮辱することは決してしないため、毎回全力で歌います。
ランキングは、その月に獲得した、直近 M 回の「補正込みの点数」の和で決まります。
「補正込みの点数」は、採点結果の点数を x 点としたとき、 x + (x - その曲のその時点での平均点) で計算されます。
「その曲のその時点での平均点」とは、その月の、その x 点を取った回以前 (その回を含む) に、その曲が歌われたときの採点結果の点数の平均となります。
トモアキ君は、超人的なプログラミング能力を駆使して、今月に天下一王国のアイドル関係の曲が、どのタイミングで歌われ、どれだけの点数が取られるかを予測しました。
トモアキ君の予測によると、今月の i 番目に天下一王国のアイドルの曲を歌う人は曲 A_i を歌い、S_i 点を取るということです。
今月はまだ始まったばかりで、まだ誰もどの天下一王国のアイドルの曲を歌っていない状態です。
トモアキ君は、好きなタイミングで歌うことができ、また、任意の 2 人が歌う間、および最初に歌う人の前、最後に歌う人の後に何回でも歌うことができます。
トモアキ君は、来月の予測をしていない上、毎回全力で歌うため、今月にちょうど M 回だけ歌い、ランキング上位を目指します。
トモアキ君は、 M 回の補正込みの点数の和を最大化するような最適な戦略を知りたいです。
そこで、トモアキ君の予測が正しいと仮定して、トモアキ君が歌うべきタイミングを求めるプログラムを書いてください。
入力
入力は以下の形式で標準入力から与えられる。
L N M K_1 K_2 .. K_L A_1 S_1 A_2 S_2 : A_N S_N
- 1 行目には、天下一王国のアイドルの曲の数を表す整数 L\ (1 ≦ L ≦ 100,000) 、今月トモアキ君以外によって天下一王国のアイドルの曲が歌われる回数を表す整数 N\ (1 ≦ N ≦ 100,000) 、トモアキ君が今月歌う回数を表す整数 M\ (1 ≦ M ≦ 100,000) がスペース区切りで与えられる。
- 2 行目には、トモアキ君が、天下一王国のアイドルの曲を歌った時に獲得可能な点数の情報が、 L 個の数によって、スペース区切りで与えられる。このうち、 i\ (1≦i≦L) 番目の数 K_i\ (68.000 ≦ K_i ≦ 100.000) は、 i 番目の曲でトモアキ君が獲得可能な点数を表す。
- 3 行目から N 行では、トモアキ君以外の人が歌った曲と、その点数のデータが、1 行ずつ与えられる。そのうち i\ (1≦i≦N) 行目では、i番目に歌われた曲の番号を表す整数 A_i\ (1≦A_i≦L) と、その時の点数 S_i\ (68.000 ≦ S_i ≦ 100.000) がスペース区切りで与えられる。
- K_i および S_i は、小数点以下ちょうど 3 桁与えられる。
部分点
- L = 1 かつ 1 ≦ N,M ≦ 2,000 を満たす全てのテストケースに正解した場合、部分点として 30 点が与えられる。
- 1 ≦ L,N,M ≦ 2,000 を満たす全てのテストケースに正解した場合、部分点として上記とは別に 30 点が与えられる。
出力
トモアキ君の最適戦略を意味する M 行を出力せよ。
ここで、i 行目は 2 つのスペース区切りの整数 T_i, B_i を出力し、T_i は i 番目にトモアキ君が歌うタイミングを、B_i は i 番目にトモアキ君が歌う曲を意味する。
この出力は、 0 ≦ T_1 ≦ T_2 ≦ ... ≦ T_M ≦ N でなければならない。
T_i = k というのは、トモアキ君以外で天下一王国のアイドルの曲がちょうど k 回歌われた後に、トモアキ君が i 番目に歌う曲 B_i を歌うことを意味する。
複数の最適戦略がある場合は、最適戦略のうちの任意の 1 つを出力せよ。
出力の最後に改行を入れること。
入力例1
1 5 3 80.000 1 68.000 1 70.000 1 85.000 1 72.000 1 68.000
出力例1
2 1 2 1 5 1
このケースは、曲数が 1 曲しか存在しません。
まず、トモアキ君以外で 2 人目が歌い終わった時に歌うと、補正込みの点数は 80.000 + (80.000 - \frac{68.000 + 70.000 + 80.000}{3}) = 87.33333... となります。
続けざまに歌うと、補正込みの点数は 80.000 + (80.000 - \frac{68.000 + 70.000 + 80.000 + 80.000}{4}) = 85.5 となります。
3 回目に歌うのは、トモアキ君以外で 5 人目が歌い終わった後にすると、補正込みの点数は、
80.000 + (80.000 - \frac{68.000 + 70.000 + 80.000 + 80.000 + 85.000 + 72.000 + 68.000 + 80.000}{8}) = 84.625 となります。
この戦略では、トモアキ君の補正込みの点数の和は 87.33333... + 85.5 + 84.625 = 257.45833... 点となり、これがトモアキ君が得られる最高点です。
入力例2
2 2 2 90.000 90.000 1 80.000 2 80.000
出力例2
2 2 2 1
答えとなる出力は複数存在しますが、どれを出力しても問題ありません。
曲 1 、曲 2 共に、他の人が歌い終わった後に 1 回ずつ歌えば、それぞれ補正込みの点数は 95.000 点になります。
入力例3
4 8 9 78.245 74.123 79.254 81.111 1 69.241 2 68.000 3 81.255 4 80.582 4 80.895 3 87.433 2 100.000 1 76.365
出力例3
1 1 1 1 4 4 5 4 5 4 5 4 5 4 5 4 5 4