LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@RubyLrving(ruby lrving)

AtCoder Beginner Contest 406

Last updated at Posted at 2025-05-19

A - Not Acceptable

問題文

O(1)
時間を分に変換して比較しましょう。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    if(a * 60 + b > c * 60 + d){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

B - Product Calculator

問題文

O(N)
ループ文とオーバーフローの問題です。
下記のコードはオーバーフローしてWAになります。
コンテスト中は解決策が思いつかなかったので回避策を取りました。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    ll mod = 1;
    rep(i, K) mod *= 10;
    ll ans = 1;
    rep(i, N){
        ans *= A[i];
        if(ans >= mod) ans=1;
    }
    cout << ans << endl;
    return 0;
}

pyhotnは整数のbit数を気にしなくて良いです。

import sys
import math
import heapq
import itertools
import numpy as np
from collections import deque
from functools import reduce
from string import ascii_lowercase

# main
def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    mod = 1
    for i in range(0, K):
        mod *= 10

    ans = 1
    for i in range(0, N):
        ans *= A[i]
        if(ans >= mod):
          ans=1
    
    print(ans)

# エントリポイント
if __name__ == '__main__':
    main()

正攻法の解決策ではないです。
しっかり勉強しないとCやD問題で詰むようになります。
正攻法を考察しましょう。
オーバーフローをしないように掛け算を割り算に変更します。

a_i * x >= m

を

a_i >= m / x

にするとWAになります。
これはなぜでしょうか。下記のサンプル入力で詳しく考察していきます。

2 1
3 3

の時、計算式は、

3 * 3 >= 10

両辺を3で割ります。

3 >= 10 / 3

端数の少数部分は切り捨て、

3 >= 3

if文の判定式はtrueになります。
これではx = 1となりWAになってしまいます。
本来なら、

3 >= 3.33333....

3は3.333.....より小さいのでfalseになります。
整数型の割り算、仕様の問題ですね。
>=は少数部分、切り捨ての値を考慮しない不等式だと分かります。
それでは>を使用しましょう。

a_i * x > (m-1)

>なのでm未満の最大の整数であるm-1を使用します。
これを先ほどのサンプル入力で考察しましょう。

3 * 3 > 10 - 1 

3 > (10 - 1 ) / 3

3 > 3

3は3より大きくないのでfalseになります。
>は少数部分の切り捨てを考慮できる不等式ですね。

a_i > (m-1) / x

が答えになります。
コーディングしましょう。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    ll mod = 1;
    rep(i, K) mod *= 10;
    ll x = 1;
    rep(i, N){
        if(A[i] > (mod-1) / x) x=1;
        else x *= A[i];
    }
    cout << x << endl;
    return 0;
}

ACできました。
さらに>=の不等式を使用する方法はないのか。
そこも考察していきましょう。
少数部分の切り捨てが問題です。
m / A[i]の計算時に1以上の余りが存在するなら切り上げの処理を行いましょう。

a_i * x >= m

x >= (m + A[i] - 1) / A[i]

A[i] - 1を加算しているので1以上の余りが存在するなら少数の部分を切り上げる処理になります。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    ll mod = 1;
    rep(i, K) mod *= 10;
    ll x = 1;
    rep(i, N){
        if(x >= (mod+A[i]-1)/A[i]) x=1;
        else x *= A[i];
    }
    cout << x << endl;
    return 0;
}

ACになりました。
>=は式の変更時、割り算なら切り上げの処理を実装する。
>は式の変更時、割り算なら切り捨てを考慮しているのでそのまま処理を実装する。
これで式を変更する際に、割り算で発生する少数部分を考慮してプログラミングを組む事ができるようになりました。

C - ~

問題文

ランレングス圧縮の問題です。
私はコンテスト中、尺取法に見えて沼りました。
この問題は問題文を理解するのが難しい問題です。

A_{i-1} < A_i > A_{i+1}

と

A_{i-1} > A_i < A_{i+1}

の並びを一つずつ含む数列Pを求めます。
サンプル1で考察しましょう。

6
1 3 6 4 2 5

の場合、

3 6 4 2 5
1 3 6 4 2 5

の２つの数列が答えになります。
次にサンプル3を見ましょう。

12
11 3 8 9 5 2 10 4 1 6 12 7

下記のパターンを数列Pとして良いか。

11 3 8 9 5

答えは❌です。条件に、

A_1 < A_2

とあります。
数列Pは＜の不等号から始まらなければいけません。

3 8 9 5 2 10
8 9 5 2 10
2 10 4 1 6
2 10 4 1 6 12

の４つのパターンになりました。
４つのパターンを見ると数列Pは以下のように値が増減しています。

名称未設定.png

ランレングス圧縮を行います。
数列Pの不等号が>の時を基準にして、左右の辺の長さを掛け算した値の合計を求めると良さそうです。
考察ができました。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    rep(i, n) cin >> p[i];
    vector<int> d;
    rep(i, n-1){
        d.push_back((p[i]<p[i+1]? 0:1));
    }

    vector<P> rle;
    for(auto x:d){
        if(rle.size() && rle.back().first == x) rle.back().second++;
        else rle.push_back({x, 1});
    }

    ll ans = 0;
    rep(i, rle.size()){
        if(rle[i].first == 1){
            ll l = 0, r = 0;
            if(0<i) l = rle[i-1].second;
            if(i+1<rle.size()) r = rle[i+1].second;
            ans += l*r;
        }
    }
    cout << ans << endl;
    return 0;
}

D - Garbage Removal

問題文

過去に類題がありますね。
もちろん予習済みです。

例題

D - Cross Explosion
D - Lamp

ごみ（x, y）のデータを、各軸ごとに保持をします。
x, y軸を基準したデータ構造を用意します。
vector<set<int>>h(H), w(W)が分かりやすです。

queryが1の時、x行目の要素を削除します。
h[x].clear()で全て削除できます。
しかしwのデータを、hより先に削除しないといけません。

C++
            for(auto y:h[x]){
                w[y].erase(x);
            }
            h[x].clear();

h[x]から列yの値を取り出します。
y列目にxの値の要素があるので、w[y].erase(x);で要素を削除します。

queryが2の時も1の時と同じような処理を行います。
考察ができましたね。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int H, W, N, Q;
    cin >> H >> W >> N;
    vector<set<int>> h(H), w(W);
    rep(i, N){
        int x, y;
        cin >> x >> y;
        x--; y--;
        h[x].insert(y);
        w[y].insert(x);
    }
    cin >> Q;
    for(int i=0; i<Q; i++){
        int q;
        cin >> q;

        if(q==1){
            int x;
            cin >> x;
            x--;
            cout << h[x].size() << endl;

            for(auto y:h[x]){
                w[y].erase(x);
            }
            h[x].clear();
        }   

        if(q==2){
            int y;
            cin >> y;
            y--;
            cout << w[y].size() << endl;
            for(auto x:w[y]){
                h[x].erase(y);
            }
            w[y].clear();
        }   

    }

    return 0;
}
1
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?