0179 幅優先探索。 0181 想定解法ではないようだけれども、DFSで無理矢理解いた。枝刈りは「今の段目での長さが今までの最適な本棚の幅よりも長くなったら刈る」でやった。 DPだと一瞬で終わるようなので、想定解法( http://algorithms.blog55.fc2.com/blog-…

250 文字が変わる所の回数を数えるだけ。 500 i番目がAliceだったときどちらが勝つかを保持するdp[i]を考える。n=layout.size()。 (n-1)番目でAliceなら全部取ってAliceの勝ち。 (n-2)番目でAliceの場合、layout[n-2]==1なら取らないといけないのでBobの勝ち…

久しぶりの参加。

問題 飛行機のキャビンアテンダントさんがお客さんにコーヒーかお茶を配る。最短で配る時かかる時間を答える。 考え方 たぶん数え上げるだけ。最短時間と書かれているけど、まず、 ・必ず全ての人にコーヒーまたはお茶を入れる=4*n ・必ず全ての人の所へ行く…

0177 球上の2点間の距離。 //(緯度(北+,南-),経度(東+,西-))->地点1(i1,k1)、地点2(i2,k2) double rad = sin(i1)*sin(i2)+cos(i1)*cos(i2)*cos(k1-k2);//i1,i2,k1,k2はラジアン double dist = 6378.1*acos(rad); //2点間距離

0160 モノの大きさは(x+y+h)。 0161 ソートして表示するだけ。 0162 あらかじめbool配列で1000000までハミングナンバーかどうかを計算しておいた。 iがハミングナンバーなら、i*2とi*3とi*5もハミングナンバーなので、1から計算していける。 0164 書いてある…

0168 とりあえず、dfsであらかじめ30まで計算しておいてそれを返すようにしたorz dp[i]がi段目に来るまでのパターン数だとすると、(i-1)段から1段ジャンプor(i-2)段から2段ジャンプor(i-3)段から3段ジャンプなので、dp[i]=dp[i-1]+dp[i-2]+dp[i-3]。 0169 一…

頭悪くて悲しくなってきた。

0183 全部チェックするだけ。 0185 あらかじめ2つの素数の和を全部計算しておいて、、、とかやるとTLE。 (n-primes[i])が素数かどうかをチェックして、その数を数えた。 0186 まず会津地鶏はmin{(b/c1),q2}個買える。これが0個ならNA。 あとは、残りの予算で…

グラフな難問．しゅたいなー木．

528 最初、文字列の片方のすべての部分文字列を作って、もう片方とラビンカーブでマッチングとかどうみてもTLEなコードを書いてTLE。 片方の文字列をずらしながら両方の文字列と比較して連続する文字をカウントしていった。 538 パターン文字を作ってしまう…

540 あみだくじ。あらかじめすべての横棒について、番号iの縦棒と番号jの縦棒をswapするかを計算しておいて、横棒を消さない場合の合計点数、横棒kを消した場合swapした後の合計点数をすべて調べて最小の合計点数を返した。 541 Nが大きいので、普通にシミュ…

やるだけ系。

523 やるだけ。 524 星座データの最初の点が写真のi番目の点だとし、そこを起点として写真と星座データが重なるか調べた。0.02sでメモリが872KB。ちょっと遅い。 525 「横の何行かを同時に１回裏返し，引き続き，縦の何列かを同時に１回裏返して」ということ…

209 そのまま,90度回転,180度回転,270度回転した景色を用意しておいて、全部調べる。 全部調べないと、回転したら切れ端の座標がより小さくなる場合を見逃す。 211 iさんが、距離di、速度viで走った場合、di*ki=t*vi。ただし、tはみんながそろう時間、kiはそ…

514 電源a個とモーターb個とケーブルc個の組み合わせで故障しているかどうかのデータが与えられる。 最初はすべて2の状態(壊れているかいないかわからない状態)。 故障していないデータ(r=1)の組み合わせはすべて1(正常な状態)に決まる。 故障しているデータ…

勉強になる。

203 dp。最後の行だけ動きが直線で、最後の行にジャンプ台があるときもカウント。 204 幾何。「半直線と円の交差判定」。レーザーがでる半径Rの円周上の点から無限遠点への半直線とUFOの円。 直線と円の交差判定と交差点を求めてから、半直線の始点と交差点…

200 cost,timeそれぞれでワーシャルフロイドする。ワーシャルフロイドのコードを書き写し間違えてはまった。 201 最初、アイテムの木を作って葉ノードから、、、と思ったら、そもそも木じゃない。 アイテムが合成で安く作れる場合はそのアイテムのコストをそ…

去年の夏休みもやったので、今年も８月中は問題をできるかぎり解きたい。 ということで、目標は「aoj２００問、とぷこだ過去問１００問」を目標にする。現在aojでやったのが２００問なので、４００問が目標。 とぷこだはMID,HARDを中心に１００問ぐらいは解…