std::vectorに代入された要素が全て同じ値か否かをチェックするコードを、
自分の参照用に記事として残します。

std::set は重複するデータの保持を許さないコンテナ *1 なので､
重複チェックの意味合い的にも適している、( 0 )と( 3 )を使っていこうと思います。

「値が一種類」は「集合としてはサイズ 1」と同値

*1:set - cpprefjp C++日本語リファレンス

2016-10-01

Life, the Universe, and Everything｜Codeshef｜beginner

CodeChef

CodeChef デビューしましたっ！(登録しただけ)
まずは Life, the Universe, and Everything (beginnerのtest用問題？)を提出して色々確認。

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N;
    while( cin >> N )
    {
        if( N == 42 ) break;
	cout << N << endl;
    }
    return 0;
}

ちゃんとC++14使えました！
beginner, easyの問題も多かったので学習用に解いていきたいと思ってます！
(contestは多分出ない....)

2016-09-29

No.218 経験値1.5倍｜yukicoder

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）は天井関数と言う様です。
実はどちらも初めて知りました(今までどうしていたのか謎...)

2016-09-21

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

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:必ずしもそうではないです

C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

TopCoder 導入編

重複要素チェック｜C++

Life, the Universe, and Everything｜Codeshef｜beginner

No.218 経験値1.5倍｜yukicoder

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