Kotlin Heroes: Episode 7

　Fまで六完で、T-シャツには一問足りず。もっと早く解けないと厳しい。

　とはいえ、残り30分でGかHのどちらか解ければOK、という状況はそれほど悪くなかったともいえる。いかしたかった。

コンテストへのリンク

コンテスト後のツイート

G. Biome Map

　文章が分かりにくいけど、行列Aで(temperature, humidity)に対応するBiomeの番号が与えられている。「その差の絶対値の和が1になるBiome」のみが隣り合うことができるということなので、つまり、Aで隣りあっているものだけが出力すべき行列でも隣りあえるということ。ただし、出力すべき行列の行や列の長さは、Biomeの個数以下でなくてはならない。

　Aの中で上下左右に移動していって、全てのBiomeを尽くせば良い、ということなので、オイラーツアーをすれば良いと分かる。

　ただ、単純にオイラーツアーを一列に並べたのでは、行や列の長さの条件に反する。

　二行にして折り返して並べるのもダメ。縦に隣りあう部分が条件に違反してしまう。（コンテスト中は、これで良い気がしていました）

　なので、斜めに並べると良い。オイラーツアーの長さはBiomeの個数*2-1個なので、この構築でちょうどBiomeの個数*Biomeの個数の正方形ができあがる。

　実装で詰まったのは、

・Kotlinで再帰を書き慣れていなかった

・木でない一般グラフでも再帰一回でオイラーツアーが取れると気付かなかった（一回全域木を取らないといけない気がした）

　の二点。

　「斜めに並べる」という本質が見えてなかったのでコンテスト中にACするのは難しかっただろうけど、実装で詰まったりせず、オイラーツアーまですんなり書けていたら、思いつけたかもしれない。