｢DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選｣に参加した

tags: 競技プログラミング

競技プログラミングとは

• 競技プログラミングとは一言で言うのは難しいのですが,このコンテストの場合においては｢より多くの問題｣を｢より早い時間(リアルタイム)｣で解くことを競うプログラミングです
• 今回出たのはそのうちAtCoderという会社がやっている競技プログラミングのコンテストです
• 楽しいかは人によって違いますが僕は｢できれば楽しいけどできないと楽しくない｣と思っています
• ちなみに今日は全く楽しくなかったです^^

泣きたい

今回は問題が6問あったんですが,1問しか解けなかったです...

＼(^o^)／ｵﾜﾀ

問題ページです

A問題

単にif文で比較するだけの問題です

落ち着いて問題を解くことに集中しました

解答

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)

ll money(ll x)
{
    if (x == 3) {
        return 100000;
    } else if (x == 2) {
        return 200000;
    } else if (x == 1) {
        return 300000;
    } else {
        return 0;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll x, y;
    cin >> x >> y;
    ll ans = 0;
    if (x == 1 && y == 1) {
        ans += 400000;
    }
    cout << ans + money(x) + money(y) << endl;
    return 0;
}

B問題

コンテスト中に答えが出なかった問題です

LLONG_MAXを使えば良いだけだったので狂いそうです...

解答

• 棒を左側と右側に分けます
  • この際に短い方を延ばせば差が縮まります
  • なのでabs(右側-左側)が最小となるものを探します
• sumとleftという変数を用いることで以上の探索を$O(N)$で実現します
  • sumを棒の長さの和とします
  • leftは左側の棒の長さの和です
  • sumからleftを引いた値が右側の棒の長さの和です
  • このとき右側の棒の長さの和をrightとしてleftとの差の大きさを求めます
  • その差が最小のものが答えです

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    vector<ll> A(N);
    ll sum = 0;
    rep(i, N)
    {
        cin >> A[i];
        sum += A[i];
    }
    ll left = 0;
    ll ans = LLONG_MAX;
    for (int i = 0; i < N - 1; i++) {
        left += A[i];
        ll right = sum - left;
        ll need = abs(right - left);
        ans = min(ans, need);
    }
    cout << ans << endl;
    return 0;
}

まとめ

最近コンテストに出ていなかったのですが記事にすることで出場回数を増やそうと思い記事にしました...(半分自戒を込めて記事を書いています)

下はRating遷移です