ABC170に参加しました - imomoの勉強記録

AtCoderのコンテストに参加した際の結果と考え方、反省点などを書いていきます。
コンテストページはこちら

解いた/挑んだ問題
結果
- コンテスト結果
- 順位、パフォーマンス変動
反省点

解いた/挑んだ問題

A問題

問題の概要

1,2,3,4,5が代入されていた変数があり、変数の一つに0を代入したものが与えられる。
0が代入される前の数字を出力せよ

制約

入力として与えられる変数5つは操作を行ったとのものとしてあり得るものである。

どのように考えたか

変数ごとに比較して、一つ目が0なら1、二つ目の変数なら2というように判定

結果

・提出ししたコード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
    int a, b, c, d, e,ans =5;
    cin >> a >> b >> c >> d >> e;
    if (a == 0)ans = 1;
    if (b == 0)ans = 2;
    if (c == 0)ans = 3;
    if (d == 0)ans = 4;
    cout << ans << endl;
    return 0;
}

if文を並べているので汚くなってしまっている

ACまでの時間

ACしたのはコンテスト開始から2分後です。

f:id:iiiimmmmo:20200615001215p:plain — ABC170_A

B問題

問題の概要

庭2本の足を持つ鶴と4本の足を持つ亀がいる
動物の総数とそれらの足の数が与えられるのでこれらの数字で成立するか判定せよ

制約

$1 \leq X \leq 100$
$1 \leq Y \leq 100$
入力中のすべての値は整数である

どのように考えたか

鶴が0～動物の総数羽いるとしてfor文を回して、あり得る値か判定する

結果

一発AC
提出したコード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
    int x, y;
    bool ans = false;
    cin >> x >> y;
    for (int i = 0; i <= x; i++) {
        if ((i * 4 + (x - i) * 2) == y) {
            ans = true;
            break;
        }
    }
    if (ans) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

片方の動物を固定して考えると楽だった

ACまでの時間

ACしたのはコンテスト開始から5分後です。

f:id:iiiimmmmo:20200615002710p:plain — ABC170_B

C問題

問題の概要

ある整数、続いて長さNの整数列が与えられる
整数列に含まれないもののうち最もある整数に近いものを出力せよ

制約

$1 \leq X \leq 100$
$1 \leq N \leq 100$
$1 \leq p_i \leq 100$
$p_1 ,. . . ,p_N はすべて異なる$
入力中のすべての値は整数である

どのように考えたか

trueで初期化した要素数が102のbool型を用意しておき、整数列の整数の要素をfalseに書き換える
0～101のfor文を回しbool配列に含まれていない数字とXの絶対値をとり、一番絶対値が小さかったものを出力

結果

一発AC
・提出したコード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
    int x, n,p;
    int ans = 0;
    cin >> x >> n;
    vector<bool>sq(102, true);
    rep(i, n) {
        cin >> p;
        p;
        sq[p] = false;
    }
    int minx = 200;
    rep(i, 102) {
        if (sq[i]) {
            if (minx > abs(x - i)) {
                minx = abs(x - i);
                ans = i;
            }
        }
    }
    cout << ans << endl;

    return 0;
}

0と101の考慮を忘れそうで危なかった

ACまでの時間

ACしたのはコンテスト開始から21分後。

f:id:iiiimmmmo:20200615005138p:plain — ABC170＿C

D問題

問題の概要

長さNの数列Aが与えられる
数列のある数字がほかの数字によって割り切ることができないものの数を答えよ

制約

入力はすべて整数
$1 \leq N \leq 2 × 10^5$
$1 \leq A_i \leq 10^6$

どのように考えたか

数列の数一つ一つの約数を求めてそれ以外の数が当てはまるか確かめ、当てはまった場合をカウントしてNから引く

結果

TLEが取れませんでした
・提出したコード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;


int main() {
    int n,a;
    ll cnt = 0;
    cin >> n;
    vector<set<ll>>s(n);
    map<int, int>m;
    vector<bool>num(1000000, false);
    vector<int>sq;
    rep(j, n) {
        cin >> a;
        m[a]++;
        sq.push_back(a);
        num[a] = true;
        for (ll i = 1; i * i <= a; i++) {
            if (a % i == 0) {
                s[j].insert(i);
                if (i * i != a)s[j].insert(a / i);
            }
        }
    }
    rep(i, n) {
        m[sq[i]]--;
        if(!m[sq[i]]) num[sq[i]] = false;
        for (auto se : s[i]) {
            if (num[se]) {
                cnt++;
                break;
            }
        }
        num[sq[i]] = true;
        m[sq[i]]++;
    }
    cout << n - cnt << endl;

    return 0;
}