2015-07-20

STLのコンパレータを外部から決定する

STL

C++のSTLはぼくがじりきでやるじっそうより「圧倒的」につおい！これは　使　わ　な　け　れ　ば　な　ら　な　い
↓
Pairを比較しｙ・・・　できねー！糞！フ○○ク！
↓
自作構造体にデータのセットとオペレータを仕込む？自分でPairの代替とか逐次つくるのはめんどい・・・

VC++ 11.0 を今使ってるけど、xstddef に　lessという構造体があって、STL上でソート等で使う比較にはlessにあるオペレータ演算子operator()を呼び出して比較の判断をしてるらしい、~~Visual studioの定義に移動がわりと便利~~
//xstddef

		// TEMPLATE STRUCT less
template<class _Ty>
	struct less
		: public binary_function<_Ty, _Ty, bool>
	{	// functor for operator<
	bool operator()(const _Ty& _Left, const _Ty& _Right) const
		{	// apply operator< to operands
		return (_Left < _Right);
		}
	};

operator()を無理やり書き換えよう！
↓
lessの部分を書き換えたら今後がやばすぎるだろ！おい馬鹿やめｒ
↓
構造体だけど : binary_function... とか書いてるので継承できるみたいなので、継承して自前でなんとかしよう
↓
オーバーライトしてoperator()を無理やり書き換えたる

こんな斜め上な方法は使う人がいないのか、わりと資料が見つからなかった
ので、メモ
今回の場合は、Pairで左の要素は昇順、右の要素は降順にしたいとしておいて決定する。lessの実装をみるとわかるように、stringでもdoubleとかデフォルトで <が実装されてれば使えるはず。自作クラス、構造体ならoperator<を作るといける。

#include <iostream>
#include <queue>

using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)


//ここからが、要点

//less の構造体を継承して
struct unti : less<pair<int,int>>
{
    //operator()をオーバーロード
    //ここでしたい計算の処理を決定する
    bool operator()(const pair<int,int>& a,const pair<int,int>& b) const
    {
        if (a.first != b.first)
        {
            return a.first > b.first; //昇順
        }
        else
        {
            return a.second < b.second; //降順
        }
    }
};



int main()
{

    //普通はテンプレートの３つ目にgreaterとか入れるけど作った構造体をいれる
    priority_queue<pair<int,int>,vector<pair<int,int>>,unti> pq;


//ここまで

    int n = 5;
    rep(i,n)
    {
        rep(j,n)
        {
            pq.push(make_pair(i,j));
        }
    }
    rep(i,n*n)
    {
        cout << pq.top().first << "  " << pq.top().second << endl;
        pq.pop();
    }
    return 0;
}

first,second をうまく並べて表示したのが下
実行結果

結局構造体の継承をしてるし実装が面倒なんだよなぁ
ただ、スニペット化さえすればなんとか・・・

ついでにC#のときだったら、comparisonとかにラムダ式をぶっこむとかすればいけた記憶がある。（~~場合によっては一行ですむ~~）

2015-07-12

E. 数 TDPC_桁DP

Typical DP Contest atcoder

Welcome to Typical DP Contest - Typical DP Contest | AtCoder

典型DP（動的計画法）コンテスト

典型とは書いてるけれども、正直なところ普通に、というより、ゲロ吐きそうなくらい難しい

これのE問題ときました^o^（日曜も終わった）
問題文
E: 数 - Typical DP Contest | AtCoder

この問題については、桁DPを使う。桁DPについては多分下のURLが詳しい
桁DP - CCS Wiki

僕のかいたこおど
Submission #447917 - Typical DP Contest | AtCoder

方針
nを文字列でキープ。　10000桁とか整数型こわれる
dpテーブル[0からn桁の最大(n = 2 なら99)までの個数][]

dp[1][0] なら 0~9までのDの倍数
dp[5][1] なら　0~99999まででDで割るとあまりが1の数

これを桁DPで求めていく。

