A - 展開図プログラマーコンテスト

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

アンドウくんは展開図が大好きです。

今日のアンドウくんは 6 面サイコロの展開図について考えています。6 面サイコロの展開図は数パターンあります。例えば以下のようなものが考えられます。

アンドウくんは 6 面サイコロの展開図から数を作る方法を思いつきました。

展開図上の任意の数字のマスを最初に選択します。その後、その数字のマスから上下左右 4 方向の隣接するマスへ、一度通過したマスを通らないように移動していき、通過したマスの数字をならべて数を作ります。

上記の展開図からは、1235 や 326 といった数を作ることができます。

また、ほかの展開図からは、1462 や 354 といった数を作ることができます。

しかし、どんな展開図からも、121 や 123456 といった数は作ることができません。

任意に 6 面サイコロの展開図を選びこの方法で数を作ったとき、作ることができる最も大きな数はいったい何になるでしょうか。

ただし、ここでいう 6 面サイコロとは以下の条件を満たすものを指します。

  • 立方体である。
  • 1〜6 の面を 1 つずつ持つ。
  • 向かい合う面の数の和は 7 である。
  • サイコロの雌雄はどちらでもよい。つまり、1 の面を天、6 の面を地となるように置いたときに、2 の面の右に来る面は 3 でも 4 でもどちらでもよい。

入力

この問題では入力は与えられない。

出力

作ることができる最も大きな数を 1 行に出力せよ。出力の末尾に改行を入れること。

配点

この問題には部分点は設定されていない。正解した場合は、10 点が与えられる。

B - stepモード

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

アンドウくんは、 N 個のスクリプトを実行し、実行開始時刻と実行終了時刻を記録しました。
しかしこの日、アンドウくんの時計は 1000 ミリ秒巻き戻るという事象が一度発生しました。
もしかすると、スクリプトの実行時間がわからなくなってしまったかもしれません。

実行開始時刻と実行終了時刻のリストが与えられるので、各スクリプトの実行時間を計算し、ミリ秒単位で出力してください。
ただし、以下の点に注意してください。

  • 実行時間が一意に定まらないスクリプトに対しては-1を出力してください。
  • スクリプトの実行時間はいずれも 1 ミリ秒以上でした。
  • 巻き戻りは瞬間的な事象であり、巻き戻りにかかる時間は 0 ミリ秒です。
  • 実行開始時刻と実行終了時刻について丸めは起こらないものとし、実行開始時刻と実行終了時刻のミリ秒未満の位の値はすべて 0 であるとします。
    つまり、実行開始時刻および実行終了時刻をミリ秒単位で表した値 t に関して、 t は整数であることが分かっています。
  • 巻き戻りの発生時刻のミリ秒未満の値は 0 ではありません。
    つまり、巻き戻りの発生時刻をミリ秒単位で表した値 r に関して、 r は整数でないことが分かっています。
    よって、巻き戻りの発生時刻は、実行開始時刻および実行終了時刻と同時刻ではありません。
  • 夏時間はありません。

入力

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

N
S_1 E_1
:
S_N E_N
  • スクリプトの数 N ( 1 \leq{} N \leq{} 100 ) が 1 行で与えられる。
  • 続く N 行には各スクリプトの実行の開始時刻 S_i と終了時刻 E_i が空白区切りで与えられる。
  • S_i, E_i の形式は、HH:MM:SS.mmmである。ただし、 H, M, S, m は数字 1 文字を表す。
    また、 21{}\leq{}HH\leq 22, 00{}\leq{}MM\leq 59, 00{}\leq{}SS\leq 59, 000{}\leq{}mmm\leq 999 である。
  • 2 回以上巻き戻りが発生するといった、問題の条件を満たさない入力は与えられない。

出力

スクリプトの実行時間をミリ秒単位で N 行に出力せよ。

ただし、実行時間が一意に定まらないスクリプトに対しては-1を出力せよ。

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

配点

この問題には部分点が設定されていない。全てのテストケースに正解した場合は、 50 点が与えられる。

入力例1

1
21:00:01.500 21:00:01.000

