J〜L 解説

SuperSonic 400x3

J-都(200〜500)

問題

・H*Wのグリッドグラフで、頂点(x,y)を始点としたハミルトン路は存在するか？

​

面積が偶数のときYes

・たて、横のどちらかが偶数のとき、輪っかが作れる

面積が偶数のときYes

・輪っかの、始める地点の隣を切れば正しいルートになる

面積が奇数のとき

・面積が偶数ならOKなことがわかった

・たてと横がどちらも奇数のときどうか？

Yesのパターン

・x+yが偶数のとき、できる

・偶数*奇数の長方形4つに分けられて

それらの長方形は輪っかが作れる

・輪っかを始点の周りで切ってつなぐと

全マスにいける

(コーナーがあるが、考えればわかるので省略)

Noのパターン

・x+yが奇数のときだけ、できない

・一マスとなりに進むと色が変わる

・黒→白→黒→...なので黒が白以上のはず

　だが、黒は白より少ないので無理

​

解法

・h*wとx+yが両方奇数だったらNo,それ以外はYes

・３問目のコードをそのまま提出する

K -救済(200〜500)

問題

H*Wのグリッドがあるので、すべての長方形の数字の和の合計を求めよ。

​

・長方形はとてもたくさんあるので、そのまま計算できない

・それぞれのマスが何回足されるか考えると簡単に解ける

​

L -樹木(400〜500)

問題概要

・N種類の樹がある

・天界では | a[ i ] - a[ j ] | ,魔界では | b[ i ] - b[ j ] | のコストで樹 i を樹 j に変更できる

・各種類の樹を1番の樹に変更するための最小コストはいくつか？

​

​

グラフ

・頂点は各樹 ... N個

・樹 i から樹 j にコスト | a[ i ] - a[ j ] | 、 | b[ i ] - b[ j ] | で行けることを辺にする ... N²個

・最短経路問題なので、Dijkstra法を使う

・各樹からDijkstraすると、O(N³logN) でTLE

改善１

・ | a[ i ] - a[ j ] | や | b[ i ] - b[ j ] | はiとjを交換しても同じ

・xから1への最短距離は、1からxへの最短距離と同じ

・頂点1だけからDijkstraすればよい

・O(N²logN) になった

改善２

・辺が各i,各jの間にあって、N²個あるのが困る

・ | a[ x ] - a[ y ] | = | a[ x ] - a[ z ] | + | a[ z ] - a[ y ] |

（a[ x ] > a[ z ] > a[ y ]のとき）

・ソートしたら、二つが隣でない限り上の表し方ができる

・ソートして隣になるものどうしだけに辺を貼ればよい

​

満点解法

・aでソートして隣り合うペアに、 | a[ i ] - a[ j ] | の辺をはる

・bでソートして隣り合うペアに、 | b[ i ] - b[ j ] | の辺をはる

・頂点1からDijkstraする

・頂点がN個、辺が2*N個くらいなので、計算量はO(NlogN)

​