시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 | 512 MB | 8 | 8 | 6 | 100.000% |
太郎君は小学生で、チラシの裏に落書きをしています。 ある時、太郎君は次のゲームを思いつきました。
太郎君はこのゲームを思いつきましたが、太郎君はこのゲームをクリアするのに大変時間がかかってしまいます。そこで、大学生であるあなたに助けを求めました。 太郎君の兄であり大学生であるあなたの仕事は以下の通りです。 厳密な状況を考えるために、あるマス目に丸印を書き込むコスト、あるマス目にある丸印を消すコストをあなたは導き出しました。このコストを用いてこのゲームをクリアするためにかかる操作のコストを最小化するような手順を考える。 このとき、最小のコストおよびそのコストを達成するような手順を出力するプログラムを書いてください。 出力については、最小コストを達成する手順なら、どのような操作、順番でも出力してもよいものとする。
n W11 W12 .. W1n W21 W22 .. W2n .. Wn1 Wn2 .. Wnn E11 E12 .. E1n E21 E22 .. E2n .. En1 En2 .. Enn F1(n文字) F2(n文字) .. Fn(n文字)
mincost cnt R1 C1 operate1 R2 C2 operate2 .. Rcnt Ccnt operatecnt
3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 o.o ... .o.
2 2 1 3 erase 2 3 write
上から1番目、左から3番目のマス目の丸印を消去し、 上から2番目、左から3番目のマス目に丸印を書き加えれば目標は達成できる。 このときコストは2のみしかかからず、これが最小のコストである。
4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 oooo oooo oooo oooo
30 12 1 1 erase 1 2 erase 1 3 erase 2 1 erase 2 2 erase 2 4 erase 3 1 erase 3 3 erase 3 4 erase 4 2 erase 4 3 erase 4 4 erase
コスト(1+2+3+4)*3だけ消去処理をすればクリアとなります。
3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 o.. .o. ..o
0 0
すでに目標は達成されているため、コスト及び操作回数はともに0となる。