http://ja.doukaku.org/user/689/Latest comments replied to yukoba(long)jaFri, 09 Jan 2009 04:40:37 -0000http://ja.doukaku.org/comment/6012/ <a href="http://ja.doukaku.org/159/">情報オリンピック2007年度国内本選問題2</a> (<a href="http://ja.doukaku.org/159/nested/">Nested</a> <a href="http://ja.doukaku.org/159/flatten/">Flatten</a>) <hr> <p>遅くなる理由として次の2点があると思います。</p> <ul class="simple"> <li>非常に繰り返し回数の多いループにおいて forを使用していること(forは無名関数 を引数に取るメソッド呼び出しの構文糖なので 遅い)</li> <li>objectのすぐ内側で変数を定義しているため、 それらがフィールドになってしまっている (フィールドの参照はローカル変数の参照に 比べて遅い)</li> </ul> <p>コードは汚くなりますが、元のコードを改造して 以下のようにすることで、自分の環境 (Athlon 64 3000+, Windows XP Professional, JDK 1.6.0)において、Javaに 移植した場合にかなり近い性能が出ることを 確認できました。ここで、</p> <ul class="simple"> <li>{ }で囲むことによって、s1やs2などをローカル 変数にすることで高速化</li> <li>組み込みのループ構文であるwhileを使うことで 高速化</li> </ul> <p>しているのがポイントです。一般的にはそれほど 気を使う必要は無いと思いますが、この問題の ようにループの回数が非常に多い場合には 有効なテクニックかと思います。</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22</pre></td><td class="code"><div class="highlight"><pre>object P2Tune extends Application { { val s1 = readLine.toArray val s2 = readLine.toArray val len = new Array[Array[int]](s1.length, s2.length) var max = 0 var i = 0 while(i &lt; s1.length) { val c1 = s1(i) var j = 0 while(j &lt; s2.length) { val prev = if(i &gt; 0 &amp;&amp; j &gt; 0) len(i-1)(j-1) else 0 len(i)(j) = if(c1 == s2(j)) prev + 1 else 0 max = Math.max(max, len(i)(j)) j += 1 } i += 1 } println(max) } } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/6012/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/6012/http://ja.doukaku.org/comment/5763/ <a href="http://ja.doukaku.org/153/">情報オリンピック2007年度世界大会「洪水」</a> (<a href="http://ja.doukaku.org/153/nested/">Nested</a> <a href="http://ja.doukaku.org/153/flatten/">Flatten</a>) <hr> プログラムの制限時間もクリアしているバージョン。 <br/>以下が擬似コードです。 <br/> <br/>------------------------------------- <br/> <br/>{まだたどっていない壁}がある <br/>&nbsp;&nbsp;[全ての壁|座標でソート済み]in{まだたどっていない壁}から最初の壁をとる。次はこの配列番号から。 <br/>&nbsp;&nbsp;左手に水:int＝頂点から右方向に壁&nbsp;なら&nbsp;1&nbsp;下方向なら&nbsp;-1 <br/>&nbsp;&nbsp;最初の壁に戻ってくるまで、壁をたどる&nbsp;(do-while) <br/>&nbsp;&nbsp;&nbsp;&nbsp;{たどった壁}に入っている&nbsp;=&gt;&nbsp;{たどった壁}から{両方水の壁}へ移動 <br/>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;{まだたどっていない壁}から{たどった壁}へ移動 <br/>&nbsp;&nbsp;&nbsp;&nbsp;次の壁の始点＝前の壁の終点 <br/>&nbsp;&nbsp;&nbsp;&nbsp;{次の壁の始点&nbsp;-&gt;&nbsp;つながっている壁|not&nbsp;in&nbsp;両方水の壁&nbsp;&amp;&amp;&nbsp;崩壊壁}から「角度」の小さい順にたどる <br/>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;角度＝外積（前の壁、次の壁）×左手に水（正負）-&gt;&nbsp;９０～３６０ <br/>&nbsp;&nbsp;{たどった壁}&nbsp;=&gt;&nbsp;{崩壊壁} <br/>{両方水の壁}を表示 <br/> <br/>------------------------------------- <br/> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154</pre></td><td class="code"><div class="highlight"><pre>package jp.yukoba.ioi2007; import scala.collection.mutable._ object Flood4 extends Application { class Base case class Point(x:int, y:int) extends Base { def &lt; (that:Point) = (y &lt; that.y || (y == that.y &amp;&amp; x &lt; that.x)) } case class Wall(no:int, from:Point, to:Point) extends Base { def &lt; (that:Wall) = (from &lt; that.from) } // 点番号 -&gt; Point val N = readInt val dotMap = Map(List.tabulate(N, i =&gt; { val line = readLine.split(&quot; &quot;).map(Integer.parseInt(_)) (i+1, Point(line(0), line(1))) }):_*) // 壁番号 -&gt; Wall val W = readInt val wallMap = Map(List.tabulate(W, i =&gt; { val ary = readLine.split(&quot; &quot;).map(Integer.parseInt(_)) // 左上に近いのを from に設定 val p1 = dotMap(ary(0)) val p2 = dotMap(ary(1)) if(p1 &lt; p2) (i+1, Wall(i+1, p1, p2)) else (i+1, Wall(i+1, p2, p1)) }):_*) // 訪れていない壁番号のセット val unvisited:Set[int] = Set(wallMap.keys.toList:_*) // ソート済みの壁の壁番号の配列 val sortAry = wallMap.keySet.toList.sort((n1, n2) =&gt; wallMap(n1) &lt; wallMap(n2)).toArray // 上のたどっていくポインタ var sortAryPos = 0 // {たどった壁} {両方水の壁} val visited = Set[int]() val bothWater = Set[int]() val brokenWall = Set[int]() // Point -&gt; Wallの配列 val point2wallAry = Map[Point, Array[(Wall,int)]]() for(pointNo &lt;- dotMap.keys) { // 頂点から出る壁は１～４つ val point = dotMap(pointNo) point2wallAry(point) = new Array[(Wall,int)](4) } for(wallNo &lt;- unvisited) { def put(p:Point, wallDir:(Wall,int)) { val ary = point2wallAry(p) for(i &lt;- 0 until (ary.length)) { if(ary(i) == null) { ary(i) = wallDir return } } error(&quot;ここにはこない&quot;) } val wall = wallMap(wallNo) put(wall.from, (wall, 1)) put(wall.to, (wall, -1)) } while(unvisited.size &gt; 0) { //println(unvisited) // [全ての壁|座標でソート済み]in{まだたどっていない壁}から最初の壁をとる。次はこの配列番号から。 def getFromSortAry():int = { while(true) { val wallNo = sortAry(sortAryPos) if(unvisited.contains(wallNo)) return wallNo sortAryPos += 1 } error(&quot;ここにはこない&quot;) } var wallNo = getFromSortAry var wall = wallMap(wallNo) // 左手に水:int＝頂点から右方向に壁 なら 1 下方向なら -1 val isLeftWater = if(wall.from.y == wall.to.y) 1 else -1 //println(&quot;isLeftWater = &quot; + isLeftWater) // 壁のたどる方向、1 = from -&gt; to、-1 = to -&gt; from var wallDir = 1 // 最初の壁に戻ってくるまで、壁をたどる (do-while) val firstWallNo = wallNo val firstWallDir = wallDir def loop() { while(true) { //println(&quot;wall = &quot; + wall + &quot;, wallDir = &quot; + wallDir) //{たどった壁}に入っている =&gt; {たどった壁}から{両方水の壁}へ移動 // else {まだたどっていない壁}から{たどった壁}へ移動 if(visited.contains(wallNo)) { visited -= wallNo bothWater += wallNo } else { unvisited -= wallNo visited += wallNo } // 次の壁の始点＝前の壁の終点 val nextStart = (if(wallDir == 1) wall.to else wall.from) // {次の壁の始点 -&gt; つながっている壁|not in 両方水の壁 &amp;&amp; 崩壊壁}から「角度」の小さい順にたどる //println(nextStart) val wallAry = point2wallAry(nextStart) var minArg = Integer.MAX_VALUE var minWallDir:(Wall,int) = null for(i &lt;- 0 until (wallAry.length)) { val nextWallDir = wallAry(i) //println(&quot;nextWallDir = &quot; + nextWallDir) if(nextWallDir != null &amp;&amp; !bothWater.contains(nextWallDir._1.no) &amp;&amp; !brokenWall.contains(nextWallDir._1.no)) { // 角度＝外積（前の壁、次の壁）×左手に水（正負）-&gt; ９０～３６０ def getArg(wall1:Wall, wallDir1:int, wall2:Wall, wallDir2:int, isLeftWater:int):int = { def toSign(p:Point):Point = Point(toSignI(p.x), toSignI(p.y)) def toSignI(i:int) = if(i&lt;0) -1 else if(i==0) 0 else 1 def toVec(wall:Wall, wallDir:int) = if(wallDir == 1) Point(wall.to.x - wall.from.x, wall.to.y - wall.from.y) else Point(wall.from.x - wall.to.x, wall.from.y - wall.to.y) val vec1 = toSign(toVec(wall1, wallDir1)) val vec2 = toSign(toVec(wall2, wallDir2)) if(vec1 == vec2) return 180 else if(vec1.x == -vec2.x &amp;&amp; vec1.y == -vec2.y) return 360 val gaiseki = (vec1.x * vec2.y - vec1.y * vec2.x) * isLeftWater if(gaiseki &lt; 0) return 90 else return 270 } val arg = getArg(wall, wallDir, nextWallDir._1, nextWallDir._2, isLeftWater) //println(&quot;arg = &quot; + arg) if(arg &lt; minArg) { minArg = arg minWallDir = nextWallDir } } } //assert(minWallDir != null) if(minWallDir == null) return // 最初の壁に戻って来たら終了 val nextWall = minWallDir._1 val nextWallDir = minWallDir._2 if(nextWall.no == firstWallNo &amp;&amp; nextWallDir == firstWallDir) return wall = nextWall wallDir = nextWallDir wallNo = wall.no } } loop() brokenWall ++= visited visited.clear } println(bothWater.size) for(wallNo &lt;- bothWater) println(wallMap(wallNo).no) //println(brokenWall.size) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5763/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5763/http://ja.doukaku.org/comment/5627/ <a href="http://ja.doukaku.org/132/">情報オリンピック2007年度国内予選問題2</a> (<a href="http://ja.doukaku.org/132/nested/">Nested</a> <a href="http://ja.doukaku.org/132/flatten/">Flatten</a>) <hr> <hr> <table><tr><td class="linenos"><pre>1 2 3 4 5 6</pre></td><td class="code"><div class="highlight"><pre><span class="nv">main</span> <span class="o">=</span> <span class="kr">do</span> <span class="nv">line</span> <span class="o">&lt;-</span> <span class="nv">getLine</span> <span class="nv">print</span> <span class="o">$</span> <span class="nv">count</span> <span class="s">&quot;JOI&quot;</span> <span class="nv">line</span> <span class="nv">print</span> <span class="o">$</span> <span class="nv">count</span> <span class="s">&quot;IOI&quot;</span> <span class="nv">line</span> <span class="nv">count</span> <span class="nv">search</span> <span class="nv">line</span> <span class="o">=</span> <span class="nv">length</span> <span class="o">$</span> <span class="nv">filter</span> <span class="p">(</span><span class="o">==</span> <span class="nv">search</span><span class="p">)</span> <span class="p">(</span><span class="nv">map</span> <span class="p">(</span><span class="o">\</span><span class="nv">i</span> <span class="o">-&gt;</span> <span class="nv">take</span> <span class="mi">3</span> <span class="o">$</span> <span class="nv">drop</span> <span class="nv">i</span> <span class="nv">line</span><span class="p">)</span> <span class="p">[</span><span class="mi">0</span> <span class="o">..</span> <span class="nv">length</span> <span class="nv">line</span> <span class="o">-</span> <span class="mi">3</span><span class="p">])</span> </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/haskell/"> Haskell </a>] [<a href="http://ja.doukaku.org/comment/5627/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5627/http://ja.doukaku.org/comment/5626/ <a href="http://ja.doukaku.org/131/">情報オリンピック2007年度国内予選問題1</a> (<a href="http://ja.doukaku.org/131/nested/">Nested</a> <a href="http://ja.doukaku.org/131/flatten/">Flatten</a>) <hr> <hr> <table><tr><td class="linenos"><pre>1 2 3 4 5 6</pre></td><td class="code"><div class="highlight"><pre><span class="nv">main</span> <span class="o">=</span> <span class="kr">do</span> <span class="nv">n</span> <span class="o">&lt;-</span> <span class="nv">readLn</span> <span class="nv">print</span> <span class="o">$</span> <span class="nv">calc</span> <span class="p">(</span><span class="mi">1000</span> <span class="o">-</span> <span class="nv">n</span><span class="p">)</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">500</span><span class="p">,</span> <span class="mi">100</span><span class="p">,</span> <span class="mi">50</span><span class="p">,</span> <span class="mi">10</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">1</span><span class="p">]</span> <span class="nv">calc</span> <span class="nv">left</span> <span class="nv">count</span> <span class="nv">coins</span> <span class="o">=</span> <span class="kr">if</span> <span class="nv">length</span> <span class="nv">coins</span> <span class="o">==</span> <span class="mi">0</span> <span class="kr">then</span> <span class="nv">count</span> <span class="kr">else</span> <span class="nv">calc</span> <span class="p">(</span><span class="nv">rem</span> <span class="nv">left</span> <span class="nv">coin</span><span class="p">)</span> <span class="p">(</span><span class="nv">count</span> <span class="o">+</span> <span class="nv">div</span> <span class="nv">left</span> <span class="nv">coin</span><span class="p">)</span> <span class="p">(</span><span class="nv">tail</span> <span class="nv">coins</span><span class="p">)</span> <span class="kr">where</span> <span class="nv">coin</span> <span class="o">=</span> <span class="nv">head</span> <span class="nv">coins</span> </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/haskell/"> Haskell </a>] [<a href="http://ja.doukaku.org/comment/5626/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5626/http://ja.doukaku.org/comment/5624/ <a href="http://ja.doukaku.org/134/">情報オリンピック2007年度国内予選問題4</a> (<a href="http://ja.doukaku.org/134/nested/">Nested</a> <a href="http://ja.doukaku.org/134/flatten/">Flatten</a>) <hr> <p>Scala -&gt; Haskell 移植</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17</pre></td><td class="code"><div class="highlight"><pre><span class="kr">import</span> <span class="nv">qualified</span> <span class="n">Data</span><span class="o">.</span><span class="n">Set</span> <span class="nv">as</span> <span class="n">Set</span> <span class="nv">main</span> <span class="o">=</span> <span class="kr">do</span> <span class="nv">m</span> <span class="o">&lt;-</span> <span class="nv">readLn</span> <span class="nv">lines1</span> <span class="o">&lt;-</span> <span class="nv">sequence</span> <span class="o">$</span> <span class="nv">replicate</span> <span class="nv">m</span> <span class="nv">getLine</span> <span class="kr">let</span> <span class="nv">seiza</span> <span class="o">=</span> <span class="nv">map</span> <span class="nv">splitAtSpace</span> <span class="nv">lines1</span> <span class="nv">n</span> <span class="o">&lt;-</span> <span class="nv">readLn</span> <span class="nv">lines2</span> <span class="o">&lt;-</span> <span class="nv">sequence</span> <span class="o">$</span> <span class="nv">replicate</span> <span class="nv">n</span> <span class="nv">getLine</span> <span class="kr">let</span> <span class="nv">stars</span> <span class="o">=</span> <span class="n">Set</span><span class="o">.</span><span class="nv">fromList</span> <span class="o">$</span> <span class="nv">map</span> <span class="nv">splitAtSpace</span> <span class="nv">lines2</span> <span class="kr">let</span> <span class="nv">diffs</span> <span class="o">=</span> <span class="n">Set</span><span class="o">.</span><span class="nv">map</span> <span class="p">(</span><span class="o">\</span><span class="nv">s1</span> <span class="o">-&gt;</span> <span class="nv">minus</span> <span class="nv">s1</span> <span class="p">(</span><span class="nv">seiza</span> <span class="o">!!</span> <span class="mi">0</span><span class="p">))</span> <span class="nv">stars</span> <span class="kr">let</span> <span class="nv">d</span> <span class="o">=</span> <span class="n">Set</span><span class="o">.</span><span class="nv">toList</span><span class="p">(</span><span class="n">Set</span><span class="o">.</span><span class="nv">filter</span> <span class="p">(</span><span class="o">\</span><span class="nv">diff</span> <span class="o">-&gt;</span> <span class="nv">all</span> <span class="p">(</span><span class="o">\</span><span class="nv">s2</span> <span class="o">-&gt;</span> <span class="n">Set</span><span class="o">.</span><span class="nv">member</span> <span class="p">(</span><span class="nv">plus</span> <span class="nv">s2</span> <span class="nv">diff</span><span class="p">)</span> <span class="nv">stars</span><span class="p">)</span> <span class="nv">seiza</span><span class="p">)</span> <span class="nv">diffs</span><span class="p">)</span> <span class="o">!!</span> <span class="mi">0</span> <span class="nv">putStrLn</span> <span class="o">$</span> <span class="nv">show</span><span class="p">(</span><span class="nv">fst</span><span class="p">(</span><span class="nv">d</span><span class="p">))</span> <span class="o">++</span> <span class="s">&quot; &quot;</span> <span class="o">++</span> <span class="nv">show</span><span class="p">(</span><span class="nv">snd</span><span class="p">(</span><span class="nv">d</span><span class="p">))</span> <span class="nv">splitAtSpace</span> <span class="nv">s</span> <span class="o">=</span> <span class="p">(</span><span class="nv">read</span> <span class="o">$</span> <span class="nv">take</span> <span class="nv">p</span> <span class="nv">s</span><span class="p">,</span> <span class="nv">read</span> <span class="o">$</span> <span class="nv">drop</span> <span class="p">(</span><span class="nv">p</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="nv">s</span><span class="p">)</span> <span class="kr">where</span> <span class="nv">p</span> <span class="o">=</span> <span class="nv">length</span> <span class="o">$</span> <span class="nv">takeWhile</span> <span class="p">(</span><span class="o">/=</span> <span class="sc">&#39; &#39;</span><span class="p">)</span> <span class="nv">s</span> <span class="nv">plus</span> <span class="nv">a</span> <span class="nv">b</span> <span class="o">=</span> <span class="p">(</span><span class="nv">fst</span><span class="p">(</span><span class="nv">a</span><span class="p">)</span> <span class="o">+</span> <span class="nv">fst</span><span class="p">(</span><span class="nv">b</span><span class="p">),</span> <span class="nv">snd</span><span class="p">(</span><span class="nv">a</span><span class="p">)</span> <span class="o">+</span> <span class="nv">snd</span><span class="p">(</span><span class="nv">b</span><span class="p">))</span> <span class="nv">minus</span> <span class="nv">a</span> <span class="nv">b</span> <span class="o">=</span> <span class="p">(</span><span class="nv">fst</span><span class="p">(</span><span class="nv">a</span><span class="p">)</span> <span class="o">-</span> <span class="nv">fst</span><span class="p">(</span><span class="nv">b</span><span class="p">),</span> <span class="nv">snd</span><span class="p">(</span><span class="nv">a</span><span class="p">)</span> <span class="o">-</span> <span class="nv">snd</span><span class="p">(</span><span class="nv">b</span><span class="p">))</span> </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/haskell/"> Haskell </a>] [<a href="http://ja.doukaku.org/comment/5624/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5624/http://ja.doukaku.org/comment/5610/ <a href="http://ja.doukaku.org/134/">情報オリンピック2007年度国内予選問題4</a> (<a href="http://ja.doukaku.org/134/nested/">Nested</a> <a href="http://ja.doukaku.org/134/flatten/">Flatten</a>) <hr> <p>こうすると再帰が無くなるのか。</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13</pre></td><td class="code"><div class="highlight"><pre>object JOI4 extends Application { val m = readInt val seiza = List.tabulate(m, i =&gt; readLine.split(&quot; &quot;).map(Integer.parseInt(_)).toList).toArray val n = readInt val stars = Set(List.tabulate(n, i =&gt; readLine.split(&quot; &quot;).map(Integer.parseInt(_)).toList): _*) val diff = stars.map(minus(_, seiza(0))). find(diff =&gt; seiza.forall(s2 =&gt; stars.contains(plus(s2, diff)))).get println(diff(0) + &quot; &quot; + diff(1)) def plus(a:List[int], b:List[int]) = List(a(0) + b(0), a(1) + b(1)) def minus(a:List[int], b:List[int]) = List(a(0) - b(0), a(1) - b(1)) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5610/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5610/http://ja.doukaku.org/comment/5609/ <a href="http://ja.doukaku.org/134/">情報オリンピック2007年度国内予選問題4</a> (<a href="http://ja.doukaku.org/134/nested/">Nested</a> <a href="http://ja.doukaku.org/134/flatten/">Flatten</a>) <hr> <p>Setを使って楽してみました。</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18</pre></td><td class="code"><div class="highlight"><pre>object JOI4 extends Application { val m = readInt val seiza = List.tabulate(m, i =&gt; readLine.split(&quot; &quot;).map(Integer.parseInt(_)).toList).toArray val n = readInt val stars = Set(List.tabulate(n, i =&gt; readLine.split(&quot; &quot;).map(Integer.parseInt(_)).toList): _*) def calc() { for(s1 &lt;- stars) { val diff = minus(s1, seiza(0)) if(seiza.forall(s2 =&gt; stars.contains(plus(s2, diff)))) return println(diff(0) + &quot; &quot; + diff(1)) } } calc def plus(a:List[int], b:List[int]) = List(a(0) + b(0), a(1) + b(1)) def minus(a:List[int], b:List[int]) = List(a(0) - b(0), a(1) - b(1)) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5609/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5609/http://ja.doukaku.org/comment/5603/ <a href="http://ja.doukaku.org/145/">情報オリンピック2006年度国内本選問題3</a> (<a href="http://ja.doukaku.org/145/nested/">Nested</a> <a href="http://ja.doukaku.org/145/flatten/">Flatten</a>) <hr> <p>コードを読みやすくしただけ。</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34</pre></td><td class="code"><div class="highlight"><pre>object Hon3 extends Application { val n = readInt val stars = List.tabulate(n, i =&gt; { val list = readLine.split(&quot; &quot;).map(Integer.parseInt(_)) (list(0), list(1)) }).toArray val map = new Array[boolean](5001 * 5001) stars.foreach(p =&gt; map(p._2 * 5001 + p._1) = true) def calc(i1:int, maxArea:int):int = { if(i1 == n) return maxArea def calc2(i1:int, i2:int, maxArea:int):int = { if(i2 == n) return maxArea val p1 = stars(i1); val p2 = stars(i2) if(hasTwoMore(p1, p2, 1) || hasTwoMore(p1, p2, -1)) return calc2(i1, i2 + 1, Math.max(maxArea, calcArea(p1, p2))) return calc2(i1, i2 + 1, maxArea) } return calc(i1 + 1, calc2(i1, i1 + 1, maxArea)) } def hasStarAtMap(p:(int,int)) = p._1 &gt;= 0 &amp;&amp; p._1 &lt;= 5000 &amp;&amp; p._2 &gt;= 0 &amp;&amp; p._2 &lt;= 5000 &amp;&amp; map(p._2 * 5001 + p._1) // d == 1 なら右方向回転、 d == -1 なら左方向回転 def hasTwoMore(p1:(int,int), p2:(int,int), d:int):boolean = { val p3 = (p2._1 + d * (p2._2 - p1._2), p2._2 - d * (p2._1 - p1._1)) val p4 = (p3._1 + d * (p3._2 - p2._2), p3._2 - d * (p3._1 - p2._1)) return hasStarAtMap(p3) &amp;&amp; hasStarAtMap(p4) } // 面積の計算 def calcArea(p1:(int,int), p2:(int,int)) = (p1._1 - p2._1) * (p1._1 - p2._1) + (p1._2 - p2._2) * (p1._2 - p2._2) println(calc(0, 0)) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5603/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5603/http://ja.doukaku.org/comment/5577/ <a href="http://ja.doukaku.org/143/">情報オリンピック2006年度国内本選問題1</a> (<a href="http://ja.doukaku.org/143/nested/">Nested</a> <a href="http://ja.doukaku.org/143/flatten/">Flatten</a>) <hr> <p>こうやって書くと var をなくせるんですね。</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16</pre></td><td class="code"><div class="highlight"><pre>object Hon1 extends Application { //Console.setIn(new java.io.FileReader(&quot;input.txt&quot;)) val ary = Console.readLine().split(&quot; &quot;) val n = Integer.parseInt(ary(0)) val k = Integer.parseInt(ary(1)) val a = List.tabulate(n, i =&gt; Console.readInt).toArray val firstSum = a.take(k).reduceLeft((i:int,j:int) =&gt; i + j) def calc(i:int, prevSum:int, maxSum:int):int = { if(i == n) return maxSum val curSum = prevSum - a(i - k) + a(i) return calc(i + 1, curSum, Math.max(maxSum, curSum)) } println(calc(k, firstSum, firstSum)) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5577/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5577/http://ja.doukaku.org/comment/5571/ <a href="http://ja.doukaku.org/143/">情報オリンピック2006年度国内本選問題1</a> (<a href="http://ja.doukaku.org/143/nested/">Nested</a> <a href="http://ja.doukaku.org/143/flatten/">Flatten</a>) <hr> <p>入出力は標準入出力にて。</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18</pre></td><td class="code"><div class="highlight"><pre>object Hon1 extends Application { //Console.setIn(new java.io.FileReader(&quot;input.txt&quot;)) val ary = Console.readLine().split(&quot; &quot;) val n = Integer.parseInt(ary(0)) val k = Integer.parseInt(ary(1)) val a = List.tabulate(n, i =&gt; Console.readInt).toArray var firstSum = 0 a.take(k).foreach(v =&gt; firstSum += v) def calc(i:int, prevSum:int, maxSum:int):int = { if(i == n) return maxSum val curSum = prevSum - a(i - k) + a(i) return calc(i + 1, curSum, Math.max(maxSum, curSum)) } println(calc(k, firstSum, firstSum)) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5571/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5571/http://ja.doukaku.org/comment/5565/ <a href="http://ja.doukaku.org/133/">情報オリンピック2007年度国内予選問題3</a> (<a href="http://ja.doukaku.org/133/nested/">Nested</a> <a href="http://ja.doukaku.org/133/flatten/">Flatten</a>) <hr> <p>コードの行数は増えても、相互再帰を使った方が、わかりやすくなると思い、書いてみました。</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25</pre></td><td class="code"><div class="highlight"><pre>object JOI3 extends Application { val n = Console.readInt val taro = List.tabulate(n, i =&gt; Console.readInt).sort((i,j) =&gt; i &lt; j) val hanako = List.range(1, n*2 + 1).filter(i =&gt; !taro.contains(i)) type Cards = List[int] def taroPuts(taro:Cards, hanako:Cards, p:int):List[int] = { if(hanako.length == 0) return List(0, taro.length); val result = putsCard(taro, p) return hanakoPuts(result._1, hanako, result._2) } def hanakoPuts(taro:Cards, hanako:Cards, p:int):List[int] = { if(taro.length == 0) return List(hanako.length, 0); val result = putsCard(hanako, p) return taroPuts(taro, result._1, result._2) } def putsCard(list:Cards, p:int):(Cards,int) = { val spanList = list.span(i =&gt; i &lt;= p) if(spanList._2.length == 0) return (list, 0) else return (spanList._1 ::: spanList._2.tail, spanList._2.head) } taroPuts(taro, hanako, 0).foreach(x =&gt; println(x)) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5565/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5565/http://ja.doukaku.org/comment/5533/ <a href="http://ja.doukaku.org/135/">情報オリンピック2007年度国内予選問題5</a> (<a href="http://ja.doukaku.org/135/nested/">Nested</a> <a href="http://ja.doukaku.org/135/flatten/">Flatten</a>) <hr> <p>末尾再帰になるように変換。これで、テストデータ4以降も正常に処理できます。</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24</pre></td><td class="code"><div class="highlight"><pre>import java.lang._ object JOI5 extends Application { val ary = Console.readLine().split(&quot; &quot;) val r = Integer.parseInt(ary(0)) val c = Integer.parseInt(ary(1)) val map = List.tabulate(r, (y) =&gt; { val line = Console.readLine().split(&quot; &quot;) List.tabulate(c, (x) =&gt; line(x) == &quot;1&quot;).toArray }).toArray def countMax(i:int, maxCount:int):int = { if(i == 2 &lt;&lt; r) return maxCount def countX(x:int, xSum:int):int = { if(x == c) return xSum def countY(y:int, ySum:int):int = { if(y == r) return ySum return countY(y + 1, ySum + (if((i &amp; (2 &lt;&lt; y)) == 0 ^ map(y)(x)) 1 else 0)) } val ycount = countY(0, 0) return countX(x + 1, xSum + Math.max(ycount, r - ycount)) } return countMax(i + 1, Math.max(countX(0, 0), maxCount)) } println(countMax(0, 0)) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5533/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5533/http://ja.doukaku.org/comment/5532/ <a href="http://ja.doukaku.org/135/">情報オリンピック2007年度国内予選問題5</a> (<a href="http://ja.doukaku.org/135/nested/">Nested</a> <a href="http://ja.doukaku.org/135/flatten/">Flatten</a>) <hr> <p>val を無くしてみましたが、テストデータ４以降がスタックオーバーフローします。</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24</pre></td><td class="code"><div class="highlight"><pre>import java.lang._ object JOI5 extends Application { val ary = Console.readLine().split(&quot; &quot;) val r = Integer.parseInt(ary(0)) val c = Integer.parseInt(ary(1)) val map = List.tabulate(r, (y) =&gt; { val line = Console.readLine().split(&quot; &quot;) List.tabulate(c, (x) =&gt; line(x) == &quot;1&quot;).toArray }).toArray def countMax(i:int):int = { if(i == 2 &lt;&lt; r) return 0 def countX(x:int):int = { if(x == c) return 0 def countY(y:int):int = { if(y == r) return 0 return (if((i &amp; (2 &lt;&lt; y)) == 0 ^ map(y)(x)) 1 else 0) + countY(y + 1) } val ycount = countY(0) return Math.max(ycount, r - ycount) + countX(x + 1) } return Math.max(countX(0), countMax(i + 1)) } println(countMax(0)) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5532/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5532/http://ja.doukaku.org/comment/5531/ <a href="http://ja.doukaku.org/134/">情報オリンピック2007年度国内予選問題4</a> (<a href="http://ja.doukaku.org/134/nested/">Nested</a> <a href="http://ja.doukaku.org/134/flatten/">Flatten</a>) <hr> <p>問題番号間違えた orz</p> <hr> http://ja.doukaku.org/comment/5531/http://ja.doukaku.org/comment/5530/ <a href="http://ja.doukaku.org/134/">情報オリンピック2007年度国内予選問題4</a> (<a href="http://ja.doukaku.org/134/nested/">Nested</a> <a href="http://ja.doukaku.org/134/flatten/">Flatten</a>) <hr> <p>val のみにしてみましたが、テストデータ４以降がスタックオーバーフローします。</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24</pre></td><td class="code"><div class="highlight"><pre>import java.lang._ object JOI5 extends Application { val ary = Console.readLine().split(&quot; &quot;) val r = Integer.parseInt(ary(0)) val c = Integer.parseInt(ary(1)) val map = List.tabulate(r, (y) =&gt; { val line = Console.readLine().split(&quot; &quot;) List.tabulate(c, (x) =&gt; line(x) == &quot;1&quot;).toArray }).toArray def countMax(i:int):int = { if(i == 2 &lt;&lt; r) return 0 def countX(x:int):int = { if(x == c) return 0 def countY(y:int):int = { if(y == r) return 0 return (if((i &amp; (2 &lt;&lt; y)) == 0 ^ map(y)(x)) 1 else 0) + countY(y + 1) } val ycount = countY(0) return Math.max(ycount, r - ycount) + countX(x + 1) } return Math.max(countX(0), countMax(i + 1)) } println(countMax(0)) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5530/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5530/http://ja.doukaku.org/comment/5529/ <a href="http://ja.doukaku.org/133/">情報オリンピック2007年度国内予選問題3</a> (<a href="http://ja.doukaku.org/133/nested/">Nested</a> <a href="http://ja.doukaku.org/133/flatten/">Flatten</a>) <hr> <p>var と mutable を無くしました。</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17</pre></td><td class="code"><div class="highlight"><pre>object JOI3 extends Application { val n = Console.readInt val taro = List.tabulate(n, i =&gt; Console.readInt).sort((i,j) =&gt; i &lt; j) val hanako = List.range(1, n*2 + 1).filter(i =&gt; !taro.contains(i)) def game(list1:List[int], list2:List[int], isList1Taro:boolean, p:int):String = { if(list1.length == 0 || list2.length == 0) return if(isList1Taro) list2.length + &quot;\n&quot; + list1.length else list1.length + &quot;\n&quot; + list2.length val spanList = list1.span(i =&gt; i &lt;= p) if(spanList._2.length == 0) return game(list2, list1, !isList1Taro, 0) else return game(list2, spanList._1 ::: spanList._2.tail, !isList1Taro, spanList._2.head) } println(game(taro, hanako, true, 0)) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5529/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5529/http://ja.doukaku.org/comment/5528/ <a href="http://ja.doukaku.org/132/">情報オリンピック2007年度国内予選問題2</a> (<a href="http://ja.doukaku.org/132/nested/">Nested</a> <a href="http://ja.doukaku.org/132/flatten/">Flatten</a>) <hr> <p>var を無くしました。</p> <hr> <table><tr><td class="linenos"><pre>1 2 3 4 5 6 7</pre></td><td class="code"><div class="highlight"><pre>object JOI2 extends Application { val line = Console.readLine def count(search:String) = List.tabulate(line.length - 2, i =&gt; line.substring(i, i+3)). filter(s =&gt; s == search).length; List(&quot;JOI&quot;, &quot;IOI&quot;).foreach(x =&gt; println(count(x))) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5528/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5528/http://ja.doukaku.org/comment/5515/ <a href="http://ja.doukaku.org/135/">情報オリンピック2007年度国内予選問題5</a> (<a href="http://ja.doukaku.org/135/nested/">Nested</a> <a href="http://ja.doukaku.org/135/flatten/">Flatten</a>) <hr> <p>flip いらないので除去。どう考えても手続き型言語の記法で書いていますね。</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22</pre></td><td class="code"><div class="highlight"><pre>import java.lang._ object JOI5 extends Application { val ary = Console.readLine().split(&quot; &quot;) val r = Integer.parseInt(ary(0)) val c = Integer.parseInt(ary(1)) val map = List.tabulate(r, (y) =&gt; { val line = List.fromArray(Console.readLine().split(&quot; &quot;)) List.tabulate(c, (x) =&gt; line(x) == &quot;1&quot;).toArray }).toArray var maxCount = 0 for(i &lt;- List.range(0, 2 &lt;&lt; r)) { var count = 0 for(x &lt;- List.range(0, c)) { var ycount = 0 for(y &lt;- List.range(0, r)) if((i &amp; (2 &lt;&lt; y)) == 0 ^ map(y)(x)) ycount = ycount + 1 count += Math.max(ycount, r - ycount) } maxCount = Math.max(count, maxCount) } println(maxCount) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5515/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5515/http://ja.doukaku.org/comment/5496/ <a href="http://ja.doukaku.org/134/">情報オリンピック2007年度国内予選問題4</a> (<a href="http://ja.doukaku.org/134/nested/">Nested</a> <a href="http://ja.doukaku.org/134/flatten/">Flatten</a>) <hr> <p>より、Scalaぽく修正。</p> <hr> <table><tr><td class="linenos"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39</pre></td><td class="code"><div class="highlight"><pre>import java.lang._ object JOI4 extends Application { val m = Console.readInt val seiza = List.tabulate(m, (i) =&gt; { val line = Console.readLine().split(&quot; &quot;) (Integer.parseInt(line(0)), Integer.parseInt(line(1))) }).sort(prev).toArray val n = Console.readInt val stars = List.tabulate(n, (i) =&gt; { val line = Console.readLine().split(&quot; &quot;) (Integer.parseInt(line(0)), Integer.parseInt(line(1))) }).sort(prev).toArray def find():(int,int) = { for(i &lt;- List.range(0, n - m)) { val diff = minus(stars(i), seiza(0)) def isMatch(diff:(int,int)):boolean = { var pos = -1 for(j &lt;- List.range(0, m)) { def search(pos:int):int = { for(k &lt;- List.range(pos, n) if(stars(k) == plus(seiza(j), diff))) return k return -1 } pos = search(pos + 1) if(pos == -1) return false } return true } if(isMatch(diff)) return diff } error(&quot;Cannot find seiza&quot;) } val diff = find() println(diff._1 + &quot; &quot; + diff._2) def prev(a:(int,int), b:(int,int)) = if(a._2 == b._2) a._1 &lt; b._1 else a._2 &lt; b._2 def plus(a:(int,int), b:(int,int)) = (a._1 + b._1, a._2 + b._2) def minus(a:(int,int), b:(int,int)) = (a._1 - b._1, a._2 - b._2) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5496/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5496/http://ja.doukaku.org/comment/5495/ <a href="http://ja.doukaku.org/131/">情報オリンピック2007年度国内予選問題1</a> (<a href="http://ja.doukaku.org/131/nested/">Nested</a> <a href="http://ja.doukaku.org/131/flatten/">Flatten</a>) <hr> <p>入力を標準入力からに修正。</p> <hr> <table><tr><td class="linenos"><pre>1 2 3 4 5 6 7 8 9</pre></td><td class="code"><div class="highlight"><pre>object JOI1 extends Application { var sum = 1000 - Console.readInt var count = 0; for(c &lt;- Array(500, 100, 50, 10, 5, 1)) { count += sum / c sum %= c } println(count) } </pre></div> </td></tr></table> <div align = "right" style="margin-right: 1em;"> [<a href="http://ja.doukaku.org/lang/scala/"> Scala </a>] [<a href="http://ja.doukaku.org/comment/5495/download/"> download code </a>] </a>] </div> <hr> http://ja.doukaku.org/comment/5495/