AtCoder Regular Contest 079 D: Decrease (Contestant ver.)

どうやら自分の解法が想定解法と違うみたいなので、別解をブログに残しておきます。

問題概要

日本語なので原文参照 → D: Decrease (Contestant ver.) - AtCoder Regular Contest 079 | AtCoder

解説

まず、出力する数列の長さは に固定してしまいます。この方が大きな入力にも対応できるからです。(もちろん、小さな入力にも対応できる)

番目の要素の値を 、また 番目の要素に対して操作を行う回数を と表すことにします。

まずは、 の値がなるべく均等になるように操作回数を各要素に配分しましょう。すると、 番目の要素の値は、他の要素で操作を行うことで 増えることがわかります。この増分を とします。

これで、 番目の要素は という値まで増え、操作回数は 回必要であることがわかりました。あとは、この情報を元に を決めれば答えがわかります。

要素の値が 以上なら操作を 1 回行う必要があり、 以上なら 2 回・・・ということを考えると、このような式を満たせば良いことがわかります。

床関数があって扱いにくいので、変形します。

したがって、

この範囲に収まるように を決定すれば良いことがわかりました。あとはこの範囲内の値になるように適当に決めたら良いです。

※注意: の下限は ですので、負の値にならないように気をつけましょう。

ソースコード

int K, rec[60], ans[60];
const int N = 50;

signed main() {
    cin >> K;
    int div = K / N, mo = K % N;
    rep(i,0,N) rec[i] = div + (i < mo);

    rep(i,0,N) {
        int sum = 0;
        rep(j,0,N) if(i != j) sum += rec[j];
        ans[i] = N * (rec[i] + 1) - sum - 1;
    }
    cout << N << endl;
    rep(i,0,N) cout << (i ? " " : "") << ans[i];
    cout << endl;
    return 0;
}

ICPC 国内予選 2017 参加記

今日を終わらせたくないので、この勢いのまま参加記を書いてしまいます。

チーム情報

今年は構文解析のプロ・ rsk0315 ( @rsk0315_h4x ) と幾何のプロ・ TAB ( @_____TAB_____ ) と就寝のプロ・自分 (tsutaj) の 3 人で、チーム four-t で出場しました。チーム結成は 4 月くらいだった気がします。

振り返り

リハーサルは圧倒的エスパー力により全完 1 位と幸先の良いスタート。このまま国内予選もうまくいってくれ〜〜〜となる。(これは罠でそんなにうまくいくわけがない)

本番までの空き時間は Primepop で精神を落ち着かせながら過ごした。3 桁の素因数分解つらい。やってるうちに慣れてきて素因数分解のプロに変化していくえび君を見ているのが楽しかった。

そしてなんだかんだで本番になる。自分はテンプレート書いて印刷かけて A 問題をやる担当になっていたので A 問題をやった。7 分くらいで AC。

その後、えび君が B 問題を難なく AC (自分が問題文を 1 文字も見ないまま終わってしまった)。その間に自分が D を考察していたけど、これ DP では？ みたいになったので早速実装する。想定解法ではなさそうだけど (わりと実行時間かかるやつだった) 時間制限 3 時間の ICPC なので大丈夫やろ！w と思って動かしたら動いたのでよかった。D 問題無事 AC。

TAB 君が C 問題の実装に取り掛かった。自分は 4 完を最優先に考えていたのでデバッグに回った。今思うとこの選択がすごく良かったのかなあと思う (結局早解きで通過できたので)

バグをとって C も AC。ここまで 1 時間 15 分で、割と早いのでは？という気持ちになったけど、順位表を見ると既に結構 4 完がいたのでもう 1 問解いて安心しておきたいなあとなる。

残りの時間で F 問題を詰めようという話になり、ずっと考察していた。途中で方針が立ったので実装したけど、境界条件が非常に面倒でデバッグが辛い。全員でコードを睨みながら間違いを潰していく。コンテスト終了 5 分前くらいに惜しいところまではいったけれど、結局詰められず終了。悔しかった。

結果は 4 完 31 位、かつ学内 1 位だったのでおそらく通過できました。去年の悔しさからずっと頑張ってきたので本当に良かったです。

反省

E の解法を聞いたら単純な全探索らしく、この問題を早々に捨ててしまったのは完全にミスだったように思う。もっと問題文をよく読んで判断すべきだった。

あと G の解法も最初フローなのかなあ、でも辺どうやって張るんだ・・・とかいろいろ考えて諦めたけど結局左手法でうまくいくようで本当につらかった。まさか G 問題でそんな解法の問題が出るとは思わなかった・・・頭が固い・・・。

F で TAB 君を助けきれなかったのも心残り。デバッグの方法とかいろいろ提案したけど、もっと早いうちから提案しておけば少しは状況違ったのかなあ・・・とか、いろいろ考えてしまう。次に実装でハマる問題が出てきた時はもっと早急に助けられるようにしたい。

全体で見たら成績はそれなりに良かったものの、反省点は結構多いです。アジア地区までに修正したいです。

さいごに

国内予選だいすき！一番好きなコンテストです。

次も頑張ります。精進するぞ〜〜〜〜〜

Codeforces Round #416 (Div. 2) C: Vladik and Memorable Trip

本番出てた回。ようやく復習できました。

問題概要

原文 → Problem - C - Codeforces

長さ の数列があり、 番目の要素を と書く。

次のルールに従って区間を選ぶ (複数でも良い、数列全体を被覆するような選び方でなくても良い) とき、選んだ区間の重みの合計を最大化せよ。

• 区間内に登場する要素 それぞれについて、 と同じ値を持つ全ての要素が必ず同一の区間内に含まれていなければならない。
• 区間の重みは、区間内に登場した数字の集合の XOR である (例えば、 という区間であれば、区間の重みは となる。)

解説

まず、各値について最左、及び最右のインデックスを覚えておき、これを と表記することにします。

取りたい区間の左端 を固定して、dp[i] = [0, i) の範囲での重み合計の最大値 なる DP を解くことを考えます。問題文の条件より、取りたい区間の中にある要素のうち、最左のインデックス が より左であるものがあれば、その区間は invalid です。逆にそうでない場合、区間の右端 を に伸ばす、すなわち今まで出てきた要素と同じ値をもつ全ての要素を同一の区間内に入れられるまで区間を伸ばしたあと、 DP 配列を更新します。

ソースコード

実装はとても楽です。大正義半開区間。

int N, a[5010];
int l[5010], r[5010], dp[5010];

signed main() {
    cin >> N;
    rep(i,0,5010) l[i] = INF, r[i] = -1;
    rep(i,0,N) {
        int p; cin >> p;
        a[i] = p;
        chmin(l[p], i);
        chmax(r[p], i+1);
    }

    rep(i,0,N) {
        chmax(dp[i+1], dp[i]);
        if(l[ a[i] ] == i) {
            int ub = r[ a[i] ], cur = i, val = 0;
            bool ng = false;
            while(cur < ub) {
                if(l[ a[cur] ] < i) ng = true;
                if(l[ a[cur] ] == cur) val ^= a[cur];
                chmax(ub, r[ a[cur++] ]);
            }
            if(!ng) dp[ub] = dp[i] + val;
        }
    }
    cout << dp[N] << endl;
    return 0;
}

問題で要求されている条件のわりに実装が簡単で面白いですね。