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

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

std::next_permutation|C++|順列

std::next_permutation という関数を覚えたのでメモstd::next_permutation は、[first, last) の範囲を次の順列に変換する関数です。*1 これを使うと配列内の要素の順列を簡単に列挙することができます。 全ての順列を取得する場合は、関数に最初に与える範…

No.676 C0nvertPr0b1em|yukicoder|std::replace_if

C++ の algorithm ヘッダにある std::replace_if を初めて使って解いたのでメモ。解いた問題:No.676 C0nvertPr0b1em - yukicoder ★1 題意 英文字列 が与えられる。 に含まれる英字 を 数字の に、 を 数字の に置き換えたものを出力する。 考察 特定の英字…

MacPorts で Python3系をインストール

Mac で少しだけ Python を実行できる環境を整えたので自分用メモ。 gcc を入れる時に使った MacPorts が既にインストールされているので、それを利用します。 まずはターミナルで python --version を実行すると、version 2.7.10 と表示されました。 Mac に…

いろいろなDP|動的計画法|ナップザック

DP 配列を- INF で埋めた DP が解らなかったのでナップザック問題を使って比較してみました。使う問題はこれ:ナップザック問題 | 動的計画法 | Aizu Online Judge ① 普通に普通の 埋めDP まずは普通に本 *1 で学習したナップザックで解きます。 定義 dp[ i …

ABC015 D - 高橋くんの苦悩|AtCoder

D - 高橋くんの苦悩 を解きました。 題意 この問題は良くある knapsack 問題に置き換えて考えられる為、本当の題意は省略します。 与えられる変数と値は以下のように置き換えて考えます。 … knapsack の容量 … 与えられる荷物の数 … knapsack に詰めれる荷物…

Max値取得|動的計画法( DP )

動的計画法 ( DP )の学習として解きました。 例題のねらい:動的計画法におけるメモ配列とDPテーブルの違いを確認する。問題: 要素の int 型配列 が与えられる. の最大値を DP で求めよ問題制約は特になかったので、適当に。( くらい?) 1. メモ化再帰編 …

2017年 進捗大反省会

昨年同様、今年1年の振り返り記事を残します。 独り反省会なので反省をポジティブにしていきます。 C++ について C++を勉強しだして2年が経ちました。 まだまだ知識が浅く、基礎的な事も解らなかったり、知識が定着していなかったりするので、 猫C++ をもう…

二分法( 二分探索 )で平方根を求める

二分探索の練習をしました。 追記:二分探索と書いたけれど、正しくは二分法 *1 かも知れない...。 追記②:正しくは二分法だった... 整数 および 実数 が与えられるので となるような を絶対 or 相対誤差が となる精度で求めてください。 #include <bits/stdc++.h> using na</bits/stdc++.h>…

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

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; boo</tuple<int,>…

ABC072 - C Together|AtCoder

C: Together - AtCoder Beginner Contest 072 | AtCoder を解きました。 題意: 長さ の整数列 が与えられます。 に対し、1 足すか、1 引くか、何もしない、の 3 つの操作が選べるので、ある整数 を選んだ時、 となる の個数の最大値を出力する。 は整数 考…

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

この記事は macOS Sierra バージョン 10.12.6, X-code Version 8.3.3 での設定方法です。X-code で競プロのテンプレートを読み込む設定に苦労したので自分用にメモ。 結論からいうと簡単にできた。 はじめに 設定の前に確認。 X-code Project は Mac OS の C…

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

ターミナルから MacVim で新規ファイルを開く時、競プロのテンプレートが書かれたファイルを読み込む設定をしたのでメモ。 1. テンプレート準備 表示させたい競プロのテンプレートのみを書いて、任意の名前を付け、拡張子を .cpp にしてどこかに一旦保存して…

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

No.52 よくある文字列の問題 - yukicoder を解きました。 題意: 文字列 が与えられる。 の先頭または末尾から 1 文字取り、順に繋げて新たな文字列を作る。 先頭または末尾から 1 文字取った は、また新たな となり文字が無くなるまでこの操作を繰り返す。 …

English Sentence|AOJ| Volume0-0029

単語の出現頻度 | Aizu Online Judge を解きました。 題意: ・英文が与えられるので、「出現頻度が最も高い単語」と、「文字数が最も多い単語」を出力する。 ・与えられる英文は半角英文字で、半角スペースを含む。 ・文章の文字数は1000文字以下 ・一つの単語の…

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 ・整数 が与えられるので、 が…

std::equal_to|C++|STL

STL

std::equal_to の覚書C++日本語リファレンスによると下記の通り↓ メンバ変数を持たず、状態を保持しないとのこと。 equal_toクラスは、等値比較を行う関数オブジェクトである。*1 equal_to()( left, right ); で、指定した型による left == right の比較が行…

std::function|C++|STL

std::function(C++11) の覚書C++日本語リファレンスによると下記の通り↓ functionクラステンプレートは、パラメータの型リストArgTypes...、戻り値の型Rに合致する、あらゆる関数ポインタ、関数オブジェクト、メンバ関数ポインタ、メンバ変数ポインタを保持…

No.7 プライムナンバーゲーム|yukicoder|メモ化再帰

No.7 プライムナンバーゲーム - yukicoder を 1ヶ月半 かけて解きました。 (何故 1ヶ月かかったのかは後述) 題意: ・はじめに先攻プレイヤーに自然数 N が与えられます。 ・N以下の素数のどれかで減算し相手に渡す、を先攻・後攻で交互に繰り返し、 N が 0 …

No.476 正しくない平均|yukicoder

No.476 正しくない平均 - yukicoder を解きました。 std::accumulateの戻り値の型 にはまったのでメモ。 #include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int main() { int N; long long A; cin >> N >> A</bits/stdc++.h>…

ABC045 - B 3人でカードゲームイージー|AtCoder

B: 3人でカードゲームイージー / Card Game for Three (ABC Edit) - AtCoder Beginner Contest 045 | AtCoder を解きました。題意: ・Aさん、Bさん、Cさんの3人でするカードゲーム。 ・Aさんのターンからゲームは始まり、各自持っているカードに書かれてい…

KUPC2013 A - 旧総合研究7号館|AtCoder

A: 旧総合研究7号館 - 京都大学プログラミングコンテスト2013 | AtCoderを解きました。題意: ・N個の改名後の校舎名と改名年度と、資料が作成された年度Qが与えられるので、 Q年度の校舎の名前を出力する。 ・平成元年度の校舎名は "kogakubu10gokan" ・1 …

C++で多倍長整数!

C++で多倍長整数が使える事をコンテスト中に知ったのでメモ。 でも標準ライブラリではなく、boost (オープンソースライブラリ) を使う様です。参考)Chapter 1. Boost.Multiprecision - 1.53.0 参考)多倍長整数 - boostjpcpp_int はメモリが許す限り無限の…

