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

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

std::tuple の使い方｜C++

C++ STL

std::tuple の使い方を覚えたのでメモします。

std::tuple とは？
std::pair が 2 つの型の値を保持出来るのに対し、std::tuple は N 個の型の値を保持する事ができる。*1

宣言・要素格納：

//宣言
vector<tuple<int, string, bool>> vc;
for( int i = 0; i < 3; ++i )
{
    string a;
    bool b;
    cin >> a >> b;
    //要素構築
    vc.emplace_back( i, a, b );
}

格納する値が全部 int の場合 vector<tuple<int, int, int>> vc; となる。
値の型が異なる場合は vector<tuple<int, string, bool>> vc; とできる。
要素構築(格納)は std::emplace_back などを使ってできる。

要素の取得

std::tuple::get *2 を使って各要素を取得できる。

for( auto x : vc )
{
    //位置を指定する場合(I番目の引数)
    cout << get<0>( x ) << " " << get<1>( x ) << " " << get<2>( x ) << endl;
}

⬆ I 番目の引数を指定する事で要素を取得できる。( tuple<0番目, 1番目, 2番目> の順 )

for( auto x : vc )
{
    //型を指定する場合
    cout << get<bool>( x ) << " " << get<string>( x ) << " " << get<int>( x ) << endl;
}

⬆引数の代わりに型を入れると、その型の要素が取得できる。

for( int i = 0; i < 3; ++i )
{
    //添字も使える
    cout << get<0>( vc[ i ] ) << " " << get<1>( vc[ i ] ) << " " << get<2>( vc[ i ] ) << endl;
}

⬆ range-based for でなく普通の for 文 + 添字 で要素の取得もできる。

要素をソート

sort( begin( vc ), end( vc ) );

⬆ sort した場合、tuple の第一要素、第二要素、第三要素の順で比較した結果が返ります。*3

sort( begin( vc ), end( vc ), greater<tuple<int, string, bool>>() );

⬆ 降順 sort は第三引数に greater<tuple<int, string, bool>>() を指定します。

sort( ALL( vc ), []( const auto &x, const auto &y )
         {
             //第一要素が同一ならば第二要素の小さい方を返す
             return get<0>( x ) == get<0>( y ) ? get<1>( x ) < get<1>( y ) : get<0>( x ) > get<0>( y );
         });

std::sort の第三引数にラムダで各要素の比較結果を返せるようにも書けます。

型の要素数取得

//型の要素数取得
cout << tuple_size<tuple<int, string, bool, int, int>>::value << endl;

tuple 型としてみなせる型の要素数を取得してくれます。*4
この場合は int, string, bool, int, int なので 5 が出力される。
vector に格納された要素数が知りたい場合は vc.size() で普通に求まる。


