CodeForces, 動的計画法 |
2完
・複数の棚がある。
・棚にメダルとトロフィーを入れたい。
・一つの棚にはメダル10個までかトロフィー5個までのどちらかのみを入れる。
・それぞれの大会で獲得したメダルとトロフィーの数と棚の数が与えられる。
・全て格納出来るかどうかを答える。
・メダルとトロフィーの総和をそれぞれ計算する。
・それぞれ格納できる数で割る。
・また、剰余が発生するかを確認し、剰余が発生する場合は棚の数をデクリメントする。
ただし、他の人のソースを見て気付いたけど、わざわざ剰余を計算するよりも、以下の様に書いた方がすっきりしてよい。
あらかじめ「割られる数」に割る数－1を足してやれば、余りが出た場合も切り上げで求めることが出来る。
N -= (aS + 4) / 5;
void solve() throws Throwable {
int[] a = readIntArray();
int[] b = readIntArray();
int N = readInt();
int aS = 0;
for (int aN : a) {
aS += aN;
}
int bS = 0;
for (int i : b) {
bS += i;
}
N -= aS / 5;
if (aS % 5 != 0) N--;
N -= bS / 10;
if (bS % 10 !=0) N--;
if(N >=0) {
pw.println("YES");
} else {
pw.println("NO");
}
}
・文字列Sを変形して文字列Tにすることが出来るかどうか。
・文字列Sの要素を削除するだけでTに出来る場合は、「automaton」
・文字列Sの要素を並び変えるだけでTに出来る場合は、「array」
・どちらも行う場合は、「both」
・どちらを行っても出来ない場合は、「need tree」
・それぞれの文字列のアルファベットの出現回数をメモする。
・文字列Tの方が出願回数の多いアルファベットがある場合、「need tree」
・文字列Sの方が出現回数の多いアルファベットがある場合、「automaton」のフラグを立てる。
・文字列Sと文字列Tで最長共通部分文字列を取得し、最長共通部分文字列の長さが文字列Tと等しくない場合、「array」のフラグを立てる。
・上記の2点より、「automaton」、「array」、「both」を判別する。
void solve() throws Throwable {
String s = readLine();
String t = readLine();
int[] sA = new int[27];
int[] tA = new int[27];
for (char c : s.toCharArray()) {
sA[c-'a']++;
}
for (char c : t.toCharArray()) {
tA[c-'a']++;
}
boolean isAutoMaton = false;
for (int i = 0; i < 27; i++) {
if(sA[i] > tA[i]) {
isAutoMaton = true;
} else if (sA[i] < tA[i]) {
pw.println("need tree");
return;
}
}
char[] sX = s.toCharArray();
char[] tX = t.toCharArray();
int[][] dp = new int[s.length() + 1][t.length() + 1];
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < t.length(); j++) {
if(sX[i] == tX[j]) {
dp[i+1][j+1] = dp[i][j] + 1;
} else {
dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
}
}
}
boolean isArray = false;
if(dp[s.length()][t.length()] != t.length()) {
isArray = true;
}
if(isAutoMaton && isArray) {
pw.println("both");
} else if (isAutoMaton) {
pw.println("automaton");
} else if (isArray) {
pw.println("array");
}
}
・複数のフェンスがある。
・フェンスの横幅は1M,縦幅はそれぞれ異なる。
・フェンスに色を塗りたい。一回で塗れるのは縦方向、または横方向のみ。横方向に塗る場合は、塗る高さにフェンスが連続してないといけない。
・全てのフェンスに色を塗る時の最小の回数を求める。
・動的計画法を使う。
・dp[N+1]に、N本目を横塗りした場合の最小の塗る回数をメモする。
やり方としては、N本目までに出現しているフェンスから遡って順々に、
最も高さの低いフェンスから、今回横で塗りたいフェンスの高さの差を求める。
N-j本目の最小の塗る数 + (i - j - 1)(一本遡る毎に縦塗りをする）+ 求めた高さの差
N本目からN-j本目まで塗る場合の最小の塗る数を求める。
void solve() throws Throwable {
int N = readInt();
int[] a = new int[N + 2];
for (int i = 0; i < N; i++) {
a[i+1] = readInt();
}
int[] dp = new int[N + 2];
Arrays.fill(dp, N);
dp[0] = 0;
for (int i = 1; i <= N + 1; i++) {
int minH = Integer.MAX_VALUE;
for (int j = i - 1; j >= 0; j--) {
minH = Math.min(minH, a[j]);
int p = Math.max(0, a[i] - minH);
dp[i] = Math.min(dp[i], dp[j] + i-j-1 + p);
// System.out.println(i + " " + j + " " + dp[i]);
}
}
pw.println(dp[N+1]);
}
1501⇒1586
最高レート更新ヽ(^o^)丿