N = 320008 を考えると
上のDPテーブルを元にすると
0~99999　のテーブルで下の3つが求められる
0~99999
100000 ~ 199999
200000 ~ 299999

途中で1や2の分だけdpの参照先をずらす

このとき、頭のsum = 3 % Dを持っておく。
頭の総和を持っておくことで、次のテーブルでの参照先のずらしに使う。

0~9999　のテーブルで略
300000 ~ 309999
310000 319999

上の条件で全部の組み合わせを数えておけば、0~319999までの数がもれることなく数え上げできる
このとき sum = (3+2)% D になっているので、
5 + 0, 5 + 1,..., 5 + 8 の各パターンがDで割り切れるか試して、最後の桁まで数え上げる

最後に 0　が含まれちゃってるのでこれは-1する。　おわり

ACした感想
133msで通ってるので、素直に答えの数え上げもテーブル化して再シミュレートしたほうが早かったのは反省。O(log_10(N)D^2 = 10^8)だから細かな高速化をしないと間に合わないのかなーと・・・
数時間かかったけど（途中で心折れたりした）、大会のランキングを見ると10分程度でできてる人がいるんだけどこれは何なのか。

2015-07-05

文字列から数値を読み込みたい人生だった

忘備録
ここらへんので手こずって今週やってたやるだけ問題に無駄に時間が掛かった感が否めない

s[i] は　charのポインタとかどーのこーので、atoiがうまく使えないし、一文字だけ抽出してあれこれできない

string s;
cin >> s;// s = "1232100";
int n = atoi(s[2]); // n = '3' とおもってやろうとしても
//n = 32100 になるとかでうまくできない、くるちい

下の方法がいい感じ, char　も結局は1ビット？の数値なので '0 'を基準化する

int n = s[2] - '0'; // このとき n = 3  , '3' - '0'をやってる
n = s[3] - '0'; //このとき n = 2

二値記号を0とか1に割り振りたいとき

int n = 3;
int m = 4;
string s1 = "LRLR"; // L と　R からなる符号
string s2 = "RRLL";
string s3 = "LLRL";
int map[3][4];

map[0][0] = abs(s1[0] - 'R')/abs('L' - 'R'); // s1[0] = 'L'ならmap[0][0] =　1, 'R'なら 0

//もし、下の場合だと、s1[0] = 'R' のときに map[0][0]が1 、'L'なら0
// map[0][0] = abs(s1[0] - 'L')/abs('R' - 'L');

//こんな感じで残りもうまい感じに変換する
//map は下のようになる
//1, 0, 1, 0
//0, 0, 1, 1
//0, 0, 1, 0

n値符号は素直にswitchとかのほうがいいのでは・・・

2015-06-30

全列挙神降臨

C#からC++に乗り換えたからいままでの記事は一体何だったのか
そもそも前の更新がいつか覚えてないあばばばばばｂ

どうでもいいけど全列挙神関数　next_permutation　が降臨したから
これはチラシの裏に書きなぐらなければならない

http://www.cplusplus.com/reference/algorithm/next_permutation/

何をする関数かというと（前提条件→）昇順にソートされた配列内のn要素の順列を順に書き出す関数

僕の勉強し始めて数日のC++力では、
next_permutation(始点のアドレス,終点のアドレス,比較用関数)
があるのは知ってるけど、
next_permutation(始点のアドレス,終点のアドレス)
しか使えないです＞＜；

あと、下のコードではこの怪しいマクロをつかってます。

#define rep(i,val) for(int i = 0; i < val; i++)

何がすごいのか
１．重複組み合わせが効率的に計算される
O(n!)だからNP困難（？？？）無理ゲー！！　で終わらせる前に、本当はうまく列挙を工夫すれば大幅に計算量をバッサリ切れる。