実行コード：[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ
std::tuple 便利すぎる...。色々な問題で使ってみたい！

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

*2:tuple::get - cpprefjp C++日本語リファレンス

*3:C++11のラムダ関数の簡単なまとめ - minus9d's diary

*4:tuple_size - cpprefjp C++日本語リファレンス

ABC072 - C Together｜AtCoder

AtCoder コード 競プロ

C: Together - AtCoder Beginner Contest 072 | AtCoder を解きました。

題意：

  • 長さ N の整数列 a_1, a_2, ... a_N が与えられます。
  • a_i に対し、1 足すか、1 引くか、何もしない、の 3 つの操作が選べるので、ある整数 X を選んだ時、 a_i = X となる i の個数の最大値を出力する。
  • 1 \leq N \leq 10^5
  • 0 \leq a_i < 10^5 (1 \leq i \leq N )
  • a_i は整数

考察：

a_i に対し 3 つの操作は自由に選べる為、 a_i = X となる i の個数が最大化される操作を選択をすれば良い。
各 a_i に対し a_i, a_i + 1, a_i -1 の操作後となる整数をカウントし、最終的に重複が一番多い X の個数が 3 つの操作を最善に選んだ結果となるので、その個数が答え。

コード：

X-codeで競プロテンプレートを読み込む設定

X-code テンプレ

この記事は macOS Sierra バージョン 10.12.6, X-code Version 8.3.3 での設定方法です。

X-code で競プロのテンプレートを読み込む設定に苦労したので自分用にメモ。
結論からいうと簡単にできた。

はじめに

設定の前に確認。

  • X-code Project は Mac OS の Command Line Tool
  • 使用言語は C++

上記 2 点が私の設定環境なので、ここが違うと設定ディレクトリなどが違うので注意。

準備

まず、変更したい Default テンプレートファイルは書き込み禁止になっているので、
パーミッション設定を変更する所から始める。

1. ディレクトリ移動する

この時、フォルダ名に半角スペースが入っているので「 \ (BackSpace)」でエスケープする

$ cd /Applications/Xcode.app/Contents/Developer/Library/Xcode/Templates/File\ Templates/Source/C++\ File.xctemplate
2. 書き込み権限付与する

ディレクトリ /Default/ 以下のファイルを変更できるように管理者権限 sudo を使って変更する
パスワードが求められるので、入力すると完了。

/*USER NAME の所には自分のUSER NAMEを入れる*/
sudo chown -R USER NAME Default

テンプレ変更

Finder で /Applications/Xcode.app/Contents/Developer/Library/Xcode/Templates/
File Templates/Source/C++ File.xctemplate/Default/ に移動

___FILEBASENAME___.cpp　という cpp ファイルがあるので、これにテンプレを書く。
Default では以下のように書かれている。

//
//  ___FILENAME___
//  ___PROJECTNAME___
//
//  Created by ___FULLUSERNAME___ on ___DATE___.
//___COPYRIGHT___
//

#include <stdio.h>

これを全部消して、自分の好きなように書いて保存。
(準備でやった書き込み権限が上手く付与されていないと変更できない)

新規ファイル作成してみる

念のため、X-code を再起動し、Project を開く。
新規ファイル作成で C++ ファイル を選択すると、競プロテンプレートが反映されている！(最高)

f:id:chiwawa_star:20170826161357p:plain

他に正しい方法があるかも知れないけれど、もうこれで満足です(おわり)

MacVim で競プロテンプレートを読み込む設定

MacVim

ターミナルから MacVim で新規ファイルを開く時、競プロのテンプレートが書かれたファイルを読み込む設定をしたのでメモ。

1. テンプレート準備

  • 表示させたい競プロのテンプレートのみを書いて、任意の名前を付け、拡張子を .cpp にしてどこかに一旦保存しておく
  • /Users/任意の名前/.vim　の直下に template という名前のフォルダを作る

　　その際、直接フォルダを作る場合は非表示ファイルを表示しないと .vim が見えない。
　　参考：Macで隠しファイルを表示する方法 - Qiita
　　Sierra は [ cmd + Shift + . ] で見えるかも。

  • 先に作ったテンプレートファイルをこのフォルダに入れる

　　私は template.cpp という名前にしたので、
　　/Users/任意の名前/.vim/template/template.cpp　という構成になった。

2. vimrc で読み込み設定

  • ターミナルで下記コマンドを入力し .vimrc を開く
$ mvim ~/.vimrc
  • .vimrc に下記 1 行を追加
  • 追加したら esc 押して :wq 押して閉じる
autocmd BufNewFile *.cpp 0r $HOME/.vim/template/template.cpp

autocmd BufNewFile *.cpp 0r $HOME/.vim/template/template.cpp
⬆︎拡張子を揃えるのを忘れない。
因みに、他の言語のテンプレートも用意して、この 1 文を増やしていけばテンプレート量産できるみたいです。

3. 読み込み確認

  • ターミナルで MacVim からテンプレを呼ぶ
$ mvim template.cpp

テンプレートが書かれたファイルが Vim で開いた！！(成功)

4. コマンド短縮登録

mvim template.cpp って長いので、.bashrc に短縮登録しました。

  • ターミナルで下記コマンドを実行
$ mvim ~/.bashrc
  • Vim が立ち上がるので、下記 1 行を追加
  • 追加したら esc 押して :wq 押して閉じる

　　alias 短縮名='実行コマンド' なので任意の短縮名を付ける。

alias cpp='mvim template.cpp'
  • 念のため、.bash_profile に下記を追加する( .bash_profile から .bashrc を読みに行く設定 )
  • ターミナルで下記コマンドを実行
$ mvim ~/.bash_profile
  • Vim が立ち上がるので、下記を追加
  • 追加したら esc 押して :wq 押して閉じる
if [ -f ~/.bashrc ] ; then
. ~/.bashrc
fi
  • ターミナルで下記コマンドを実行、反映される。
$ source ~/.bashrc
$ source ~/.bash_profile

ターミナルで cpp と書くと Vim でテンプレートが反映された新規cppファイルが開く！(成功)
すごく便利〜！
※開かなかったらターミナルを再起動すると良いかも知れない

$ cpp

他にもテンプレートを読み込む方法がありましたが、一番簡単な方法で導入してみました。
おわり

次は MacVim で LaTeX を書けるように設定したいです。

参考：
ファイル新規作成時にテンプレートの値を挿入する。 - Qiita
【Mac】ターミナルなどのコマンドラインで長いコマンドを短く省略する方法 | らふらく^^ ~ブログで飯を食う~

No.52 よくある文字列の問題｜yukicoder｜深さ優先探索(DFS)

yukicoder 深さ優先探索(DFS) 競プロ

No.52 よくある文字列の問題 - yukicoder を解きました。

題意：

  • 文字列 S が与えられる。
  • S の先頭または末尾から 1 文字取り、順に繋げて新たな文字列を作る。
  • 先頭または末尾から 1 文字取った S は、また新たな S となり文字が無くなるまでこの操作を繰り返す。
  • 新たにできた文字列が何通りあるかを出力する。
  • 1 \leq |S| \leq 10

考察：グラフを描く

S = abc の場合のグラフを描いて考えました。

S… 与えられた文字列
T… S の先頭、または末尾から 1 文字取って結合した新たな文字列

頂点… S と T (状態)
辺…… S の先頭または末尾から 1 文字取り、新たな T を作る(遷移)

f:id:chiwawa_star:20170304121816j:plain

考察：実装を考える

グラフの状態である S と T を再帰関数の引数に持って、 S が空 ( S.empty() *1 ) になるまで、再帰的に下記 2 つの操作を繰り返します。

  • S の先頭文字を T に結合していく
  • S の末尾文字を T に結合していく

新たに出来た文字列 T は 最初に与えられる S や、組み替え次第で同じ文字列ができる事がある為、std::set *2 に入れて重複文字列をカウントしないようにします。

計算量：

  • 与えられた S の読み込みに \Theta(|S|) 時間
  • string::substr で S の先頭から 1 文字除いた文字列を関数に渡すのに O(|S|) 時間。取り除いた 1 文字を T に結合するのに O(|S|) 時間
  • string::substr で S の末尾から 1 文字除いた文字列を関数に渡すのに O(|S|) 時間。取り除いた 1 文字を T に結合するのに O(|S|) 時間
  • if 文での S.empty() 判定 1回につき O( 1 ) 時間
  • std::set への要素挿入に O(|S|^2) 時間
  • 解の出力に O( 1 ) 時間
  • 全体では O(2^{|S|}|S|^2) 時間

コード：

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
set<string> st;
void dfs( string S, string T )
{
    //基底部：Sが空になったら終わり
    if( S.empty() )
    {
        //重複を排除
        st.emplace( T );
        return;
    }
    //再帰部：
    //S[ 1 ] - S[ S.size() - 1 ]までを次に渡す, Tに｢先頭｣文字をくっつける
    dfs( S.substr( 1, S.size() - 1 ), T + S[ 0 ] );
    //S[ 0 ] - S[ S.size() - 1 ]までを次に渡す, Tに｢末尾｣文字をくっつける
    dfs( S.substr( 0, S.size() - 1 ), T + S[ S.size() - 1 ] );
}
int main()
{
    string S, T;
    cin >> S;
    
    dfs( S, T );
    
    cout << st.size() << endl;
    
    return 0;
}

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

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