競プロ雑メモ

貪欲法

雑な解釈

愚直に繰り返すだけ！

使用感

とりあえずこれで挑戦してみるのがいい気がする
ざっくり見積もりで10の4乗くらいまでだったら使う感じかな？

順列の操作

関数紹介

#include<algorithm>をインクルードすると使える
next_permutation(vector.begin(),vector.end());

説明書

• 昇順ソート済みの順列のみ使う
• do whileで回す
• 辞書順に並べ替えてくれる

雑な解釈

辞書順最小を求めろってキーワードがあったら
貪欲法でぶん回せば求まる

使用感

結構使いそうだよねFor文でどうやんだ？ってのが一発で解決したよ

シミュレーション問題

Atcoderをつくる

ACとWAがあって、ACを取るまでに何回WAしたか

引っかかったところ

同じ問題を何回ACしても1カウントというところ

解決策と反省

しっかりと問題、ACか WAを再現するデータを作らなければいけない

ソート

関数紹介

#include <algorithm>お馴染みのやつ
vectorの中の並び替え
昇順
sort(v.begin(),v.end());
降順
rbeginとrendになる

雑な解釈

入れ替わる

使用感

なんかアルゴリズムってかんじ
これはこれで仕組みを勉強しなきゃなあ

型

困った…非常に困った

雑な解釈

10^{9}

この数にピンときたら
long int

使用感

ロングローング

Map

関数紹介

#include <Map>で使えます
連想配列っていうらしい
特徴は要素の要素数に対する対数オーダーでの高速な検索能力
らしい...しらんがな

使い方

std::map<キー、バリュー>って感じです
キー：社員名
バリュー：サラリー見たな例が多かったです。

雑な解釈

Stringがキーとして入れれるので便利だと思う

使用感

便利

ドブ沼にハマった

for文でやらかした

N回入力が行われるループの中でビンゴカード(2次元配列)に
同じ要素があるかのループにて
N回入力のループ
縦と横の2重ループの3つのループ
カウンターの添字をi,j,kでを使っていたところ無事爆死

対策

もう少しわかりやすいカウントの変数を作る