定式化すると、n要素を愚直に全列挙しようとするとn!だけど、もし、重複分がa1,a2,a3,...個あると、
n!/a1!/a2!/a3!/...と場合の数が減る。
なので、うまく重複分を削れることができれば、数え上げ回数がかなーーーり削減されることになる。
うまく、場合の数を絞り上げればメモ化が捗りそう

下は一次元配列の場合のシンプルな使い方

int main()
{
    int count = 0;
    int syoken[5] = {1,2,3,4,5};
    int syoken_sagi[5] = {1,1,2,2,2};

    do
    {
        count++;
        rep(i,5)
        {
           // cout << syoken[i] << " " << endl;
        }
     //   cout << endl;
    }while (std::next_permutation(syoken, syoken + 5));
    cout << count << endl;
    count = 0;
    do
    { 
        count++;
        rep(i,5)
        {
           // cout << syoken_sagi[i] << " " << endl;
        }
      //  cout << endl;
    }while (std::next_permutation(syoken_sagi, syoken_sagi + 5));
    cout << count << endl;
    return 0;
}

出力結果
120
10

重複分を無駄に計算してたら110回も余分なことをすることになってたのでこれはデカイ

下のコードは二次元配列 {{0,0,0},{3,3,3},{9,9,9}}の全列挙を試したコードで、
countがループの回数を計測してるので、出力結果が9!/3!/3!/3! = 1680 回のループで考えうるすべての場合の数え上げができてる！
重複分を無視して愚直に数え上げしようとすると、9! = 362880回のループになるので、これは　圧　倒　的　削　減
なんかよくわかんないけど array[0]で先頭のアドレス渡すとうまくいけた
なんでだろう、わからない・・・

int main()
{
    int count = 0;
    int syoken[3][3];
    rep(i,3)
        rep(j,3)
        syoken[i][j] = 3*i;
    do
    {
        rep(i,3)
        {
            rep(j,3)
            {
               //cout << syoken[i][j] << " ";
            }
            //cout << endl;
        }
        count++;
        //cout << endl;
    }while (std::next_permutation(syoken[0], syoken[0] + 9));
        cout << count << endl;
    return 0;
}

上のように２次元配列でもアドレスをうまく指定すれば、うまくやってくれるらしい
まぁ、減らせると言ってもn = 50とかになっちゃうと普通に無理
それでも全列挙の心強い味方なのは確定的に明らかで、配列のデータをエンコーディングしてキーとしてもれば、mapとかDictionaryとかでのメモ化が捗りそう（まだやってないけど）

2.実装がくっそ楽
これを自前で実装しようと思ったら繰り返しや再帰の高度なコーディングがいるけど、
do whileとか3行のテンプレでいけちゃう、知ってるか知ってないかで別ゲー

この記事の結論
~~ぶっちゃけこの記事はただの自分用のメモ、二次元配列の全列挙ができることを書きたかった~~
どーでもいいけど、do while ってゴミだと思ってたけど（リーダブルコードで読みにくいってdisられてた）ちゃんと有用なのね

2015-03-28

Atcoderの解答状況

atcoder ABC ARC

yukicoderみたいに難易度でどんな状況下知りたいなーとか思ってたら、下のサイトで見れるのを知った
AtCoder Problems

こうやって見ると
ABC:時間が無限で問題を選べばDまで行けそう
ARC:時間が無限で問題を選べばCはもしかしてのワンチャンある
くらいかなぁ・・・

超難問だからボーナス付きの101点問題で100点までとった奴が緑にならないのがｸﾔｼｲ

2015-03-24

ABC20

Welcome to AtCoder Beginner Contest #020 - AtCoder Beginner Contest #020 | AtCoder
解説スライドは下

Abc020

自分の実装（今作り始めてる幾何問題用ライブラリが入ってるけどこれは無視してね。凸包すらまだ実装できてない。）

All submissions - AtCoder Beginner Contest #020 | AtCoder

これをみてくれ、こいつをどう思う？♂

f:id:pekoon:20150324010204j:plain

