AtCoder Beginner Contest100
A.Happy Birthday!(100)
問題
https://beta.atcoder.jp/contests/abc100/tasks/abc100_a
円を16等分する。16等分された部分をA個、B個選ぶ時、隣り合わないようにA個、B個選ぶことはできるか。
方針
A問題だけどちょっと考える。隣合わない選び方は16等分されている円のうち1つ飛ばしで最大8個まで選ぶことができる。なのでA、Bがともに8個以内であれば可能。そうでなければ不可能。
雑記
1分くらい考えました。
B.Ringo's Favorite Numbers(200)
問題
https://beta.atcoder.jp/contests/abc100/tasks/abc100_b
100でちょうどD回割り切れる自然数のうち、N番目に小さい数を求めよ。
方針
N*10D とやりたくなる。見事にWA。よくよく考えると、ちょうどD回割り切れる数なので、例えばD=0のとき、100は100で1回割り切れてしまうので、順番に含めてはいけない。ちょうどD回割り切れる数を列挙して、そのN番目を求める。
雑記
この問題を0WAで解ける人は洞察がするどい。あるいはN=100のサンプルケースがあればみんな幸せになりそうですね。
C.*3 or /2(300)
問題
https://beta.atcoder.jp/contests/abc100/tasks/abc100_c
長さNの数列Anが与えられる。1回の操作で数列の各要素に
- A_iの値を2で割る
- A_iの値を3倍する
というどちらかの操作を行う時、操作できる最大の回数を求めよ。ただしすべてのiに対して3倍することはできず、操作後のA_iの値は整数でなければならない。
方針
ぱっと見る感じ無限回操作できるように思えた。しかし、2で割ったときのA_iが整数でなければならない。という点がポイントと気づいた。A_iを3倍するという操作は答えに関係なく、各要素が2で最大何回割ることができるか。という問いに帰着する。各A_iが2で何回割ることができるか数え上げた。
public void solve(int testNumber, InputReader in, PrintWriter out) { int n = in.nextInt(); long[] a = in.nextLongArray(n); long ans = 0; for (int i = 0; i < n; i++) { while (a[i] % 2 == 0) { a[i] /= 2; ans++; } } out.println(ans); }
雑記
C問題としては簡単と思えた。一発ACでよかった。
D.Patisserie ABC(400)
問題
https://beta.atcoder.jp/contests/abc100/tasks/abc100_d
N個の要素がある。N_i番目の要素の値はx_i,y_i,z_iである。N個の要素の中からM(<=N)個選ぶ時、M個の組み合わせの各x_i,y_i,z_iの総和の絶対値の最大値を求めよ。
方針
この問題は本番中にわからなかった。理解するために以下の小問題を考える。
5個の要素をもつ数列A_n={-7,-4,1,2,4}が与えられる。A_nのうち3個選びその総和の絶対値の最大値を求めよ。
総和の絶対値であることがポイントである。絶対値とは |x| = {-x,x}のことである。総和の絶対値を |sum| とする時、絶対値の記号を外すと、 |sum| = {-sum,sum} であるから、このどちらかが解になることがわかる。sum = A_i + A_j + A_k とあらわされたとすると、|sum| = {A_i + A_j + A_k, -A_i - A_j - A_k} である。つまりこれはA_nの各要素を正の方向から降順に3つ選択するか、もとの数列の各要素を予め-1をかけて、正の方向から降順に3つ選択するかのどちらかに他ならない。(ここに気づけるかどうかがポイントと思われる)。小問題の場合は正の方向から3つ選んだ場合は{1,2,4}となり合計7、負の方向から選択する場合は各要素を予め-1にすることでA_n'={7,4,-1,-2,-4}となる。この場合の最大値を求めればいいと考えると貪欲に降順にソートし、上から3つ選択すればいい。つまり{7,4,-1}となり答えはmax(7,10)=10である。
さて、小問題の考察を踏まえて、D問題の考察をしよう。題意より求める答えは以下のようになる。
max(|Σx_i| + |Σy_i| + |Σz_i|)
各要素x,y,zを最大化する時それぞれ最大化する方向として正負の2通り存在するので、全体としては23=8通りの組み合わせが存在する。具体的には
- max(+Σx_i +Σy_i +Σz_i)
- max(+Σx_i +Σy_i -Σz_i)
- max(+Σx_i -Σy_i +Σz_i)
- max(+Σx_i -Σy_i -Σz_i)
- max(-Σx_i +Σy_i +Σz_i)
- max(-Σx_i +Σy_i -Σz_i)
- max(-Σx_i -Σy_i +Σz_i)
- max(-Σx_i -Σy_i -Σz_i)
である。このそれぞれの正負の組み合わせのいずれかが解になると仮定して最大値を求める。ひとつの具体的な計算方法を確認しよう。今
max(+Σx_i -Σy_i -Σz_i)
が最大化する解になるとする。各総和が、元の要素のl,m,n番目から構成されるとすると
⇔max{(x_l+x_m+x_n) + (-y_l-y_m-y_n) + (-z_l-z_m-z_n)}
⇔max{(x_l-y_l-z_l) + (+x_m-y_m-z_m) + (+x_n-y_n-z_n)}
となることがわかるので、A_iのx_i,y_i,z_iの各要素の符号を決めて和を取り、和の降順にm個選べば良い。
public void solve(int testNumber, InputReader in, PrintWriter out) { int n = in.nextInt(), m = in.nextInt(); long[][] num = new long[n][8]; for (int i = 0; i < n; i++) { long x = in.nextLong(); long y = in.nextLong(); long z = in.nextLong(); num[i] = new long[]{x+y+z, x+y-z, x-y+z, x-y-z, -x+y+z, -x+y-z, -x-y+z, -x-y-z}; } long ans = -INF; for (int i = 0; i < 8; i++) { long tmp = 0; List<Long> tmpList = new ArrayList<>(); for (int j = 0; j < n; j++) { tmpList.add(num[j][i]); } Collections.sort(tmpList, Comparator.reverseOrder()); for (int j = 0; j < m; j++) { tmp += tmpList.get(j); } ans = Math.max(ans, tmp); } out.println(ans); }
雑記
本番ではずっとDPの遷移について考えていて、どうやったらDPでできるか。ということしか考えられませんでした。ひとつはDPに習熟していないことが原因とは思っています。DPでどこまでできるか、どこまでできないかのあたりがある程度つけられれば少し検討して、DPではできないかもしれないと気づけたかもしれません。行き詰まったときに別の方針を検討する必要がありそうです。
さて、解くためのポイントですが以下のように感じました。
- 絶対値の扱い方
- 求める解の定式化
実際、「絶対値だから場合分けすればいい。ということと、符号を決めて各要素の和をとって降順に選択すればいい」ということにに気づければ実装は割と簡単な気がします。絶対値の扱いは高校数学の数Ⅰでよく出てくる典型の考え方のように感じました。基本的な数学的事項が問われていた気がします。いくつか絶対値が絡む問題を問いて復習し、次回以降は確実に本番でACしたいですね。
追記
最適解を求めるプロセスとしてはsatanicプロの考え方がわかりやすかったです。x_i,y_i,z_iの最終的な符号を決めれば、
ans = Σx+Σy+Σz = Σ(x+y+z)
になり、貪欲に求められるということ。
ある最適な選び方をしたときの答えが
— satanic@競プロ! (@satanic0258) 2018年6月16日
ans=|Σx|+|Σy|+|Σz|
で,その時Σx<0,Σy>=0,Σz<0だったとき,
x[i]=-x[i], z[i]=-z[i];
としておくと
ans=Σx+Σy+Σz
が答えになる.
逆に最終的な評価の符号を決めてしまえばΣx+Σy+Σzを最大化すればよくなり,これは
Σx+Σy+Σz=Σ(x+y+z)
より貪欲に選んでいける
絶対値の捉え方については、場合分けをするということよりも |x| = max(-x , x) というような元の数に対する2つの操作のうち大きい方をとる操作という考え方もあるようです。
あと絶対値を
— 宮内けんこ (けんちょん) (@drken1215) 2018年6月17日
・正のときはそのまま
・負のときはマイナスをとる
という捉え方も「場合分け解法」を思い付くには有益ではあるけれども、
・|a| = max(a, -a)
だと思った方が、証明に納得感が生まれる気がするのん。
そもそも絶対値とは、それが正か負かに関係なく
— 宮内けんこ (けんちょん) (@drken1215) 2018年6月17日
・そのまま
・-1 倍したもの
のうちの「大きい方をとる操作」だという捉え方をしておくと、上述の心配事がそもそも気にならなくなるのん。