2012-06-01から1ヶ月間の記事一覧
問題 1からNまでの値の平均値を計算する際、ある整数Mだけを足し忘れてしまった。 間違った平均値のみわかっている場合、元のN、Mでありうるものを列挙する。既約分数とは限らない分数「X/Y」が与えられ、それぞれ1 考え方 与えられるX,Yは既約にするため、g…
問題 平面上にN+1個の点があり、i番目とi+1番目の間の距離diがN個与えられる。 1番目とN+1番目の点の距離でとりうる最大値と最小値を返す。 考え方 最大値は、一直線に並べたときが最大なので、距離の総和が答え。 最小値は、自明なものとして、N=1のときはd…
問題 N個の平面上の点が与えられる。 2つの点の距離で最大となるものを返せ。 考え方 異なる2つの点を選んで、距離最大値を保持しながら計算していく。
問題 N人で弱いと思う人に投票しあう。 もし、投票数が一番多い人が1人ならばその人が決定し終了する。 もし、そのような人が複数人いる場合、それらの人だけについて投票しなおす。投票は、あらかじめ投票する人を決めている人が何人かいて、その人たちが先…
問題 数字が書かれたカードが与えられる。 カードのうち1枚を引いて、その数字と、その数字の前後のカードがもしあればそれらを取り除く、 というのを繰り返す。 このとき、より多くのカードを引けるようにした場合、何回引けるか。 考え方 連続している数字…
問題 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日ずつ足していって、もう片方の日付になるまでカウントする。