400/401(ABCとしては全完といってよい)
人が少なかったのかもしれないけど、上位5%付近に食い込めたゾ(15/276)
思ったよりもここまでたどり着くのが早かったなーというのが個人的な印象
偶然たまたま運がよくうまく行った時に限界まで調子に乗って行くスタイル。３．。３．

A　やるだけ　でも、解説スライドにあったような「配列をうまく使うことで複数の条件分岐を手早く実装できる」ことはかなり勉強になる。普段からvx,vyの二次元グリッド捜査にはつかってたのに。もっと汎用性がある（ダラーッと長いifelseラッシュが驚くほどスッキリする）
「実装が楽で早く保守（デバッグ）も楽」なコーディングが最強で、これは永遠の課題になると思う。

B　java,C#とかのstring が実装されていれば余裕。これができなかったら普段の問題の標準入力すら処理できないことになる　制約条件が999の長さの文字列と勘違いしてBiginteger型使ってしまった(int型で十分)

C　最短経路長問題。H,Wが異様に小さい(10)ので、ベルマン-フォード法を何回でも回せそうってことがわかる。それに対してTがくっそでかいので「計算量をlogTに落とす必要がある。」「最大のxを求める」のキーワードから二分探索が使そうということが検討できる。
実装量が重かった。幅優先探索を使って、より小さいパスが見つかれば、そのマスで新たに再計算する方法でゴールまでにたどり着くコストを最小化（スタートからゴールの最短経路長）して、T秒以内に間に合うかどうかを判定し、二分探索すれば十分間に合った。
前に二分探索の考察を書いてスニペット作っててよかった。これ自体は普段のABCのD問題くらいの難易度あるような気がする

D　101点無理ゲー　LCM * GCD = a * b とユークリッドの互除法を知っていれば15点までは余裕。
・K=100とNに比べて圧倒的に小さいこと（なぜKが小さいなら効率的に解けるのか）
・実際にユークリッドの互除法の計算過程を手計算するなりして、例えばGCD(12,5),GCD(7,5)を計算した場合に、次の計算時には「同じく」2、5に遷移する、この先も一緒だからGCDが共通になる
・N = 10^9の膨大な値に対して定数時間O(１)で求める方法がある
ことの3つを検討すると、スライドの解説にあるような100点解法に行きつけた。
2,5,8,11,・・・の数列和の計算をするのにものすごい時間かかった。
1+2+3+4+・・・+n = n(n+1)/2 、k+k+k+k+・・・+k = kn (nは項数)を使ったのが沼（項数の計算がすごい大変だった）

スライド解説の101点解法はムリ、読んでも完全には理解できない・・・。これがいけるひとは一体どんな勉強をしてきたんだろうか・・・典型問題（？）らしい

A、BとC、Dので問題間の難易度差がちょっとアレ

2015-02-22

二分探索の終了条件

アルゴリズム

二分探索とは
二分探索 - Wikipedia

↑　こ↑こ↓に載ってる奴．昇順，降順といった制約を持っているものに対して非常に高速(O(logn))で処理できるアルゴリズムです．考え方自体はものすごいシンプルだけど，こんなのも実装できない自分が悔しい．

何が無理かというと，終了条件がよくわからない．low,mid,hiの3つがあるときどれが答えなの？いつ終了するの？結局low,mid,hiのどれを答えにすればいいの？という疑問
難しい問題になると，単体の知識問題が減って，こういう技を上手く合わせ技で使い必要があるので，ここらへんで文章書いて考えを整理したかった．前提として離散値で考えます(int,longの整数型)

パテいーん１．　よくあるソート済み配列のうまくいく場合

midで見つかったときにそのままbreakしてmidを答えとして探索を終えればいいだけ．
これはちょろいね
パテいーん2の考察に詳細は譲るとして，hi > low+1 が成立している間まで探索を続けるといい感じ．

パテいーん２．　よくありソート済み配列で答えが見つからない場合

