doubleの基数ソートができないといつから錯覚していた？
Fastest道を志す方なら、整数のソートには基数ソート(radix sort)が有力だという事を知っていると思います。実際、32bit整数のソートなら普通にstd:sortに任せるよりかなり速いです。今回の記事は整数のソートに基数ソートを用いるのは当然として受け入れてもらった上で、(正の)doubleについても基数ソートができるよという話をします。それに加えて、競技プログラミングでありがちな正整数a,bが1<=a,b<=1,000,000,000という制約下での(long double)b/aのデータを64bitに無理やり詰め込んで基数ソートができそうだという報告をします。
ではまずdoubleで基数ソートができるという話です。doubleというデータ型のbitごとの内部表現を見てみます。64bitの内訳は以下になっています。
・1 bit (63番目のbit) 正負の表記。正だと0、負だと1。
・11 bit (52-62番目のbit) 指数部
・52 bit (0-51番目のbit) 仮数部
このうち指数部の11bitの中身はまんま整数と同じルールで書かれています。仮数部の52bitも小数を2進法で表したものになっており、この52bitの大小関係も上位bitから確認すれば大丈夫です。そして上位が指数部、下位が仮数部になっているので、最上位の正負を表す1bitを除いた部分は内部表現としては整数と同様に上位のbitから確認すれば大小比較できることが分かります。
で、どうやってdoubleを基数ソートするの？と思うかもしれませんがこれは単にdoubleのbitの内部情報を保ったままlong longに入れてしまうだけでとても簡単です。
typedef long long ll; int main() { int N; cin >> N; ll A[200001]; for (int i = 0; i < N; i++) { int a, b; cin >> a >> b; double d = (double)b / a; A[i] = *(ll*)&d; } }
「*(ll*)&d;」の部分でdoubleのbitの内部情報を保ったままlong longに入れています。&dでdoubleのポインタを持ってきて、(ll*)でそれをlong longのポインタに変換して、*でポインタの中身をlong longとして取り出しています。これによりdoubleが正であれば大小関係を保ったままlong long A[]にデータが入っているので基数ソートができます。ソートした後、逆に*(double*)(A + i)といった具合に書けばA[i]をdoubleとして値を取り出せると思います。
doubleが負の場合は残念ながら場合分けをしてやるしかありません。long longの場合は負でも最上位の正負bitだけを反転させれば全体の大小関係が正しくなりますが、負のdoubleは指数部と仮数部で絶対値を表しているようなのでうまくいきません。
続いて、正整数a,bが1<=a,b<=1,000,000,000という制約下での(long double)b/aのデータを64bitにうまく詰め込んで基数ソートができそうという話です。
1,000,000,000は2^30弱なので、b/aという割り算の結果の大小関係を表現するには60bitの精度が必要です。再度doubleの内部表現を見ると、仮数部が52bitなので精度が足りません。単純な対策として知られるのがlong doubleを使う方法で、これは15bitの指数部と64bit(実質63bit)の仮数部なので、60bitの精度という要求をクリアします。今回は(long double)b/aを基数ソートしたいのですが80bitのlong doubleは64bitのlong longに収まらず、80 bit分を2つの整数にまたがって管理・比較すると基数ソートに時間がかかるようになり、他の方法に対し速度的な優位性がなくなっていくうえ煩雑です。(他の方法はa,bを整数ペアのまま保持して比較関数を工夫してstd:sortにかける方法を想定しています。)
そこでまずは64bitに収めるため仕分けをします。まず正負bitは仕分けします、これで1bit稼ぎました。次にdoubleの指数部は11bitが使われていますが、今回は1e-9から1e9までの小数なので2^-30から2^30までの範囲の指数ということで整数60=30+30が表現できるよう64=2^6で、指数部が6bitあれば十分です。この工夫により仮数部に58bitが使えることになりましたが、今回の要求精度は60bitと見積もっており、実際に実験してみるとやっぱり最悪60bit必要で不足でした。
そこであきらめず訳が分からないコードを書くのがFastest道ということで、場合分けをします。精度が60bit必要な最悪ケースというのはAとBがともに1e9の近辺のときに限られるので、(long double)B/Aはほぼ1です。つまり、最悪ケースを考えて精度を高める必要があるのは指数部の絶対値が小さい時であり、指数部の絶対値が大きくなったら精度は下げてもよい(仮数部のbit数を減らしてもよい)という事になります。60bitを仮数部に捧げると指数部は4bitしかないため16種しか値をとれませんが、16種の指数部のbitパターンのうち最小の0000と最大の1111のときは精度を下げ(仮数部のbit数を減らし)、6bitの長さの第2指数部を持つようにします。
つまり、
〇最上位4bit(第1指数部)が0000でも1111でもないとき、
・4 bit (60-63番目のbit) 第1指数部 (0001から1110までの14種の数字で絶対値の小さい指数を表現(-6~+7))
・60 bit (0-59番目のbit) 仮数部
〇最上位4bit(第1指数部)が0000もしくは1111のとき、
・4 bit (60-63番目のbit) 第1指数部 (0000もしくは1111)
・6 bit (54-59番目のbit) 第2指数部 (本来の-30から+30までの指数を表現できる)
・54 bit (0-53番目のbit) 仮数部
これにより「上位bitから比較すれば大小が分かる」という条件を保ったまま、指数部の絶対値が小さいとき60bitの精度を持ち、指数部の絶対値が大きくなると54bit精度に切り替えるのが実現できるという寸法です。第一指数部の絶対値が6とか7とかまでしか表現できませんが指数部で2^6=64倍動けば要求精度はそのまま6bitほど減りますのでちょうどうまい具合に収まります。
正のlong doubleを無理やりunsigned long longに入れ込むコードを示します。
typedef unsigned long long ull; ull ld2ull(long double LD) { ull A = *(ull*)&LD ^ 1ull << 63; ull B = *((ll*)&LD + 1) - 16352 & 63; if (B >= 39) return 15ull << 60 | B << 54 | A >> 9; else if (B <= 24) return B << 54 | A >> 9; else return B - 24 << 60 | A >> 3; } int main() { int N; cin >> N; ull A[200001]; for (int i = 0; i < N; i++) { int a, b; cin >> a >> b; long double LD = (long double)b / a; A[i] = ld2ull(LD); } }
こちらではビットシフトの演算子を使うのでAにlong longでなくunsigned long longを使っています。Aは内部表現を変えてしまったのでこれを小数に戻すのは面倒です。Fastest上、いつか必要に迫られたらやるかもしれませんが今回はA自体を浮動小数点数に戻すコードは考えません。どちらかというと、このAと必要な情報(元配列のindexや元のa,bなど)をペア等にしておいて、Aのbit情報に従い基数ソートすることを応用として想定します。速度の面で考えると、long doubleの割り算や64bitの基数ソートのせいで爆速というわけではありませんが、それでもstd:sortに比べれて速くなる可能性を秘めております。
少しコードの説明をします。*(ull*)&LDは先ほどと同様の処理ですが、80bitの情報を64bitに入れるのでlong doubleの下位bitである仮数部64bitだけがそのままでてきます。long doubleの仮数部はdoubleと違って最上位bitは常に1になっていてその一つ下のbitからが目的のbitなので注意です。*((ll*)&LD + 1)で取り出しているのが指数部です。0-63までの値に収めるために引き算などをしています。
DFSを再帰を使わずに書いて数msを捻りだす回
年末なので文字を書いて生きた証を残しましょう。記事タイトルの時点でしょうもないFastestメモですが頑張りましょう。
C++で、木のDFSって再帰関数で簡単に書けますよね。
以下に、ある根からDFSを始めて「自分の親の頂点」と「自分以下の部分木の頂点数」と「自分と根の距離」を記録するDFSをてきとーに書きました。
const int VN = 100100; vector<int> edge[VN]; int parent[VN], subnum[VN], dist[VN], d; int dfs(int u) { int ret = 1; dist[u] = d++; for (int v : edge[u]) { if (v != parent[u]) { parent[v] = u; ret += dfs(v); } } d--; return subnum[u] = ret; }
頂点0があったら壊れそうですね。あと辺を大量のvectorで持っていますがこれは遅いので私がFastestやるときは絶対やりません（何）。
まぁ本筋は再帰でDFSを書くのは簡単ということです。
で、今回はですね。再帰を使わずに配列とかwhileとかでDFSをやろうという話です。
再帰でDFSを書くと、プログラミング言語さんがメモリとか自分で確保しながらうまい具合にやってくれるのだと思いますが、それに頼っていてはFastest道を究めることはできません。配列などを使って自力でDFSを書くと数msを捻りだすことができます。この数msは世界の役に立つことはないかもしれませんがFastest道には必要なものです。
(もう少し細かくこの数msの話をしますと、再帰で書いた場合と配列で書いた場合で実行時間の差が大きくなるのは再帰が深くなる時です。木が一本の長い構造の時に差が大きくなります。再帰が浅いときは実行時間の差はほぼありません。頂点数が多くて一本の構造の時この差は10msにも近づきます。)
上に書いた再帰のDFSは「自分の親の頂点」と「自分以下の部分木の頂点数」と「自分と根の距離」を結果として記録するDFSですが、以下の処理の代表例とできると思いチョイスしています。
・親から降りてくる情報に基づいて計算できるもの
・子から吸い上げてくる情報に基づいて計算できるもの
・(オイラーツアー的な)行き帰りの探索順に沿って計算できるもの
再帰を捨て配列で書くと頭が爆発するかもしれませんが、今回の例を頑張って応用すれば配列でDFSは必ず実現できるはずです。頑張っていきましょう。
const int VN = 100100; vector<int> edge[VN]; int parent[VN], dist[VN], subnum[VN], d; int Q[VN], q; int main() { Q[q++] = 1; while (q) { int u = Q[q - 1]; if (u > 0) { dist[u] = d++; Q[q - 1] = -u; subnum[u] = 1; for (int v : edge[u]) { if (v != parent[u]) { parent[v] = u; Q[q++] = v; } } } else { d--; q--; subnum[parent[-u]] += subnum[-u]; } } }
解説はコメントでやるといい気がするので、もっかいコメント付きで載せて解説とします。
const int VN = 100100; //本当にFastestを目指すときは辺をvectorで書いてはならない。 vector<int> edge[VN]; int parent[VN], dist[VN], subnum[VN], d; //以下が追加。stackの代わりの配列。ここはvectorで書いてもよさそう。 int Q[VN], q; int main() { //stack代わりの配列に頂点1を追加。(今回は1が根。) Q[q++] = 1; //stack代わりの配列に残っている限り探索継続。 while (q) { int u = Q[q - 1]; //stackの最後の要素(u)が正のときは、行きの処理。 if (u > 0) { //stackの最後の要素(u)を負にして次回が帰りの処理になるようにする。 Q[q - 1] = -u; //行き帰りの探索順で行う計算の行きパートはここ。 dist[u] = d++; //子から吸い上げてくる情報を初期化するのはここ。 subnum[u] = 1; for (int v : edge[u]) { if (v != parent[u]) { //親からの情報による計算はここがおすすめ。(親uと子vが定義済みのため。) parent[v] = u; Q[q++] = v; } } } //stackの最後の要素(u)が負のときは、帰りの処理。 else { //stackの最後の削除。配列なら最後尾の番号減らすだけでよい。 q--; //行き帰りの探索順で行う計算の帰りパートはここ。 d--; //子から吸い上げてくる情報による計算はここ。(親に渡す。) subnum[parent[-u]] += subnum[-u]; } } }
正と負で行きと帰りを分けているので、こちらも頂点0が入ってくると壊れます。
子から吸い上げてくる処理をするにはparentの情報が必要になります。今回のように配列を別途用意するか、もしくはQ(stack)をintのpairにしたり64bit整数にしたりして、親の情報を入れ込むのも面白いかもしれませんね。
DFSがstackで実装できるのは常識かもしれませんが、再帰で書くと簡単に書けるため、再帰を使わずにDFSしているのを見かけることはほとんどありません。
競プロのコンテスト本番では当然再帰を選ぶことになりますが、Fastest道に手を出すとこんなところにも一手間かける必要がある、というお話でした。
64分木で集合の最小値を高速でみつける
あるときABC218GのFastestをみたらtatyamさんが取っていました。中身を見たらよくわからないデータ構造を使っていて、どうやらnoshi91さんのものであるようでした。
Submission #25860371 - AtCoder Beginner Contest 218
コードを見たり検索したりして、どうやら「64分木」なるデータ構造のようだとわかりました。
雰囲気は理解した気になったので、集合の最小値を高速でみつける64分木らしきクラスを書き、無理やりABC218GのFastestを取りました。
Submission #27488760 - AtCoder Beginner Contest 218
tatyamさんの提出を見ると、64分木では本来は「指定範囲内での最小値」とかも読めるようで、64分木の部分はtatyamさんのほうがエレガントで高速のように思えます。(私の入力とソートが高速で結果的にFastestが取れている)
とりあえず今回は、集合全体の最小値を高速でみつけるだけのクラスを書いたので、メモとして残します。
以下が私が書いたクラスです。
typedef long long ll; class hoge { public: ll A0, A1[1 << 6], A2[1 << 12]; hoge() : A0(), A1(), A2() { } void push(int a) { A2[a >> 6] |= 1ll << (a & 63); A1[a >> 12] |= 1ll << (a >> 6 & 63); A0 |= 1ll << (a >> 12); } void erase(int a) { A2[a >> 6] ^= 1ll << (a & 63); A1[a >> 12] ^= (ll)!A2[a >> 6] << (a >> 6 & 63); A0 ^= (ll)!A1[a >> 12] << (a >> 12); } int top() { int ret = __builtin_ctzll(A0); ret = ret << 6 | __builtin_ctzll(A1[ret]); ret = ret << 6 | __builtin_ctzll(A2[ret]); return ret; } }
ほぼ全てがbit演算子という頭が悪いクラスで、if文すら存在しないのでかなり高速だと思われます。
関数は、push(int)とerase(int)とtop()があります。
push(int)では0から262143(2^18-1)までの整数を入力し、集合に加えます。
erase(int)では整数を集合から取り除きます。erase(int)は集合に存在しない数を指定すると壊れます。チェックする機能は持たせていません。
top()では集合にある一番小さい整数を出力します。集合に何もない場合何が返ってくるかわかりません。
入力する整数の大きさに制限がありますが、priority_queueのように使うことができて高速です。しかも任意の要素が削除できるのでその点だけはpriority_queueよりも高性能です。メモリも4000個ちょいのlong longなので省メモリです。もしsortに自信がある方なら、座圧してこのクラスを使ったほうが高速になる可能性を秘めていると思います。
記事はここまでで良いように思うのですが、64分木について少し追記します。
2分木は親が2個の子を持つ木ですが、64分木は64個の子を持つ木です。64を選んだのは例によってlong longが64ビット整数だからで、ビット演算を用いれば立っているビットのうち一番左のビットは何ビット目？といったことが高速にわかります。
よって、部分木に1つでも整数がpushされているとき対応するビットが立つようにしておけば、根からたどって高速で最小値をみつけられます。
深さが1増えると64倍になるので、3回辿るだけで200,000以上の整数まで対応できるのが強いです。
密なグラフの最短経路探索
もう競技プログラミングは引退気味かなと思いつつ、それならFastest Submissionをそれなりに頑張った私の工夫とか公開していけば誰かの役に立つんじゃないのと思って、記事を書くようにしようと思いました。
ABC218のFで、頂点400の密なグラフで高速にBFSができた気がするので、この記事にメモ程度に残します。
Submission #27464352 - AtCoder Beginner Contest 218
まず密なので、隣接行列で辺を管理します。
単純な隣接行列では400*400のテーブルで辺の有無を管理しますが、今回はlong longの64ビット単位で計算して高速化を目指します。
そこで以下のような感じで頂点uから頂点vへの辺をまとめました。
long long E[400][7] = {}, vis[7] = {}; for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; E[u][v >> 6] |= 1ll << (v & 63); }
7は400 / 64の切り上げです。
さらに、頂点にすでに訪れたかどうかも”long long vis[7]”のビットごとに割り当てて管理することにします。ただ、ここまでだと省メモリくらいの効果しかありません。
ある頂点uから辺をたどるとき、隣接行列だと単純な方法では行先のN(=400)頂点への辺があるか一つずつチェックすることになりますが、ここを高速化します。
for (int i = 0; i < 7; i++) { long long t = (E[u][i] | vis[i]) ^ vis[i]; vis[i] |= t; while (t) { Queue.push(i << 6 | __builtin_ctzll(t)); t -= t & -t; } }
BFSを想定して行先をQueueにpushするように書いています。
ポイントはいくつかあります。
"long long t"は「辺E[u][i]にはあるが、vis[i]にはない」つまり未訪問の頂点のビットが立っている状態になっています。
"while(t)"は「未訪問の頂点が残っているかぎり」となります。
"i << 6 | __builtin_ctzll(t)"は、tの立っているビットのうち最下位のものを頂点番号に戻したものです。
"t -= t & -t"は立っている最下位ビットだけを0にする魔法です。Binary Indexed Tree (Fenwick Tree)で見かけた方もいると思います。
これで綺麗に未訪問の頂点へ向かう全ての辺をたどれます。
肝心の速度はどうなっているかというと、
多くの頂点が訪問済みの場合、7(N / 64)回のループとt=0の確認だけになるので、単純な方法でN回ループするより高速です。
多くの頂点が未訪問の場合、未訪問を見つける度に演算を挟むので当然その瞬間は遅いですが、この未訪問への訪問は全体を通して高々N回しか起こりません。ゆえにこの処理は全体の計算量を悪化させません。
これでいい具合に現時点のFastestはとれました。
ARC025 D コンセント
古いARCの問題はそもそも挑戦者が少なく、挑戦して回るとふいにFastest codeが取れたりする。
それに気をよくした中級者が勘違いをして解説をしようとする。そんなお話。
(追記:この記事はuzzyが競プロを始めて半年程度のときに書いた記事で、まだFastestも数個程度でした。)
この問題はそもそも結構難しくて、4年以上前の問題だけど歴代でも数十人しか解いていない模様。私も例外ではなく一度降参して、解説をみてもピンと来なかったので次の問題を埋めに行った経緯があります。
しかし先日不意にクリックして考察して、解説をみたらピンときたので「俺は神だ」と自己暗示しながら、しかし3時間近くかけてACしました。
AC後に「難しい問題が解けたなぁ」と満足げにちょいちょいコードをいじって提出を重ねるとだんだん実行時間が短くなって、なんだかFastest codeが取れました。
私が取る前のFastestはコンテスト中の最初のACコードだったようなので、化け物だなぁとしか思えませんね。
縦に最大2行、横に最大10^11列の穴が並んでいて、縦か横に連続した二つの穴を使ってコンセントを差し込むとき、その差し込み方の組み合わせの総数を求める問題。
解くにあたり以下のワザを使いました。
・全体的には「DP」で数え上げました。
・「座標圧縮」しました。
・DPの漸化式を行列で書いて、「ダブリング(繰り返し二乗法)」で行列累乗を高速化しました。
・一点更新の、一番基本的な「Segment tree」で仕上げました。
では頑張っていきましょう！
まずDPで数える方法を考えます。色々ありそうな気がしますが、私が思いついたまま書きます。
順番に一列ずつ見ていくとして、縦が最大2行なので、一つ手前の列の穴の状態は両方空き、下が空き、上が空き、両方埋まり、の4つです。
つまりDPとしては4つの数を伝えていけば数え上げられます。
コンセントの指し方は、今の行だけでおさまるか、今の行と前の行にまたがるものを毎回数えます。
まずコンセントキャップ無しでパターンを考えましょう。計5種類です。
(迫真のマウスペイント)
この5種類をうまく勘定すればいいわけですね！
i列目まで見たとき数え上げてきた数4つとして、両方空きをdp[i][0]、下が空きをdp[i][1]、上が空きをdp[i][2]、両方埋まりをdp[i][3]としましょう。
上の画像を全部考えれば以下の感じになります。
dp[i+1][0] = dp[i][0] + dp[i][1] + dp[i][2] + dp[i][3]
dp[i+1][1] = dp[i][0] + dp[i][2]
dp[i+1][2] = dp[i][0] + dp[i][1]
dp[i+1][3] = 2*dp[i][0] + dp[i][1] + dp[i][2] + dp[i][3]
[i+1][0]は全て空きなので、何も置かなければ達成。問題無用で全部足せばOK。
[i+1][1]は前の行にまたがらないと実現しない。今埋める行が空いてる必要がある。
[i+1][2]も同様。
[i+1][3]は前列に関わらず縦におけるので全部足せる。さらに全部空きなら横向きに二つ置ける。
同じ感じでコンセントキャップがある場合も書けます。
上にキャップがある場合は
dp[i+1][0] = 0
dp[i+1][1] = dp[i][0] + dp[i][1] + dp[i][2] + dp[i][3]
dp[i+1][2] = 0
dp[i+1][3] = dp[i][0] + dp[i][1]
下にキャップがある場合は
dp[i+1][0] = 0
dp[i+1][1] = 0
dp[i+1][2] = dp[i][0] + dp[i][1] + dp[i][2] + dp[i][3]
dp[i+1][3] = dp[i][0] + dp[i][2]
両方にキャップがある場合は
dp[i+1][0] = 0
dp[i+1][1] = 0
dp[i+1][2] = 0
dp[i+1][3] = dp[i][0] + dp[i][1] + dp[i][2] + dp[i][3]
・・・という感じですね！
さてこれであとはこの漸化式を元に全部足し算をすればいいはずですが、最大10^11列の計算を20000回やれという今回の問題にはまだ工夫が必要ですね。
解説にあるように10^11といっても大抵の場所にはキャップはなく、キャップ無しが延々と並んでいる状態になっています。ということでダブリングが視野に入ります。
漸化式を行列っぽい並びで書いたのでキャップ無しを行列で表示するのは簡単ですね。
うん！こんな感じ！
この4×4の行列を例えばAとして、A^2、A^4、A^8、A^16・・・みたいなのを前もって計算しておいて、キャップ無しが確定の長さを2進数にして、1になってるところは掛け算してく感じ。
計算時間は行列の掛け算がO(4^3)で、10^11は二進数だと2^40くらい。つまりひとつの行列計算に64×40で2500。キャップ無し確定領域が20000個くらいで計5×10^7くらい。ということでOK！
さて、キャップ無し確定領域が一つの行列にまとめられることが分かったので、あとは20000回のキャップ付け外しの件ですね。
さらっと行列累乗つかってるわけだから当然ですけど、行列は並び順さえ変えなければ計算順は自由です。(AB)C=A(BC)です。
ということでSegment treeとか使おうというわけですね。
一番単純な一点更新のセグツリーに行列をまんま持たせて、積を各ノードに入れていく感じです。変化したところの関係するノードだけを対数時間で更新していけます。
末端のほうのノードにどの行列を割り当てるかですけど、冷静になるとコンセント抜き差しするとこの行列とキャップ無し確定の行列が交互に並んでるので、例えば奇数番と偶数番でどっちかが抜き差しするノード、とか決めるといいと思います。
ここで座標圧縮みたいなことしてます。64ビット整数のT[i]の値を入れたら左から何個目の抜き差しポイントなのか出してくれるmapとか用意するといいですね。
これでもう終わりですね。セグツリーの初期化として「抜き差しポイント間の距離-1」乗したキャップ無しの行列を偶数ノードに、まんまキャップ無しの行列を奇数ノードに入れておく。
そして左からj個目の抜き差しポイントのキャップの状態、みたいな値を持っておいてクエリに従ってキャップ状態とセグツリーを更新して、結果出力。最後の結果は両方埋まってる感じのベクトルを行列にかける。((0,0,0,1)というベクトルなので行列の右の列がでてくる)
ですがやってる最中にH=1の時のことを完全に忘れていて私はWAしました。まぁH=1は下が常に埋まっているだけなのでそのまま流用できます。ダブリングするものを下にキャップがある行列にして、最後のキャップの状態も下が埋まっている感じで初期化すれば大丈夫です。
なんだかお疲れさまでした。これまとめておこうと思ってブログ作ったのでまぁ長かったですね。
私の解法としては以上ですけど、ちょっとずつ改良したらFastestとれた件もちょいと書きます。
一番ボトルネックだったのはやはりセグツリー関連です。最初は範囲Queryも書いてセグツリーつくったんですが、よく見たら全体の結果だけ欲しいのでそんなもの不要で根のノードの行列だけ持ってくればいい。
あとセグツリーの初期化はいちいち上のノードを更新する必要はない。2*N+1個の末端の行列を入れてからまとめて上を一度更新すればいい。
行列の計算の中身は、掛け算よりmodを取るのが遅い。行列の各成分はa*b+c*d+e*f+g*hという感じだが。それぞれ10^9以下なので実は全部足しても4*10^18で64ビット整数には収まる。なので各成分一回のmodでOK。
最初の記事
ブログ書いたことないけどブログを作りました。
32歳にもなってなぜか競技プログラミングというネットゲームにハマって、AtCoderで青になったのでブログ作ってもいいかなと血迷いました。
最初の記事なので自分の紹介をします。
私のプログラミング経験は貧弱なものです。
CGIゲーム全盛期にCGIゲームの管理人をしていたのと、FLASH全盛期にシューティングゲームを作ろうとして挫折したりしていました。(10年ほど前)
その後全くプログラミングとは関係ない人生を歩んで、急に31歳の年末年始に何か新しいことをしようとVisual Studioとかインストールしました。
最初はVC++？かなにかでWindowsフォームアプリケーションを作るという感じのサイトでHello World的なことをしました。
そしてそのノリのまま、ちょうどその時微妙なマイブームだったイラストロジック(ピクロス)を解くソフトをフォームアプリケーションで作りました。それはそれで満足のいくソフトになりました。
でもそのイラストロジックのソフトもまぁ2か月やそこらで飽きて、またプログラミングから離れたりします。
しかし年末年始やお盆休みには新しいことをしようとするものです。
その次の2018年お盆休み、32歳の私はAtCoderの存在を知り、いきなりその日のビギナーコンテスト(ABC)に出たりしました。
確か初回はunratedだったのですが、A問題からエラー吐く酷い結果だったと思います。
でもなんだかんだ思ったより楽しかったのですね。
そのうち平日も毎日問題を解くようになり、レーティングも上がってなぜか半年くらいで青になって、「もう少し早く始めていたら人生違ったのかなぁ」と思う今日この頃です。
まぁそんな感じです。
私は人生適当なのでこのブログも適当ですが、なんか難しい問題解けたとか、なんか参加したとかあれば書いていってもいいかなと思っている次第です。
何卒よろしく
