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

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

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)

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

題意:

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

考察:グラフを描く

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

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

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

f:id:chiwawa_star:20170304121816j:plain

考察:実装を考える

グラフの状態である ST再帰関数の引数に持って、 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;
}

English Sentence|AOJ| Volume0-0029

単語の出現頻度 | Aizu Online Judge を解きました。

題意:

・英文が与えられるので、「出現頻度が最も高い単語」と、「文字数が最も多い単語」を出力する。
・与えられる英文は半角英文字で、半角スペースを含む。
・文章の文字数は1000文字以下
・一つの単語の文字数は32文字以下
・「出現頻度が最も高い単語」「最長の文字数を持つ単語」はそれぞれ文中に一つだけしか存在しない事が保証されている。

考察:

<出現頻度が最も高い単語>
出現頻度が最も高い = 重複数が最も多い と言えるので、各単語の重複数のMAX値をとる。
➡︎ 指定された値と等値な要素の数を数える事ができる std::count *1 を使う。

<文字数が最も多い単語>
文字数が最も多い = 文字列長(要素数)が最も長い(多い) と言えるので、各単語の文字列長のMAX値をとる。
➡︎ 文字列長は string::size *2 で取得する。

計算量:

入力の受け取りに Θ( |S| ) 時間、vector への要素構築に償却定数時間、MAX値を探索するloopに O( |S| ) 時間, std::count で 1つの単語について重複を数えるのに  O(|S|) 回なので、1回の loop で O( |S|^2 ) 時間となり、全体では O( |S|^2 ) 時間。

コード:


提出はここ

復習:

プロの提出を見ていたら map解 があったので、 mapでも解いてみました。
値の持ち方を map< 単語, 重複数 > として、重複を始めにカウントしてしまうという解き方。
計算量は、全体で O( N\, log \,N ) なので、こちらの方が良さそう。

追記:

( int ) とキャストしている箇所を size_t にしたら?とアドバイス頂いたので、修正してみました。

無駄なキャストがなくなりました!

ABC062 A - Grouping|AtCoder

A: Grouping - AtCoder Beginner Contest 062 | AtCoder を解きました。
A 問題ですが、学びがあったのでメモ。

題意

・1 から 12 までの整数が下記のようにグループ分けされています。

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

・整数  x, y \, ( 1 ≤ x < y ≤ 12 ) が与えられるので、 \it x, \it y が同一のグループに属している場合 Yes を、そうでない場合は No を出力する。

コード:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x, y;
    cin >> x >> y;
 
    int cnt1{}, cnt2{};
    for( auto &i : vector<int>{ 1, 3, 5, 7, 8, 10, 12 } )
    {
        if( i == x || i == y ) cnt1++;        
    }
    for( auto &i : vector<int>{ 4, 6, 9, 11 } )
    {
        if( i == x || i == y ) cnt2++;        
    }
    cout << ( cnt1 == 2 || cnt2 == 2 ? "Yes" : "No" ) << endl;
}

実装を少し考えてみたけれど、自分ではこれ以上簡潔に書けなくて、
AC した後、他の方の提出を見たらグループ番号を持たせるという工夫があり、学びでした。

  • 1, 3, 5, 7, 8, 10, 12 ➡︎ グループ 0
  • 4, 6, 9, 11 ➡︎ グループ 1
  • 2 ➡︎ グループ 2

↑上記のようにグループ番号( 0, 1, 2 )を付加します。(番号は何でも良い)
↓そして、 1 から 12 までの整数を昇順に並び替えグループ番号で配列に持ちます

vector<int> vc{ -1, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 }

この時、制約より x0 が与えられる事はないので、適当に -1 とかで vc[ 0 ] を埋めておく。
これにより、vc[ x ] vc[ y ] がどのグループか  O( 1 ) で知る事ができ、一致判定が可能となる訳です。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> vc{ -1, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 };
    
    int x, y;
    cin >> x >> y;
    
    cout << ( vc[ x ] == vc[ y ] ? "Yes" : "No" ) << endl;
}

↑コードが凄く簡潔になりました!

std::equal_to|C++|STL

std::equal_to の覚書

C++日本語リファレンスによると下記の通り↓
メンバ変数を持たず、状態を保持しないとのこと。

equal_toクラスは、等値比較を行う関数オブジェクトである。*1

equal_to< 型 >()( left, right ); で、指定した型による left == right の比較が行われ、
bool 値( 0 / 1 )が返ってくる様です。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    //int
    for( int i = 0; i < 3; i++ )
    {
        cout << i << ":" << equal_to<int>()( i, 2 ) << endl;
    }
    cout << endl;
    //string
    vector<string> vc{ "NO","YES","NO" };
    for( int i = 0; i < 3; i++ )
    {
        cout << i << ":" << equal_to<string>()( vc[ i ], "YES" ) << endl;
    }
    return 0;
}

実行結果はこちら

#include <bits/stdc++.h>
using namespace std;
int main()
{
    //int
    auto f = [ = ]( int x ){ return x == 2; };
    for( int i = 0; i < 5; i++ )
    {
        cout << i << ":" << f( i ) << endl;
    }
    cout << endl;
    //string
    vector<string> vc{ "NO","YES","NO" };
    auto f2 = [ = ]( string x ){ return x == "YES"; };
    for( int i = 0; i < 3; i++ )
    {
        cout << i << ":" << f2( vc[ i ] ) << endl;
    }
    return 0;
}

実行結果はこちら

ラムダでも同じ感じで書けました◎
(単にラムダを書く練習です...)

std::equal_to の使い所はまだ思い浮かばないのですけど、
使うとしたら、std::all_of *2 との合わせ技で使う例を見たので、
vector 等に入った要素の比較判定とかで使えそうではあります。

広告を非表示にする