naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Beginner Contest 100

ABC100回記念に参加!
今回もDから解いた。サーバトラブルで数分ロスしたけどとりあえずジャッジに投げて受理さえされればこっちのもの
4完(1000点)ペナルティなしで20'25で31位。
↑これまでに参加したAtCoderのコンテストの中で最高順位!(みんな条件は同じなので、サーバトラブルがなくてもその前後だとは思う)

D - Patisserie ABC (400)

max(|Σ綺麗さ| + |Σおいしさ| + |Σ人気度|)
= max(
  Σ綺麗さ + Σおいしさ + Σ人気度,
  Σ綺麗さ + Σおいしさ - Σ人気度,
  Σ綺麗さ - Σおいしさ + Σ人気度,
  Σ綺麗さ - Σおいしさ - Σ人気度,
  -Σ綺麗さ + Σおいしさ + Σ人気度,
  -Σ綺麗さ + Σおいしさ - Σ人気度,
  -Σ綺麗さ - Σおいしさ + Σ人気度,
  -Σ綺麗さ - Σおいしさ - Σ人気度
  )
= max(
  Σ(綺麗さ + おいしさ + 人気度),
  Σ(綺麗さ + おいしさ - 人気度),
  Σ(綺麗さ - おいしさ + 人気度),
  Σ(綺麗さ - おいしさ - 人気度),
  Σ(-綺麗さ + おいしさ + 人気度),
  Σ(-綺麗さ + おいしさ - 人気度),
  Σ(-綺麗さ - おいしさ + 人気度),
  Σ(-綺麗さ - おいしさ - 人気度)
  )

だよね。(Σは全要素じゃなくてM個に含まれるものだけの和)

±1の全ての組み合わせ(8通り)を試せばよい*1。±1をそれぞれに掛けて足して大きい方からM個の合計を(8通り)求めて、その最大値を返せばいい。
→AC 12'03''
https://abc100.contest.atcoder.jp/submissions/2677647

気づいたこと(accumulate()利用時の注意点)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);++var)

int main() {
    int N = 100;
    vector<int> a(N);
    vector<ll> b(N);
    vector<ll> c(N);
    rep(i,N) a[i] = b[i] = c[i] = 1e9;

    cout << accumulate(ALL(a), 0) << endl;
    cout << accumulate(ALL(b), 0) << endl;
    cout << accumulate(ALL(c), 0LL) << endl;

    return 0;
}

これ、実行してみると

1215752192
1215752192
100000000000

になるんだよね。2番目はlong longだから100000000000が出てほしいところなんだけど。
f:id:n4_t:20180616222837p:plain
返り値は第3引数の型と同じになるので、0LLにしてやらないとlong longで計算してもらえない。

解説より

また、この問題は実はO(N)で解くことができます。長さNの数列をソートしてM番目に大きい値Aを最悪計算量O(N)で求めるアルゴリズムこのリンクに書かれており、値Aが求まった後は求めた値より大きい値の合計を計算すれば良いので、この問題の最悪計算量はO(N)となります。

median of medians(中央値の中央値)を用いてnth elementを最悪計算量O(N)で求め、それ以上の値をO(N)で列挙(累積)することでO(N)で求められる、という話。
↑これは使えるようになりたい

C - *3 or /2 (300)

手順「2で割る」をできるだけ使い渋る(1回につき1つは2で割らないといけないが)作戦。
3を掛けても2で割れる回数には影響はない。2で割らないやつには3を掛ける。
というわけでΣ(a_iが2で何回割れるか)が打てる最大手数。
→AC 2'43''
https://abc100.contest.atcoder.jp/submissions/2678471

B - Ringo's Favorite Numbers (200)

一見N\cdot 100^Dで良さそうなんだけど、これだとN=100のときにD+1回になるよね。ひっかけ問題。(ひっかからないぞ)
→AC 3'27''
https://abc100.contest.atcoder.jp/submissions/2679266

A - Happy Birthday! (100)

A,Bともに8以下ならYay!、さもなければ:(を表示。
→AC 2'12''
https://abc100.contest.atcoder.jp/submissions/2679745

*1:最初ビットで書き始めたけどこの数だとforを積んだほうが書きやすいし自分的にわかりやすいのでfor3重ループにした。