Neunomizuの日記

俺だけが俺だけじゃない

「三井住友信託銀行プログラミングコンテスト2019」に参加した

tags: 競技プログラミング

感想

  • D問題がわからなかった...

A

  • M1M2を比較するだけです
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int m1, m2, d1, d2;
    cin >> m1 >> d1;
    cin >> m2 >> d2;
    if (m1 == m2) {
        cout << 0 << endl;
    } else {
        cout << 1 << endl;
    }
    return 0;
}

B

  • Xを1から50000まで動かしてNになるか調べるだけです
  • 50000を(万)を5000(千)と見間違えて2WAしました...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int x = 1; x <= 50000; x++) {
        if ((int)floor(x * 1.08) == n) {
            cout << x << endl;
            return 0;
        }
    }
    puts(":(");
    return 0;
}

C

  • 100円のおにぎりがあるのでX100で割ったときのあまりを上手く払えるかを考えます
  • 他の商品の値段は101円から105円まであります
    • これを100円の商品に対して余分に1円から5円払うという風に考えます
  • つまりX100で割った数だけ1~5円を余分に払えるということです
  • そのため答えの条件を満たすかは
    • $Xを100で割ったあまり \leq Xを100で割った商 \times 5$
    • で調べることが可能です
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;
ll X;
ll cnt, rem;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> X;

    cnt = X / 100;
    rem = X % 100;
    if (rem <= cnt * 5) {
        cout << 1 << endl;
    } else {
        cout << 0 << endl;
    }

    return 0;
}

D

  • わからず...
  • 2分木でも作るのかなと思ったんですが明らかに計算量がおかしい...
  • 公式の解答を見ると000から999まで全探索するようですね
    • ということで実装します
    • 自分で実装しようと思って解答を見たらスッキリしていてどこか虚しくなったので公式解答を見て多少改変したやつを貼ります
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N;
    string S;
    cin >> N >> S;
    int cnt = 0;
    for (int i = 0; i < 1000; i++) {
        int num[3] = { i / 100, (i / 10) % 10, i % 10 };
        int f = 0;
        for (int j = 0; j < N; j++) {
            if (S[j] == ('0' + num[f])) {
                f++;
            }
            if (f == 3) {
                cnt++;
                break;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

まとめ

  • コーディングをしていないので依然として茶色になりそう
  • D問題を確実に解けるようになりてぇ~~~
  • 過去問をやろうな俺