問題 問題概要 服を選んで、|Cx1 - Cx2| + |Cx2 - Cx3| + … + |Cxi-1 - Cxi| の最大値を求める問題。 解法 動的計画法で解ける。i日目までの服の選び方を決めたとき，i + 1日目以降について服を選んで目的の値を最大化する際には，1日目からi - 1日目までの…

問題 問題概要 回転ずしで美味しさが最大になるように寿司を取る。ただし２回連続ですしを取ることはできない。 解法 1をすしを取る、0をとらない、とすると、 1010 1001 0101 0010 のようなパターンが続くことになる。それを漸化式で表すと、 dp[i][0] = ma…

問題 問題概要 ３つの座標が与えられる。その３点を頂点とする三角形の面積を求める問題。 解法 3 点 (0,0), (a,b), (c,d) で構成される三角形の面積は、|ad−bc|⁄2という公式で求められる。この公式を用いるため、三角形の頂点の１つが原点になるように平行…

問題 問題概要 X * Y = Z2を満たすような最小のYを見つける問題。 解法 小さい約数から順番に割っていく。その時に同じ約数で何回割ったかで場合分けする。もし同じ数字で割った割った回数が偶数回のときはその数をYにかける(Yの約数として入れる)。それを繰…

問題 問題概要 計算問題。 解法 やるだけ。 ミス なし。 コード #include <iostream> #include <string> #include <algorithm> #include <functional> #include <vector> #include <bitset> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> typedef long long ll; using namespace std; #define rep(i,n) for(int i=0;i<(n…</cmath></cstring></cstdlib></cstdio></bitset></vector></functional></algorithm></string></iostream>

問題 問題概要 与えられた図形が、点Pを通るどのような直線で切ったとしても、面積を2等分する点Pが存在するかどうかを求める問題。 解法 点対称のような図形になればいい。なんて言えばいいかわからないけど、角張った円のような。(重心関して点対称であれ…

問題 問題概要 各国は世界平和を目指して、ミサイルを破棄。ただし、各国はミサイルを製造が古い順番に破棄していかなければならず、さらに、各国のミサイルの威力の合計値(軍事力)の最大値と最小値の差がd以下を常に保ちながら破棄していく必要がある。 解…

問題 問題概要 ゲームのステージがN個あり、そのステージすべてをクリアするためのステージの並べ方の場合の数を求め問題。ただし、(k個目のステージの難易度) >= (k-1個目のステージの難易度) - Tでだければならない。 解法 ステージの難易度を昇順にソート…

問題 問題概要 条件に合う最もよいピザを選ぶ 解法 この問題は貪欲法で解ける。なぜなら、トッピングの値段がすべて同じだからである。トッピングの値段が同じであるなら、トッピングのカロリーが高いものから優先的に選んでいけばいい。あとは、何個のトッ…