出力例1

500

スクリプトの終了時刻が開始時刻より前になっているので、実行中に巻き戻りが発生したことが分かります。

入力例2

1
22:00:00.000 22:00:03.000

出力例2

-1

スクリプトの実行中に巻き戻りが発生したかどうか特定できません。

発生していた場合は 4000 ミリ秒、発生していなかった場合は 3000 ミリ秒になります。

入力例3

3
21:00:00.000 21:00:03.000
21:00:01.500 21:00:01.000
21:00:02.000 21:00:02.500

出力例3

4000
500
500

2 つ目のスクリプトから、巻き戻り前の時間軸で21:00:01.500より後、21:00:02.000より前に巻き戻ったことが分かります。

入力例4

3
21:00:00.000 21:00:03.000
21:00:01.500 21:00:01.000
21:00:00.500 21:00:01.000

出力例4

4000
500
-1

入力例3と同様に、 2 つ目のスクリプトから、巻き戻り前の時間軸で21:00:01.500より後、21:00:02.000より前に巻き戻ったことが分かります。 しかし、3つ目のスクリプトの終了時刻が、巻き戻り前の時間軸での記述なのか巻き戻った後の記述なのかの判断ができません。

C - 天下一美術館

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

天下一美術館のセト館長は、新コーナーの白黒のモザイクアートコーナーのレイアウトを決めることになりました。

見栄えを良くするためには、隣同士に並ぶ各アートは似ているものにしたいと考えています。

そこでセト館長の２つのアート同士の相違度を定義することにしました。

モザイクアートは白か黒に塗られた M \times N のマス目です。

一方のモザイクアートを他方のモザイクアートに変換する操作を考え、その操作に必要な最小のコストを相違度とします。

操作は、黒マスから白マスへの変換、白マスから黒マスへの変換、上下左右の4方向に隣り合ったマス目の交換の3種類あり、どれもコストが1かかります。

セト館長のために与えられた2つのモザイクアートの相違度を求めるプログラムを作成してください。

入力

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

M N
A_{1,1} A_{1,2} … A_{1,N}
A_{2,1} A_{2,2} … A_{2,N}
:
A_{M,1} A_{M,2} … A_{M,N}
B_{1,1} B_{1,2} … B_{1,N}
B_{2,1} B_{2,2} … B_{2,N}
:
B_{M,1} B_{M,2} … B_{M,N}
  • 1 行目には絵の縦幅 M ( 1 \leq M \leq 70 ) と、絵の横幅 N ( 1 \leq N \leq 70 ) が空白区切りで与えられる。
  • 2 行目から M 行には 1 番目のモザイクアートが与えられる。
    各行には各マスの色 A_{i,j} が空白区切りで N 個与えられる。
    1 番目のモザイクアートの i 行目 j 列目のマスが黒マスの場合は A_{i,j} = 0 であり、白マスの場合は A_{i,j} = 1 である。
  • M+2 行目から M 行には 2 番目のモザイクアートが与えられる。
    各行には各マスの色 B_{i,j} が空白区切りで N 個与えられる。
    2 番目のモザイクアートの i 行目 j 列目のマスが黒マスの場合は B_{i,j} = 0 であり、白マスの場合は B_{i,j} = 1 である。

出力

2つのモザイクアート同士の相違度を1行に出力せよ。出力の末尾に改行を入れること。

配点

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

  • N,\ M \leq{} 10を満たすテストケース全てに正解した場合は、40 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 50 点が与えられる。

入力例1

2 2
0 0
1 0
0 0
0 1

出力例1

1

下の行に対してマス目の交換を行うことにより、コスト1で変換が可能です。

入力例2

3 3
0 0 0
0 1 0
1 0 1
0 1 0
1 0 1
0 1 0

出力例2

4

白から黒への変換を1回、マス目の交換を3回行うことでコスト4で変換が可能です。

入力例3

3 4
0 0 0 0
1 1 0 0
0 0 0 0
1 1 1 0
0 1 0 0
0 0 0 0

出力例3

3

白から黒への変換を2回、マス目の交換を1回行うことでコスト3で変換が可能です。

