問題 2次元座標平面上に格子点がN個与えられる。 その中から4点選んで、長方形を作る。ただし、各辺は軸に平行でなければいけない。 このとき、長方形内部に点を含まないような長方形で最大の面積となるものの面積を返す。 考え方 N個の点から2点(x1,y1)と(x…

問題 N個の街をつなぐM個の道の情報が与えれる。道の情報として、移動元の街、移動先の街、かかる時間が与えられる。街番号0から街番号N-1まで最短時間で移動したい。ただし、ゴールするときの時間は4か7で割り切れるようにしたい。 最短の到達時間を返す。 …

問題 7 2 3 1 5 3 のような数字の三角形が与えられる。一番上からスタートし、その地点から真下か右下に移動することができる。 一番下の段まで移動したとき、それまでの経路上の数値の合計値の最大値はいくらか。 考え方 DP。 その地点までの経路の合計値の…

問題 家の見取り図が与えられる。 部屋、壁およびスタート地点、ゴール地点、計算機のおいてある地点の情報が与えられる。 壁へは移動できない。 スタートから計算機の部屋へ寄り、ゴール地点までにかかる単位時間を答える。 部屋間の移動は1単位時間ででき…

問題 文字列がN個与えられる。その中から2つ以上選んで、任意の順番でつなげたものの中で、辞書順最小になるものを答える。 考え方 「2つ以上」となっているが、辞書順最小となるものは常に「2つつなげたもの」になるので、2つ(AとB)選んで、A+BとB+Aを候補…

問題 2012年の日付が2つ与えられる。 日付が何日離れているか答える。 考え方 早いほうの日付から1日ずつ足していって、もう片方の日付になるまでカウントする。