prithivMLmods/Coder-Stat

1<h1>団子職人(Dango Maker)</h1>2 3<p>4  あなたは団子を作る職人である．今，あなたは団子に串を刺そうとしているところである．5</p>6 7<p>8  団子は，縦<var>N</var> 行，横<var>M</var> 列に仕切られたマスの中に配置されている．各マスには団子が1 個ずつ入っている．それぞれの団子には，赤(R)，緑(G)， 白(W) のいずれかの色が付いている．あなたは，左から右の方向，または，上から下の方向に連続する3 マスから団子を取り出し，この順に1 本の串にちょうど3個刺すことができる．9</p>10 11<p>12  今あなたは，赤，緑，白の団子が1 個ずつこの順に刺さった串を可能な限り多く作りたい．串に刺す順番は，マスから取り出した順番と同じでなければならない．また，同じ団子に2 本以上の串を刺すことはできない．13</p>14 15<p>16  あなたは，団子が刺さった串を最大何本作ることができるだろうか．17</p>18 19 20<h3>課題</h3>21 22<p>23  マスの中に配置された団子の色の情報が与えられたとき，赤，緑，白の団子が1 個ずつこの順に刺さった串が最大何本作れるかを求めるプログラムを作成せよ．24</p>25 26<h3>入力</h3>27<p>28  標準入力から以下の入力を読み込め．29</p>30 31<ul>32<li> 1 行目には，整数<var>N</var> と<var>M</var> が空白を区切りとして書かれている．</li>33<li> 続く<var>N</var> 行のうちの<var>i</var> 行目(<var>1 \leq i \leq N</var>) には，R, G, W からなる長さ<var>M</var> の文字列が書かれている．この文字列の<var>j</var> 文字目(<var>1 \leq j \leq M</var>) は，上から<var>i</var> 行目，左から<var>j</var> 列目のマスの団子の色を表す．</li>34</ul>35 36 37<h3>出力</h3>38<p>39  標準出力に，団子が刺さった串の本数の最大値を1 行で出力せよ．40</p>41 42<h3>制限</h3>43<p>44  すべての入力データは以下の条件を満たす．45</p>46<ul>47<li><var> 1 \leq N \leq 3 000．</var></li>48<li><var> 1 \leq M \leq 3 000．</var></li>49</ul>50 51<!--52小課題53小課題1 [13 点]54以下の条件を満たす．55 N ≦ 4．56 M ≦ 4．57小課題2 [20 点]58以下の条件を満たす．59 N ≦ 10．60 M ≦ 10．61小課題3 [67 点]62追加の制限はない．63  -->64 65 66<h3>入出力例</h3>67<h3>入力例1</h3>68<pre>693 470RGWR71GRGG72RGWW73</pre>74<h3>出力例1</h3>75<pre>76377</pre>78<p>79  次のように串に刺すことで，団子が刺さった串を3 本作ることができる．80</p>81<ul>82<li> 上から1 行目，左から1 列目の団子から右方向に3 個の団子を取り出し，この順に串に刺す．</li>83<li> 上から1 行目，左から4 列目の団子から下方向に3 個の団子を取り出し，この順に串に刺す．</li>84<li> 上から3 行目，左から1 列目の団子から右方向に3 個の団子を取り出し，この順に串に刺す．</li>85</ul>86 87<p>88  4 本以上の串を作ることはできないので，3 を出力する．89</p>90 91<h3>入力例2</h3>92<pre>934 494RGWR95GRRG96WGGW97WWWR98</pre>99<h3> 出力例2</h3>100<pre>1014102</pre>103<p>104  次のように串に刺すことで，団子が刺さった串を4 本作ることができる．105</p>106 107<ul>108<li> 上から1 行目，左から1 列目の団子から右方向に3 個の団子を取り出し，この順に串に刺す．</li>109<li> 上から1 行目，左から4 列目の団子から下方向に3 個の団子を取り出し，この順に串に刺す．</li>110<li> 上から2 行目，左から2 列目の団子から下方向に3 個の団子を取り出し，この順に串に刺す．</li>111<li> 上から2 行目，左から3 列目の団子から下方向に3 個の団子を取り出し，この順に串に刺す．</li>112</ul>113 114<p>115  5 本以上の串を作ることはできないので，4 を出力する．116</p>117 118<h3>入力例3</h3>119<pre>1205 5121RGRGW122GRRGW123WGGWR124RWRGW125RGWGW126</pre>127<h3> 出力例3</h3>128<pre>1296130</pre>131 132 133<br/>134<p>135  <a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/"><img alt="クリエイティブ・コモンズ・ライセンス" style="border-width:0" src="https://i.creativecommons.org/l/by-sa/4.0/80x15.png"/></a>136  <br/>137  138  <a href="https://www.ioi-jp.org/joi/2017/2018-ho/index.html">情報オリンピック日本委員会作 『第17 回日本情報オリンピック(JOI 2017/2018) 本選』</a>139</p>140 141