(low,hi) = (奇数，偶数),(偶数,奇数)の場合について考える．
うまく見つからないと，hi = low+1となるような2つの要素による区間に収束する．このとき，遇，奇がどちらの場合でもmid = (hi+low)/2=lowとなるので，区間が2となるつまりhi > low+1 が成立している間まで探索を続けるといい．

パテいーん３．　競プロでの二分探索では一番頻出（だと思ってる）最大，最小の境界探索に使う
最初から，最後からの一個ずつの総当りがO(n)をかけるのに対して，O(logn)になるので，はやい．つよい　ちょっと時間削ろうとなるとシンプルな割に強力な手法だからココらへんは迷わずサクサク実装できないとつらい．

俺が解いた，見たことあるやつだとこんなのがあった↓　二分探索ができないと部分点まで突破できなかったりする．

------------------

Modular Query | Aizu Online Judge　
集合内に1とM-1の間で割り切れる要素が一つでもあるかどうかを二分探索．クエリは一個一個逐次処理するしかない．

C: データ構造 - AtCoder Regular Contest 033 | AtCoder

AtCoder Regular Contest 033 解説　僕の解説より100倍詳しくて丁寧でつよい
概要としては，セグメント木のインデックスに二分探索していく感じ．

-------------------

実はこの記事はこういうパテいーんの終了条件をどうにかしたかっただけなのでよーく考える．たい
まずイメージとして0,1,2,…,k,...,n-1までのn個の要素があるとして条件Xを満たすのは，
0からkまでとなる問題があるとしてこの最大値のkを求めてねという問題とかで二分探索を使うことになる．
配列にすると，インデックスiについて，条件Xを満たす0,条件Xを満たさない1としてみると
000....0011....11（,は省略）というような配列で0が現れる最大のインデックスi_maxは？を求める問題だともいえる．(こう書いてみるとパテいーん1,2と共通点を感じるように思えてくる)
このとき，
[1] midで0となる→low =mid　としていくことで，もっと攻めていく
[2] midが1となる→hi = mid　としていくことで，もっと抑える
として二分探索を行うことになる．
初期条件に，lowには明らかに0となるインデックス，hiには明らかに1となるインデックスを初期値としておくと，最後はlowが条件を満たす0，hiが条件を満たさない1となる2つの要素の区間に収束する．条件を満たさない最小のインデックスも求まるじゃないか(憤慨)．このときに下線部の制約条件を守らないと上の太字のようには必ずしもならないので注意．
なぜこうなるかの思考実験↓
二分探索を行っていく間ではlow,hiの区間で含まれる0の個数がa，1の個数bが初期状態となるとして，この場合だと
[1]midで0をとった場合low,mid間の0を弾く，0,1の境界が残りつつ，aの値が減少
[2]midで1をとった場合mid,hi間の1を弾く，0,1の境界が残りつつ，bの値が減少
これを繰り返していくと，究極的にはlow,hi区間でのa,bがともに1となる状態に収束することになる．

本題の終了条件をパテいーん２．の時のように考えると，hi > low+1 が成立している間まで探索してhi = low+1となったときに終了して，条件を満たす最大値はlowを答えとして，条件を満たす最小値1(の最小のインデックスを求める問題)ならhiを答えとするといいということになる．

パテいーん３についてはこれを念頭において，下のように書くとよろしい！コードスニペットに落としこんでもいいかもね

int low = 0;

int hi = max;

int mid = 0;

while(hi > low+1) // これがこの記事の答え

{

mid = (low+hi)/2;

if(条件Xを満たす(mid))

{

low =mid;

}

else

{

hi = mid;

}

パテいーん1,2については，条件Xを満たす(mid)内のブロックで return mid;

elseの方は空白

midをreturnできなければ，答えが見つからなかった旨をreturn -1;とかしてやるといい感じ
上級者の人たちだったらここらへんは思考タイム0なので慣れないと( ･`ω･´)

競技プログラミングのべんきょうきろく

ブログ名からひと目でわかる圧倒的チラ裏