WUPC2012 A - 招待状|AtCoder

A: 招待状 - WUPC 2012 | AtCoderを解きました。 #include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int main() { vector<int> M{ 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; int MM1, DD1, MM2, DD2</int></bits/stdc++.h>…

2016年 進捗大反省会

今年の振り返りをカテゴリ別に書き残そうと思います。 C++ について: C++ を勉強し始めて、1年が経ちました。 春頃に range-based for *1 を覚えてから何故か劇的に C++力 が伸びました。 一気に vector, map, set などのコンテナを使える様になって出来る…

SRM 602 Div2 Level-1 250:TypoCoderDiv2

SRM 602 div2 250:TypoCoderDiv2 を解きました。題意: TypoCoderには2種類の Rating がある。 Brown ➡︎ 1200以上 Ciel ➡︎ 1200以下 ただし新しい参加者は Rating 500 スタート。 N回分のコンテスト参加後の Rating が与えられるので何回色が変わったかを出…

C++で素数列挙!エラトステネスの篩 編

C++で素数列挙!O( N√N )編 を書きましたが、 今度はもっと高速な エラトステネスの篩(ふるい)編 *1 を書いたのでコードを残します。 #include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int N; //エラトステ</bits/stdc++.h>…

C++で素数列挙!O( N √N )編

以前、C++で素数判定!を書いたのですが、 今回は C++で素数列挙!O( N √N ) のコードを書いたのでメモとして残します。 #include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int N; vector<int> P; void prime( co</int></bits/stdc++.h>…

Sum of Integers|AOJ|深さ優先探索(DFS)

深さ優先探索(DFS)を勉強中で、DFSを使って解ける優しめ問題という事で、 整数の和 | Aizu Online Judge を解きました。<題意> 0 〜 9 の数字から異なる数をN個取り出して、和がSとなる組み合わせが何個あるか出力する #include <bits/stdc++.h> using namespace std; str</bits/stdc++.h>…

ICPCOOC 2016 - A Rearranging a Sequence|AOJ

ICPCOOC2016 - A Rearranging a Sequence を解きました。<題意> ・N個の整数の中から、M個の整数を移動(TOPに積む)する。 ・移動する整数M個は e[ i ] で与えられる。 ・移動後の並びを出力する。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(in</bits/stdc++.h>…

cpp macro template - 2 -

型で事故り、マクロtemplateを修正したのでメモ。 out #define SORT(x) sort((x).begin(),(x).end(),greater<int>()) out #define SORTP(x) sort((x).begin(),(x).end(),greater<pair<int,int>>()); in #define SORTR(x) {sort(begin(x),end(x));reverse(begin(x),end(x));}</pair<int,int></int>