D - ハシポン

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

ある連結なグラフについて、取り除くとグラフが非連結になるような辺のことを橋と呼びます。

また、自己辺や多重辺を含まないグラフを単純グラフと呼びます。

ワタナベくんは橋をちょうど1本含む単純グラフをハシポングラフと名づけました。

連結な無向単純グラフが与えられるので、最小で何本の辺を追加したらハシポングラフになるかを求めてください。

ただし、ハシポングラフにすることが不可能な場合はIMPOSSIBLEを出力してください。

入力

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

V E
a_1 b_1
a_2 b_2
:
a_E b_E
  • 1 行目には与えられるグラフの頂点の数 V ( 1 \leq V \leq 100,000 ) と辺の数 E ( 0 \leq E \leq 150,000 ) が空白区切りで与えられる。
  • 続く E 行には i 番目の辺がつなぐ頂点の番号 a_i と b_i ( 0 \leq{} a_i, b_i \leq{} V-1 ) が空白区切りで与えられる。
  • 与えられるグラフが連結な無向単純グラフであることは保証されている。

出力

最小の追加すべき辺の数、またはIMPOSSIBLEを1行に出力せよ。出力の末尾に改行を入れること。

配点

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

  • V \leq 20 を満たすテストケース全てに正解した場合は、35 点が与えられる。
  • V \leq 2000 を満たすテストケース全てに正解した場合は、30 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 55 点が与えられる。

入力例1

4 4
0 1
1 2
2 3
3 1

出力例1

0

与えられたグラフは既にハシポングラフです。

入力例2

5 5
0 1
1 2
2 3
3 1
3 4

出力例2

1

例えば、頂点1と頂点4をつなぐ辺を追加するとハシポングラフにすることが出来ます。

入力例3

3 2
0 1
1 2

出力例3

IMPOSSIBLE

ハシポングラフは単純グラフでなければいけません。

入力例4

1 0

出力例4

IMPOSSIBLE
E - 天下一魔法使い

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたは天下一の魔法使いになるために、魔法陣を地面に描く練習をしています。魔法陣の描き方は以下の通りです。

  • 円周上に N 個の点を等間隔に、点のうちの 1 つが真北の位置になるように描く。
  • 点を線分でつないで、K 頂点以上の自己交差のない多角形をいくつか描く。
  • 各点がちょうど 1 つの多角形に含まれるようにしなければならない。
  • 描かれた多角形がひとつながりになっていなければならない。ただし、多角形がひとつながりになっているとは、全ての多角形のペア (a, b) について、多角形 a と多角形 b が連結であるような状態を指す。また、多角形 a と多角形 b が連結であるとは、以下のいずれかの条件を満たすような状態を指す。
    • 多角形 a の辺と多角形 b の辺が 1 箇所以上で交差している。
    • 多角形 a と多角形 c が連結かつ多角形 b と多角形 c が連結であるような多角形 c が存在する。

例えば、N = 10, K = 3 のときは以下のような魔法陣を描くことができます。

fig1

以下のような魔法陣は、多角形がひとつながりになっていないため正しい魔法陣ではありません。

fig2

あなたは、このような方法で描くことができる魔法陣がいくつあるのか計算してみることにしました。

入力

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

N K
  • 1 行目に、2 つの整数 N (3 ≦ N ≦ 400), K (3 ≦ K ≦ N) が空白区切りで与えられる。

出力

問題文の方法で描くことのできる魔法陣の個数を 1,000,000,007 (10^9+7) で割った余りを 1 行に出力せよ。出力の末尾に改行を入れること。

配点

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

  • N ≦ 50 かつ N/3 < K を満たすテストケース全てに正解した場合は、30 点が与えられる。
  • N ≦ 50 を満たすテストケース全てに正解した場合は、上記とは別に 50 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 50 点が与えられる。

入力例1

6 3

出力例1

8

以下の 8 通りの魔法陣を描くことができます。

fig3

入力例2

6 4

出力例2

1

六角形を描くパターンだけが描けます。

入力例3

50 5

出力例3

665400552