問題 問題概要 省略 解法 ループを回すだけ。一見、制約が大きいので回すだけではダメなように見えるが、金額は最低でも2倍に増えて行くので(k=1を除いて)、計算量がlogになり、時間内に可能。ただし、 k=1の場合は例外として処理する必要がある。 ミス 特に…

問題 問題概要 都市0から都市Nへ移動する。都市iから都市i+1にj日目に移動するとき，Di*Cj疲労度がたまる。都市0から都市Nまで移動した時の疲労度の最小を求めよ．ただしM日以内にNに到達しなければならない。 解法 都市iにいて，その時j日目の状態において…

問題 問題概要 服を選んで、|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でだければならない。 解法 ステージの難易度を昇順にソート…

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

問題 問題概要 幅優先探索で最短経路を求める問題。ただしスタートとゴールがいくつもある。 解法 よくあるstartからgoalまでの最短経路を求める問題と同じ。ただし、その途中でチーズを小さい順に食べていかなければならない。そのため、（ciをチーズi番目…

問題 問題概要 M個のクエリ満たす数字の並びを求める問題。 解法 まず、 どのような数字が数字の集合としてあり得るのかを計算してflagに入れておく。そして漸化式でdpを解く。感覚的には空集合の場合の数から全集合の場合の数へ、集合の数を増やす感じに計…

問題 問題概要 与えられた数字をソートして、もとの添え字の番号を出力する。 解法 pairは1つ目の要素でソートした後、2つ目の要素でソートするので、pairに(身長, 番号)を入れることで、身長でソートした番号がわかる。 ミス 特になし。 コード #include <iostream> #</iostream>…

問題 問題概要 直方体の体積を求める問題 解法 ただ計算するだけだが、2辺をかけるとlong long型を超える可能性があるので、modをとることでオーバーフローを防ぐ。 体積 = a * b % mod * c % mod ミス 特になし コード #include <iostream> #include <cstdio> using namespace</cstdio></iostream>…

問題 問題概要 指定された添え字の番号を出力する 解法 やるだけ ミス 特になし コード #include <iostream> #include <string> using namespace std; int main(void){ string s; cin >> s; int n; cin >> n; printf("%c\n", s[n - 1]); return 0; }</string></iostream>

問題 問題概要 与えられる文字列(数字)n個の中からk個選んで、つなげることで、できあがる文字列の種類を求める。 解法 next_permutationを使い、すべての順列を作る。その順列すべてに対して、前からk個選んで選んだ順番に文字列としてつなげる。そのように…

問題 問題概要 一列バージョンのぷよぷよみたいな感じ。好きな場所の色を一箇所変えることができ、それを行うことにより最も多くボールを消せる場合を求める問題。 解法 まずすべての玉の色を変えて全探索する。そして色を変えた前後で同じ色の数をカウント…

問題 問題概要 縦横のどちらか一列すべてを消すゲーム。指定された番号の人が負けるかどうかを判定する問題。 解法 この問題はプレイヤーが負けないように選べはゲームをする回数はh + w - 1に必ずなるので、あとはmodで計算。ただし与えられる数字は0オリジ…

問題 問題概要 連続したクエリの中に頂点とそれをつなぐ辺の長さのクエリと、2点間の最短距離を求めよというクエリが含まれる。 解法 任意の2点間の距離を求めるにはワーシャルフロイト法で求めることができる。ただし、最短経路を求めよというクエリに対し…

問題 問題概要 レーテイングを表記する 解法 場合分けしてやるだけ ミス 特になし コード #include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> using namespace std; int main(void){ int a, b; cin >> a >> b; if(a > b) printf("-%d\n", a - b); if(a == b) printf("</cstdlib></cstdio></algorithm></iostream>…

問題 問題概要 まず星座の座標のみが与えられる。次にゴミデータも含んだ星座の座標が与えられる。座標は相対的なもので、星と星の位置関係は変わらないが、1度目と2度目で与えられる絶対座標は異なる。どのように平行移動すれば絶対座標が一致するから求め…

問題 問題概要 数字の連続した長さの最大値を求める問題。ただし与えられたクエリの中に、0があれば好きな数字に変えることができる。 解法 まず、与えられた数字をバケツソートしておく。前から順番に数字を見ていき、連続成分の大きさで最大ものを探す。そ…