Round 2

肉を切らせて...。次回骨を断たれます。

250

NとKの偶奇は一致するとして、紙をNxNのグリッドに分け、中央のKxKの部分を切り抜く。これを残った部分に再帰的に適用する。最終的に指定された領域がどういう形状か答えよ、という問題。

指定される範囲が狭いので、全部について調べても間に合うよ、という問題。

600

50x50程度の盤面に3種類の文字が書かれている。任意の三点のうち、すべての文字が違うものをすべて考える。それらの中で、自分よりも大きいもので、二点を共有するものがあるものの数を答えよ、という問題。

取り敢えず50x50通りの方向でスライスしてみる。同一直線状にある二種類の文字について、出現個数と、値の取る範囲を調べておく。もう一個の文字については位置だけ覚えておくが、違う直線にあるもののうち、右側と左側の個数を覚えておく。各直線について、二種類の文字で長さが最長になり、かつ、一番遠いところからもう一種類持ってきているもの以外は、自分より大きい二点を共有するものを自明に作ることができる。

50x50通りの傾きと、50x50点すべてのチェックがボトルネックになるんじゃないかなぁ。うまいことメモリ使うけれど。

900

見てない。