解いた問題のソースコードと解説など。


貪欲

POJ 2782 Bin Packing

問題 アイテムがN個あり、それぞれの重さが与えられる。これらのアイテムをビンに詰めたいとする。一つのビンにたいして最大で2個までのアイテムを詰められる。このとき必要な最小のビンの数を求めよ。ただし一つのビンに詰めるアイテムの重さの和がLより大…

POJ 1505 Copying Books

問題 要素数mの数列をk個の連続する数列に分割する。分割したそれぞれの数列の要素の和を計算し、そのうち最大となる値を最小化するように数列を分割したい。この条件をみたすように数列を分割して出力せよ。ただし複数の分割方法がある場合には、分割したは…

POJ 2437 Muddy roads

問題 一直線の道路上にN個のぬかるみがありそれが[s,e)の形で与えられる(s,eは非負整数)。なお与えられる範囲に重複はない。長さKの木板が無数にあり、これらを使ってぬかるみをすべて覆いたい。最小でいくつの木板が必要か。 やりかた 貪欲。 領域の左端…

SRM 329 Div1 Medium LogCutter

問題 長さLの丸太がある。この丸太はK箇所で切断でき、位置はであたえられる。この丸太を最大C箇所で切断できるとした時に、もっとも長い丸太を最小化せよ。返す値は最小化した値と最初に切断する位置とせよ。最初の切断位置が複数取れる場合は最も小さい値…

SRM 348 Div1 Medium RailwayTickets

問題 (意訳)数直線上に線分が幾つか与えられる。任意の地点で重複する線分はseats以下にしたい。取り除かねばならない線分の最小の数を求めよ。ただし線分の端点は重複と数えない。 問題 線分の右端でソートして貪欲。 ソートした上で数直線上を最初から見…

SRM 331 Div1 Medium Shopping

問題 コインが複数種類あり、それらの金額が与えられる。各金額のコインは無尽蔵にあるとする。1~Xまでのすべての金額を支払えるようにコインを選ぶとき、このコインの枚数を最小化せよ。 やりかた 公式解説を参考にしました。 ある時点で選んだコインの総…

SRM 316 Div1 Medium PlacingPieces

問題 直線の棒がいくつか与えられ、それらの長さはpieces[]である。この棒からいくつか選んで長さL上の板の上に、はみ出ないように、かつ区間が互いに重ならないように置いていく。棒を置いていない区間に残りの棒が1つも置けないようになったら終了とする…

SRM 573 Div1 Easy TeamContest

問題 3*Nの要素を持つ配列strengthが与えられる。この要素を3つずつN個のグループに分ける。最初の3つの要素をまとめたものがあなたの所属するグループである。グループの強さはグループのstrengthがx,y,zだとすると max(x,y,z) + min(x,y,z) で決まる。残り…

SRM 568 Div1 Easy BallsSeparating

問題 箱がN個あり、i番目の箱には赤色のボールがred[i]個、緑色のボールがgreen[i]個、青色のボールがblue[i]個入っている。すべての箱に対して、それぞれの箱に入っているボールの色数が必ず1色以下になるようにボールを他の箱に移動したい。動かす最小の…

SRM 512 Div2 Hard DoubleRoshambo

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11289&rd=14537 AとBが両手でじゃんけんをする。1.Aの右手がBの左手に勝ち、Aの右手もBの右手に勝つときAに2点入る 2.Aの右手がBの左手に勝ち、Aの右手がBの右手と引き分けるときAに1点入る 3.そ…

SRM 499 Div2 Hard PalindromeGame

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11331&rd=14428vector string が与えられる。各文字列の長さは等しい。各文字列には点数が割り当てられており、この文字列から複数を取り出してそれらを任意の順で結合した文字列がもし回文とな…

SRM 481 Div2 Hard BatchSystem

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10808&rd=14234バッチシステムであるジョブiをこなすのに必要な時間duration[i]とこの仕事をおこなう者の名前user[i]が与えられる。user[i]が与えられた仕事を終えるまでに待たねばならない時間…

SRM 480 Div2 Hard SignalIntelligence

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11059&rd=14159vector int numbersが与えられ、ここからある文字列を作る。numbers[i]を文字列に組み込むとは、文字列の2のべき乗番目から連続してnumbers[i]個の1を組み込むという行為になる。…

SRM 470 Div2 Hard ActivateGame

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10750&rd=14153数字が書かれたvector stringが与えられる。はじめは左上のみがアクチベートされている。毎ターンアクティブなセルとそれに隣接するアクティブでないセルをひとつずつ選んで、そこ…

SRM 463 Div2 Hard Nisoku

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10760&rd=14148N枚のカードがあり、各カードには1.5から10.0までの数字が書かれている。このうちから2枚選んで取り出してカードに書いてある数字を足した数かかけた数を新しいカードに書いてその…

SRM 415 Div1 easy ShipLoading

持ち上げられるクレーンの重さでソートし、荷物を持ち上げることのできるクレーンで使用回数(秒数)がもっとも少ないものに順繰りに荷物を割り振っていく。最終的にもっとも使用したクレーンの回数が答え。 int minimumTime(vector <int> cranes, vector <string> boxes)</string></int>…

POJ 2287 Tian Ji -- The Horse Racing

問題文長さnの数列が2つ与えられる(a,bとする)。この2つの数列の数字同士を全てカップリングさせてaの方の数字が大きれば+200点。bの方が大きければ-200点。得点を最大化せよ、という問題。DP強化週間のつもりが貪欲。=の時をうまく扱えずに人の答えを見て…

POJ 2181 Jumping Cows

問題文長さPの数列が与えられて偶数秒にはその数列から数字を選んで足す、奇数秒には選んで引く。これを0秒から始める。i+1秒で選ぶ数字はi秒で選んだ数字より数列中で後のものでなくてはならない。最大和を求めよ、という問題。DP強化週間のつもりが、たん…

Get up! 明日のSUPER ST@R!