No.218 経験値1.5倍｜yukicoder

No.218 経験値1.5倍 - yukicoderを解きました。

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    cout << ( ( A + B - 1 ) / B * 2 / 3 < ( A + C - 1 ) / C ? "NO" : "YES" ) << endl;
    return 0;
}

小数点の切り上げを覚えたのでメモ！

2.0 ➡︎ 2
2.1 ➡︎ 3

...としたい場合に2つの方法がありました。

1）std::ceil
ceil - cpprefjp C++日本語リファレンス

2）( a + m -1 ) / m
//切り上げ整数除算
今すぐ使える C++ コーディングテクニック集 - torus711 のアレ

1）は天井関数と言う様です。
実はどちらも初めて知りました(今までどうしていたのか謎...)

No.22 括弧の対応｜yukicoder｜stack

No.22 括弧の対応 - yukicoder を解きました。

括弧の対応、括弧列の問題は典型的な問題らしく、stack で解くと良いと教えて頂きました。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
//開き側の位置も閉じ側の位置も分かっている(重要)
int main()
{
    int N, K;
    string S;
    cin >> N >> K >> S;
    
    stack<int> st;
    int res{};
    REP( i, (int)S.size() )
    {
        if( S[i] == '(' )
        {
            st.push( i + 1 );
            continue;
        }
        //括弧が ) の時 -> K番目が来たらstackのtopを保存する
        if( i + 1 == K )
        {
            res = st.top();
            break;
        }
        //括弧が ( の時 -> K番目がstackのtopに来たら閉じ括弧の位置を保存する
        if( st.top() == K )
        {
            res = i + 1;
            break;
        }
        st.pop();
    }
    cout << res << endl;
    return 0;
}

2回目の提出コード↑
1回目の提出でK番目の括弧の向きによって、括弧を反転させる...などという周りくどいコードを書いたのですが...そんな必要は全くなかったので書き直しました。
stackのtop()にある括弧の位置が分れば、閉じ括弧の位置も取得出来るので、括弧の向きに囚われがちなんですが、括弧の向きは重要ではない事が解りました。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
//pairで対応する括弧のindexを保持していくversion
int main()
{
    int N, K;
    string S;
    cin >> N >> K >> S;
    
    vector<pair<int, int>> P;
    stack<int> st;
    
    REP( i, (int)S.size() )
    {
        if( S[i] == '(' )
        {
            st.push( i );
            continue;
        }
        //Lに'('のindex, Rに')'のindexを入れる
        int L = st.top() + 1;
        int R = i + 1;
        P.emplace_back( L, R  );
        
        st.pop();
    }
    for( auto &x : P )
    {
        if( x.first == K )
        {
            cout << x.second << endl;
            break;
        }
        if( x.second == K )
        {
            cout << x.first << endl;
            break;
        }
    }
    return 0;
}

3回目の提出↑
実はstackで解けると知る前、vector<pair<char, int>>で括弧とindexを保持していく解法でコード書いていたんですが...上手く行かず。
でもvectorでも書いてみたかったので、プロのコードを参考に書いてみました。
私はpairに括弧とindexを入れましたが、括弧は2種類しかないので、わざわざpairで持つ意味がないっぽかったです...。
その代わりに、leftとrightに分けて括弧と閉じ括弧のindexをpairで持ちました。
括弧が対応しているイメージで解けるのは良いかも...(？)

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N, K;
    string S;
    cin >> N >> K >> S;
    
    stack<int> st;
    vector<int> res( N );
    REP( i, N )
    {
        if( S[i] == '(' )
        {
            st.push( i );
            continue;
        }
        int tmp = st.top();
        st.pop();
        res[i] = tmp;//left'(' のindex
        res[tmp] = i;//right')'のindex
    }
    cout << res[ K - 1 ] + 1 << endl;
    return 0;
}

↑最後、別解(プロのコード参照)
pairで左右の位置を保持すると、添字と左右の括弧の位置の3つの値を持ってしまう事になり、少し無駄があるという事で、pairでなく、vector<int>にして値を保持する書き方も。
コードがもっと簡潔になりました。

「括弧の対応を求める問題」はスタックを使うとうまく解けることが知られています

【初心者的スローガン】括弧列はstackで解く！*1
今回はこれを覚えました(おわり)

*1:必ずしもそうではないです

Round#91 A. Lucky Division｜Codeforces

Problem - 122A - Codeforcesを解きました。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
bool check( int N ){
    string S = to_string( N );
    REP( i, (int)S.size() )
    {
        if( S[i] != '4' && S[i] != '7' ) return false;
    }
    return true;
}
int main()
{
    int N{};
    cin >> N;
    cout << ( check( N ) || N % 4 == 0 || N % 7 == 0 || N % 47 == 0 || N % 74 == 0 ? "YES" : "NO" ) << endl;
    return 0;
}

lucky digits が 4 と 7。
lucky digitsのみで構成されるNとlucky digitsで割り切れるNがlucky。

Switching Railroad Cars｜AOJ｜stack

stackに慣れる為に車両入れ替え | Aizu Online Judgeを解きました。

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N;
    stack<int> st;
    while( cin >> N )
    {
        if( N == 0 ){
            // 0が来たら取り出し
            cout << st.top() << endl;
            st.pop();
            continue;
        }
        // 0以外はstackに積む
        st.emplace( N );
    }
    return 0;
}

TLE本でstackを勉強してから使ってなかったので、使い方の確認をしました。
st.push(N)よりst.emplace(N)(C++11)を使うようにしています。

stackはコンテナアダプタ！

参考）stack - cpprefjp C++日本語リファレンス

C++ で 桁和

#include <bits/stdc++.h>
using namespace std;
int digit( int N )
{
    while( N >= 10 )
    {
        int tmp{};
        while( N > 0 )
        {
            tmp += ( N % 10 );
            N /= 10;
        }
        N = tmp;
    }
    return N;
}
int main()
{
    int N{};
    cin >> N;
    cout << digit( N ) << endl;
    return 0;
}

とある問題で桁和を使うのかと思って書いたのですが、
結果的に桁和不要だったので、桁和コードだけ個別に残します...。

例えば、N が 799 の場合、 7 + 9 + 9 = 25 ➡︎ 2 + 5 = 7 と
1桁になるまで足していくコードです。
(もしかしたら、もっと簡潔な書き方があるかも知れないです...)

実行結果：[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