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^)丿