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

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

VSCode の Snippet に競プロ用テンプレを設定する方法

VSCodeで新規ファイルを開いた時に tmp と打つと自分のテンプレが追加されるようにしたのでメモ

設定環境MacOS 10.14.3 / VSCode 1.32.1

f:id:chiwawa_star:20190513012728p:plain

Code ➡ Preferences ➡ User Snippets と進む

f:id:chiwawa_star:20190513013325p:plain

gitで管理している競プロ用フォルダ c-pro の中に作りたいので、
New Snippets file for 'c-pro' ... を選択します。

{
    "Print to console": {
        "prefix": "tmp",
        "body": [
            "#include <bits/stdc++.h>",
            "using namespace std;",
            "#define REP(i,n) for(int i=0; i<(n); i++)",
            "#define REP2(i,x,n) for(int i=x; i<(n); i++)",
            "#define ALL(n) begin(n),end(n)",
            "struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;",
            "const long long INF = numeric_limits<long long>::max();",
            "int main()",
            "{",
            "    return 0;",
            "}"
            ],
        "description": "template"
    }
}

選択すると、名称未設定.code-snippets というファイルが出来るのでそこに展開したいテンプレートを json で書きます。

"prefix": で設定した text を打つとサジェストされるようになります。
"body": は展開される中身(テンプレ)
"description": は Snippet 使い分けるために書いておいた方が良さそう

f:id:chiwawa_star:20190513015015p:plain

tmp って打つとサジェストされる

f:id:chiwawa_star:20190513015212p:plain

無事テンプレ展開されるようになりました!
簡単便利!

約数列挙|C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    
    vector<int> v;
    for( int i = 1; i <= N; i++ )
    {
        if( N % i == 0 )
        {
	       v.emplace_back( i );
        }
    }
    for( auto &x : v )
    {
        cout << x << " ";
    }
    cout << endl;
    cout << "count : " << v.size() << endl;
    return 0;
}
INPUT
100
OUTPUT
1 2 4 5 10 20 25 50 100 
count : 9

実行コード:[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

2018年 進捗大反省会

年が明けてしまったけれど、2018年振り返り進捗大反省記事を書きます。

競プロ

2018年は問題数にしたら 100 問ちょっとしか解けなかった。(理由は後述)
過去最小値な気もするけど、2018年前半は DP 問題を主に勉強してました。
2019年は ABC - C, D 埋めをしたいですね。

言語

C++ 以外にも色々な言語を少しずつ触ってみました。

  • Python で ABC A 問題を解いてみた
  • Java で ABC A 問題を解いてみた
  • Java で初めて競プロ以外のコードを書いてみた(!!!)
  • Swift を最近始めてみた(アプリの勉強)

エディタ

仕事

一昨年夏に転職したけれど、夏に退職してしまった。(ちょうど1年くらい)
開発環境が最高だったけれど、パワハラが横行していて思ったような仕事ができず本質的ではない気がしてきて辞めた。(私が直接的にパワハラを受けた訳ではない)

しかし、ここでの一年は色々な事を経験させて貰えたり、学習したりで大変満足している。
( git フローも覚えたよ!)
残業をたくさんして家での勉強時間が減ってしまったのは唯一残念だった。
家で競プロする時間がないのが思いの外ストレスで、辞める理由の1つに入るくらいだった。

新しい職場は、前よりさらに刺激的です。
使用ツールがガラッと変わったので、一から色々覚え直ししているのですけど、
最高のメンターにより、毎日が学びで楽しいです。
定時で帰れることも多く、ドラッグストアが開いている時間に帰れるのがうれしい。

スプラトゥーン2

仕事を辞めてから2ヶ月半くらい毎日スプラトゥーン2をして遊んでいた。
こんなに継続的にゲームをしたのは人生初だった。
ゲーム禁止家庭で育ったので、ゲームが絶望的に下手...でも下手なりに楽しめるため楽しい。
プレイ時間もそろそろ1'500時間に届きそう(でも下手)

f:id:chiwawa_star:20190104040042j:plain

競プロ界隈の人といつもわいわい遊んでる。
みんな遊んでくれてありがとう。
わいわい遊びたい人いたら、Twitterでお声がけください!

2019年の目標

  • 仕事を軌道にのせる(まずこれ)
  • 英語頑張らないと
  • 競プロする時間つくる
  • Swift 勉強
  • iPhone, Android の仕様覚えないと
  • スプラ S 帯いきたい

仕事とプライベート(趣味)がバランス良く両立できないと精神衛生上ダメなんだなあと学んだので、
今年は趣味に費やす時間も確保したいです。
C++ 書けない日があるのは楽しくない人生です。(おわり)

std::next_permutation|C++|順列

std::next_permutation という関数を覚えたのでメモ

std::next_permutation は、[first, last) の範囲を次の順列に変換する関数です。*1
これを使うと配列内の要素の順列を簡単に列挙することができます。
全ての順列を取得する場合は、関数に最初に与える範囲が昇順にソート済みになっている必要があります。

全列挙例
#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> v{ 1, 2, 3 }; //要素は昇順にソートしておく
    
    for( int i = 0; i < 6; ++i )
    {
        for( auto &x : v )
        {
            cout << x << " ";
        }
        cout << endl;
        next_permutation( begin( v ), end( v ) ); //次の順列が生成される
    }
    return 0;
}

