ぐっすり [ AtCoder Regular Contest 036 A ]
問題
長さ N の数列がある。
数列の長さ 3 の部分列のうち、初めて和が K 未満になるような部分列の位置を求めよ。
考察
勉強のため、二種類の解法で解きたいと思います。
累積和から部分和を求める
数列に対してあらかじめ累積和をとっておくことで、その数列の好きな位置・好きな長さの部分和を O(1) で求められるようになるテクニックです。以下のサイトで詳しく解説されています。
コード（累積和から部分和を求める）
void solve (FastScanner in, PrintWriter out, Methods ms) { int n = in.nextInt(), lower = in.nextInt(); long[] sum = new long[n+1]; sum[0] = 0; for (int i=1; i<n+1; i++) { sum[i] = sum[i-1] + in.nextInt(); } for (int i=3; i<n+1; i++) { if (sum[i] - sum[i-3] < lower) { out.println(i); return; } } out.println(-1); }
しゃくとり法
詳しくは以下略。
長さが常に一定（3）のしゃくとり法なので、実装が異様に簡単です。
コード（しゃくとり法）
void solve (FastScanner in, PrintWriter out, Methods ms) { int n = in.nextInt(), lower = in.nextInt(); int[] ar = in.nextIntArray(n); int L = 0, R = 3; int sum = ar[0] + ar[1] + ar[2]; while (L < n-3) { if (sum < lower) { out.println(R); return; } R++; sum += ar[R-1]; sum -= ar[L]; L++; } out.println(-1); }
ちなみに
N<=10^5 なので、部分列の和を毎回求める全探索（a[0]+a[1]+a[2], a[1]+a[2]+a[3]......）でも間に合います。
部分列の長さが短いので、全探索としゃくとり法の計算量の差がほとんどありませんね……。
高橋君とお肉 [ AtCoder Regular Contest 029 A ]
問題
N 個の数字を A,B の2つのグループに分ける。
Aグループに属する数字の合計を sumA 、Bグループに属する数字の合計を sumB とする。
sumA, sumB の差が最小になるようにグループ分けをするとき、sumA, sumB のうち大きいほうを出力せよ。
考察
DPの解法もあるみたいですが、素直に全探索します。
N は 1<=N<=4 なので組み合わせの数は最大でも 2^4=16 となり間に合います。
それぞれの肉について、Aに属するかBに属するかをビット全探索で探索し、差が最小となるような組み合わせを求めます。
コード
void solve (FastScanner in, PrintWriter out) { int n = in.nextInt(); int[] niku = in.nextIntArray(n); int min = Integer.MAX_VALUE; for (int bit=0; bit<(1<<n); bit++) { int sum1 = 0, sum2 = 0; for (int j=0; j<n; j++) { if (((bit>>j) & 1) == 1) { sum1 += niku[j]; } else { sum2 += niku[j]; } } min = Math.min(min, Math.max(sum1, sum2)); } out.println(min); }
梱包できるかな？ [ AtCoder Regular Contest 013 A ]
問題
N*M*L の大きさの箱に、P*Q*R の大きさの荷物はどれだけ入るか。
荷物はどの向きで入れてもよい。
考察
以前作成した nextPermutation の使いどころがやってきました。
・Javaでnext_permutationメソッドを作ってみる - 文系プログラマーのプログラミング備忘録
nextPermutation メソッドで荷物の向きのパターンを全列挙し、入れられる数の最大値を出力します。
コード
void solve (FastScanner in, PrintWriter out) { int[] a = in.nextIntArray(3), b = in.nextIntArray(3); ArrayList<Character> list = new ArrayList<>(Arrays.asList('0', '1', '2')); int max = Integer.MIN_VALUE; while (list.size() != 0) { max = Math.max(max,(a[0]/b[list.get(0)-'0'])*(a[1]/b[list.get(1)-'0'])*(a[2]/b[list.get(2)-'0'])); list = nextPermutation(list); } out.println(max); } static ArrayList<Character> nextPermutation (ArrayList<Character> list) { int pivotPos = -1; char pivot = 0; for (int i=list.size()-2; i>=0; i--) { if (list.get(i) < list.get(i+1)) { pivotPos = i; pivot = list.get(i); break; } } if (pivotPos==-1 && pivot==0) { list.clear(); return list; } int L = pivotPos+1, R = list.size()-1; int minPos = -1; char min = Character.MAX_VALUE; for (int i=R; i>=L; i--) { if (pivot < list.get(i)) { if (list.get(i) < min) { min = list.get(i); minPos = i; } } } Collections.swap(list, pivotPos, minPos); Collections.sort(list.subList(L, R+1)); return list; }
nextPermutation メソッドはあれから少し改良して、順列パターンを String ではなく ArrayList
All Green [ AtCoder Beginner Contest 104 C ]
問題
問題 i は、解いたときに貰えるスコアが 100*i 点、問題数が p[i] 問、全ての問題を解いたときに貰えるボーナススコアが c[i] である。これらの問題を解いてスコア G以上 を得るとき、少なくとも何問の問題を解かなければならないか。
考察
難しい問題ほど解くのに時間がかかる……といった制約も存在しないので、一見、貰えるスコアが多い順に問題を解いたほうがいいように思えます。しかし、以下のようなケースが存在します。
2 1000
1 99999
10 100
100点問題が1問と、200点問題が10問あり、1000点以上を得ることが目標です。
200点問題を5問解くと合計が1000点になりますが、100点問題は1問解くだけで全完ボーナス99999点が貰えるので、100点問題を1問だけ解くのが最適となります。
全完ボーナスの存在がなければスコアの大きい順に貪欲に解いていく方法で解けますが、全完ボーナスが存在するために問題が複雑になっています。
そこで、それぞれの問題について
・全完ボーナスが貰えるまで解く（全ての問題を解く）
・一問も解かない
の2通りの解き方をビット全探索で全探索します。問題数は 1<=D<=10 なので間に合います。
もし、ある組み合わせにおいて、いくつかの問題を全完ボーナスが得られるまで解いたにもかかわらず、それでもまだ目標のスコアに届かない場合は、スコアが最も多い問題を全完しないギリギリまで（p[i]-1問まで）解きます。
それでもまだ届かない場合は、もともと最適な選び方ではなかったということで、その組み合わせを放棄します。
コード
void solve (FastScanner in, PrintWriter out) { //入力 int n = in.nextInt(), goal = in.nextInt(); Problem[] p = new Problem[n]; for (int i=0; i<n; i++) { p[i] = new Problem(in.nextLong(), (i+1)*100, in.nextLong()); } //ビット全探索+@ long min = Long.MAX_VALUE; for (int i=0; i<(1<<n); i++) { int num = 0; //その組み合わせでは何問解いたか？ long sum = 0L; //その組み合わせで得られたスコアの合計 //全完していない問題のうち、最もスコアが高いもの、すなわち //i をビット表現したときに最も右側にある 0 の位置を記録する変数 int rightMost = -1; for (int j=n-1; j>=0; j--) { // if ((1&i>>j) == 1) { sum += p[j].num * p[j].score + p[j].bonus; num += p[j].num; } else if ((1&i>>j) == 0 && rightMost == -1) { rightMost = j; } } //sum が目標スコア以上の場合は、解いた問題の数をそのまま min に記録する if (sum >= goal) { min = Math.min(min, num); continue; } else if (rightMost != -1){ //そうでない場合かつ、全完していない問題が少なくとも1つある場合 //目標スコアに届くまで、スコアが最も多い問題を needNum 回解く必要がある long needNum = (goal-sum+p[rightMost].score-1) / p[rightMost].score; if (needNum > p[rightMost].num) { //スコアが最も多い問題が needNum 問より少ないなら、放棄 continue; } else { //そうでないなら、スコアが最も多い問題を needNum 問解き、 //min を更新する min = Math.min(min, num + needNum); } } } out.println(min); } static class Problem { long num, score, bonus; Problem (long a, long b, long c) { num = a; score = b; bonus = c; } }
Ehab and another construction problem [ Codeforces Round #525 (Div. 2) A ]
問題
x (1<=x<=100) が与えられる。
以下の条件を全て満たすように、a,b を選んで出力せよ。条件を満たすように a,b を選べない場合は -1 を出力せよ。
・1<= a,b <=x
・a を b で割り切ることができる
・a*b > x
・a/b < x
考察
x=1 のとき、明らかに選べないので、-1 を出力します。
x=2 以上のとき、仮に b を 2 に固定して考えてみます。
x=2 のとき、a=2, b=2 とすると
・1 <= 2,2 <= 2
・2%2 = 0
・4 > 2
・1 < 2
となって全て満たします。
x=3 のとき、同様に a=2, b=2 とすると全て満たします。
x=4 のとき、a=4, b=2 とすると全て満たします。
x=5 のとき、同様に a=4, b=2 とすると全て満たします。
このように考えていくと、どうやら x が偶数の場合は a=x, b=2、x が奇数の場合は a=x-1, b=2 とすると条件を満たすことができそうです。困ったら偶奇に逃げる癖がついていますが、この先大丈夫でしょうか……。
コード
void solve (FastScanner in, PrintWriter out) { int n = in.nextInt(); if (n==1) out.println(-1); else { out.println((n%2==0?n:n-1)+" "+2); } }
AtCoder Grand Contest 031 感想
AtCoder Grand Contest 031 に参加しました。
2時間、一生懸命考えましたが解法のカの字も浮かびませんでした。したがって提出していません。
A - Colorful Subsequence
atcoder.jp
文字の出現回数+1 をかけ合わせるだけでいいみたいです。
仮に、a=1, b=1, c=1 としてみます。このとき、それぞれを取るか取らないかという考え方をして、答えは 2*2*2 で 8......ですが一つも取らないということはできないので 8-1=7通りとなります。
a=1, b=1, c=3 のとき。a,b については同様。c は、1番目を取るか、2番目を取るか、3番目を取るか、取らないかの 4 種類。したがって、2*2*4-1 で15通りとなります。
敗因
組み合わせ = 2^N だと思い込んでいた。先ほどの例だと、a=1, b=1, c=1 のときの求め方は 2^1 * 2^1 * 2^1 だと勝手に思い込んでいたということです。なぜかはわかりませんが僕の頭の中はこうなっていました。
そのため、2^3 とか、2^3 - (2^(k-1) - 1) とかわけのわからない数式を量産して混乱していました。よって、数学の「組み合わせ問題」に慣れていなかったせいである、と結論することができるでしょう。数学を勉強しましょうね。
Find Divisible [ Educational Codeforces Round 57 (Div. 2) A ]
問題
範囲 L,R (1<=L<=R<=998244353) が与えられる。
L,R の範囲内にあるような x,y (x!=y) で、y を x で割り切ることができるものを出力せよ。
なお、そのような x,y が存在することは保証されている。
考察
x!=y であるような x,y の存在が保証されているので、範囲には少なくとも 2 個の数字が含まれます。
L=10, R=10 のような入力は来ないということですね。
次に、問題を読み換えることを考えます。
・y を x で割り切ることができる
ではなく、
・y/x をしたときに 1以上の商 が得られるかどうか
と考えます。
得られる商のうち、最も小さいものは 1 です。しかし、商として 1 を得るためには y と x が同じ数でなければならず、問題の x!=y という条件に当てはまらないので、商が 1 となるように x,y を選ぶことはできません。となれば、問題で指定されているような x,y は、y/x の商が少なくとも 2 以上になるような x,y ということになります。
次に、商が 2 のときを考えます。商として 2 を得るためには、x=k のとき y=2k である必要があります。これならば x!=y となるように x,y を選ぶことができるので、選択肢に入ります。仮に、商が 2 となるように x,y を選べることが保証されているならば、範囲の右端である R は少なくとも L の2倍でなければなりません。式で表すと L=k のとき少なくとも R>=2k である必要があるということです。
次に、商が 3 のときを考えます。x=k のとき y=3k、かつ、L=k のとき R>=3k です。L=k, R>=3k という範囲には、L=k, R>=2k が含まれています。商として 3 を得られるような範囲のときには、必ず商として 2 を得られる、ということです。このことは商が 4 であっても 100 であっても同様です。
これらのことから、与えられる範囲 L,R は L=k のとき R>=2k 、すなわち、y/x の商が 2 になるような x,y が存在するような範囲であることが保証されています。ただし、商が 3 以上の場合については、必ずしも保証されていません。
よって、x=L, y=2L を出力すればよいです。このとき、2L が範囲内であることは R>=2k によって保障されています。
コード
void solve (FastScanner in, PrintWriter out) { int n = in.nextInt(); for (int i=0; i<n; i++) { int L = in.nextInt(), R = in.nextInt(); out.println(L+" "+2*L); } }