実行コード:[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

出力
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

std::next_permutation については下記サイトで解りやすく説明されています。
参考:順列生成 next_permutation, prev_permutation 入門


No.676 C0nvertPr0b1em|yukicoder|std::replace_if

C++ の algorithm ヘッダにある std::replace_if を初めて使って解いたのでメモ。

解いた問題:No.676 C0nvertPr0b1em - yukicoder ★1


題意

  • 英文字列 S が与えられる。
  • S に含まれる英字  I,l を 数字の  1 に、 O,o を 数字の  0 に置き換えたものを出力する。
  •  |S| \leq 10^3


考察

特定の英字を探し、一致したら数字に置き換えるという易しい問題です。
loop で一文字ずつ見ていっても解けますが、今回は std::replace_if を使って解きました。

std::replace_if は、「条件を満たす要素を指定された値に置き換える。*1 」という機能を提供するSTLです。

std::replace_if( 検索開始位置, 検索終了位置, 置換条件, 置換する値 )

同じような STLstd::replace *2 がありますが、std::replace の場合、「指定された値と一致する要素を指定された値に置き換える」ことしか出来ません。( e.g. 文字列に含まれた全ての A を 1 に置換する...など )
ですので、今回の問題のように置換したい条件がある場合は、std::replace_if を使うと第三引数( 置換条件 )にラムダ式 *3 を使えて便利です。

第三引数に使うラムダ

// 文字が I, または l のとき true を返す
[]( const char &c ){ return c == 'I' || c == 'l'; }

// 文字が O, または o のとき true を返す
[]( const char &c ){ return c == 'O' || c == 'o'; }

注意点として、今回は英字を数字に置換するので、置換する数字の方を第四引数で指定するとき同じ char 型で渡す必要があります。

第四引数は置換する要素と同じ型にする

replace_if( ALL( S ), []( const char &c ){ return c == 'I' || c == 'l'; }, '1' );
replace_if( ALL( S ), []( const char &c ){ return c == 'O' || c == 'o'; }, '0' );

 


コード

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    string S;
    cin >> S;
    replace_if( begin( S ), end( S ), []( const char &c ){ return c == 'I' || c == 'l'; }, '1' );
    replace_if( begin( S ), end( S ), []( const char &c ){ return c == 'O' || c == 'o'; }, '0' );
    cout << S << endl;
    return 0;
}

提出:https://yukicoder.me/problems/no/676
別解:https://yukicoder.me/submissions/255892 ( loop解 )
 


計算量

std::replace_if の計算量は 「正確に last - first 回の述語の適用を行う。」となっている。
この問題の場合、文字数分の比較(条件判定)が発生するので、std::replace_if 1 回の走査につき  O(|S|).
全体では  O(|S|) となる。


参考