競プロを武器にして完全未経験から新卒でソフトウェアエンジニアになって半年経った
競プロを武器にして完全未経験から新卒でソフトウェアエンジニアになって半年経ちましたので、振り返りも兼ねて感想をブログに記します。ソフトウェアエンジニアというにはあまりにスキルが足りないので、以下では「ソフトウェアを書く人」と表現させてください。
主なテーマは「未経験でソフトウェアを書く人になることは大変か」、「競技プログラミングは役に立ったか」、「今後」です。自分語りみたいになるかもしれないので、そういうのが苦手ではない、むしろ好きだという方には読み進めていただけたらと思います。また、業務の具体的な内容を期待される方もいらっしゃるかもしれませんが、触れませんので、予めご了承くださいませ。
自己紹介
未経験でソフトウェアを書く人になることは大変か
大変でした。 buildってなんですか。APIってどうやって実装するんですか。Javaって書いたことないけどできますか。DBって触ったことないんですけど・・・。AWS知らないのに最初がそのタスク！？
職種や配属先が入社前から決まっていたこともあり、入社後すぐにいわゆるOJTで進んでいきました。先輩方に優しくなんでも教えていただいたり、あまり重くない（多少遅延しても大丈夫そうな）タスクを割り振っていただいたりしたおかげで、なんとか生き延びました。実はいつ首を切られるかとソワソワしていたんですが、いつの間にか試用期間の3ヶ月も終わり、半年も経ってしまいました。今「完全未経験でもなんとかなる！」みたい思ってる就活生の方々におかれましては、なるべく早めにインターンなどで経験を積んでおくことをオススメいたします。責任が軽いうちにたくさん失敗しておくといいかと思いますので。TLでは結構実務経験積んでてすごいと思ってみてます。
競技プログラミングは役に立ったか
競技プログラミングが役に立つどころか、競技プログラミングがなかったらこんなに何もできない状態から食らいつくことはできなかったと思います。Javaが書けないとは言っても、文法がわかれば、ロジック自体を正確に書くのに苦労はしませんでしたし、開発経験が少ないと言っても、ソースを読んで挙動を理解する力は競プロで培われていたので、部分部分では困りませんでした。設計の経験が少なかったり、可読性に対する意識が足りていなかったために、レビューでは毎回たくさんのコメントをいただいておりますが、非常に勉強になりますし、コメントの要求を一つ残らず満たすソースを考えるのは、コンテストみたいで楽しいです（マージがAC）。確かに、競技プログラミングの要求するアルゴリズムそれ自体を使うという場面はほとんどないですが、「仕様が与えられるので、バグに気をつけて実装してください」という200点問題が大量に降ってくる実務現場は、あくまで私にとってはですが、競技プログラミングの経験なしで生き抜いていける場所ではありませんでした。ありがとう、競技プログラミング。
今後
ここまで半年、右も左も分からないことをいいことに、周りに甘え切って生きてきました。が、そろそろ半人前くらいの雰囲気で稼働したくなってきました。いろんな仕事を刈り取って、失敗しながら経験を積んでいけたらと思います。初年度、後半戦も頑張ります。
あと、3年以内にマラソンの知識を実務で活かすという野望があるんですが、このペースでは不可能そうです。どうしたらいいですか？
追記) 珍しく100いいねを超えたので、興味を持ってくださる方が多いということで、Twitter経由でご連絡していただけたら答えられる範囲で答えますので、特に情報が少ない就活生の方など、お気軽にご連絡ください。
もし競プロ経由の就活ってどんな感じですか、とか、仕事の話聞きたいとか、ありましたら、私のわかる範囲で対応しますので、DMでもリプライでもご連絡いただけたらと思います。
— naga (@long_ng_cp) September 29, 2021
2年前私が聞きたかった話とかならできると思います。
AtCoder Beginner Contest 218 ABC218 参加記
jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 218での成績：2007位
— naga (@long_ng_cp) September 11, 2021
パフォーマンス：1136相当
レーティング：1428→1402 (-26) :(#AtCoder #ABC218 https://t.co/gykafsug4z
:(
A - Weather Forecast
解説
判定します。
実装
int main() { int N; string S; cin >> N >> S; if(S[N - 1] == 'o') { cout << "Yes" << endl; } else { cout << "No" << endl; } }
B - qwerty
解説
C++ではchar型に数字を足し算をしたあと、さらにchar型にcastできます。
実装
int main() { vector<int> P(26); cin >> P; rep(i,26){ cout << char('a' + P[i] - 1); } cout << endl; }
C - Shapes
解説
実装重すぎるというか、この程度も実装できなかったの？という気持ちに。回して左上からの相対位置で判定。
実装
int main() { int N; cin >> N; vector<string> S(N), T(N); auto find_top_left = [&](const vector<string> &v) -> pair<int, int> { rep(i, N) rep(j, N) { if(v[i][j] == '#') { return {i, j}; } } return {-1, -1}; }; auto rotate = [&](vector<string> &v) -> void { vector<string> tmp = v; rep(i,N){ rep(j,N){ v[i][j] = tmp[j][N-1-i]; } } return; }; cin >> S >> T; rep(_, 4) { auto [sx, sy] = find_top_left(S); auto [tx, ty] = find_top_left(T); vector<pair<int, int>> s, t; rep(i,N){ rep(j,N){ if(S[i][j] == '#'){ s.push_back({i-sx, j-sy}); } if(T[i][j] == '#'){ t.push_back({i-tx, j-ty}); } } } if(s == t){ cout << "Yes" << endl; return 0; } rotate(S); } cout << "No" << endl; }
D - Rectangles
解説
すべての辺がx軸/y軸に平行な長方形は、a < A, b < Bとして(a, b), (a, B), (A, b), (A, B)であるということを使います。最後に2で割ると通ります。理由はわかりません。
実装
int main() { int N; cin >> N; map<pair<int, int>,int> mp; vector<pair<int, int>> xy; rep(i,N){ int x, y; cin >> x >> y; xy.emplace_back(x, y); mp[{x, y}]++; } sort(all(xy)); ll ans = 0; rep(j,N){ rep(i,j){ auto [a, b] = xy[i]; auto [A, B] = xy[j]; if(a == A)continue; if(b == B)continue; if(mp.count({a, B}) && mp.count({A, b})){ ans++; } } } cout << ans/2 << endl; }
E - Destruction
解説
多重辺、自己ループは、価値が最小の1本以外は取るか、捨てるか（無視）していいです。 以降、多重辺、自己ループのなくなったグラフで考えます。
最低でN-1本の辺ですべての頂点を連結にできます（例えば木）。言い方を変えると、それ未満の辺の本数ではグラフを連結にすることはできません。よって、N-1本は必ず使います。
グラフの辺をとっていくのはすごく面倒なのはよく知っているので、逆の操作を考えます。つまり、辺を削除して報酬を得るのではなく、変を追加する操作によって報酬を捨てていくことを考えます。こう考えると、価値の小さい方から捨てていくのが自然になります。頂点(a, b)をつなぐある辺を追加するべき（捨てるべき）か否かは、それらの頂点が既に連結かどうかで判定します。連結なら、もう一度つなぐ必要もないので、繋ぎません。連結でないなら、繋ぎます。
このようなアルゴリズムにより、すべてが連結になるまで、価値の小さい辺から貪欲に追加していくことで、今回の問題を解くことができます。UnionFindを使うことで、実行制限以内に解くことができました。
実装
int main() { int N, M; cin >> N >> M; vector<pair<ll, pair<int, int>>> es; ll ans = 0; UnionFind T(N); rep(i,M){ int a, b; ll c; cin >> a >> b >> c; a--, b--; if(a == b){ ans += max(0LL, c); continue; } if(c <= 0){ T.unite(a, b); continue; } es.push_back({c, {a, b}}); } // 報酬が小さい順に連結していく sort(all(es)); for(auto [c, ab]: es){ auto [a, b] = ab; if(T.same(a, b)){ ans += c; } else{ T.unite(a, b); } } cout << ans << endl; }
F - Blocked Roads
解説
ある辺が使えなくなった時の最短経路を求める問題。 1からNへの最短経路なので、経路で使う辺は高々N-1、というのがポイント。
まず、ある1->Nへの経路を決めます。それに含まれない辺については、あろうがなかろうが経路に変更はありません。その経路に含まれる辺が通れなくなった場合のみ、最短経路を計算し直すことで、計算量はO(N(N+M))となり、十分高速です。
実装
int main() { int N, M; cin >> N >> M; vvec<int> G(N); vector<pair<int, int>> st; vector<int> dist(N, INF); vector<int> pre(N, -1); rep(i, M) { int s, t; cin >> s >> t; s--, t--; st.emplace_back(s, t); G[s].push_back(t); } std::queue<int> q; q.push(0); dist[0] = 0; while(!q.empty()) { int v = q.front(); q.pop(); for(auto n : G[v]) { if(dist[n] != INF) continue; dist[n] = dist[v] + 1; pre[n] = v; q.push(n); } } if(dist[N - 1] == INF) { rep(i, M) { cout << -1 << endl; } return 0; } int v = N - 1; vector<pair<int, int>> tour; map<pair<int, int>, int> mp; while(v != 0) { tour.push_back({pre[v], v}); mp[tour.back()]++; v = pre[v]; } rep(i, M) { auto [s, t] = st[i]; if(mp[{s, t}]) { // 計算し直し vector<int> dist2(N, INF); std::queue<int> q2; q2.push(0); dist2[0] = 0; while(!q2.empty()) { int v = q2.front(); q2.pop(); for(auto n : G[v]) { if(dist2[n] != INF) continue; if(v == s && n == t)continue; dist2[n] = dist2[v] + 1; q2.push(n); } } cout << (dist2[N-1] == INF ? -1: dist2[N-1]) << endl; } else { cout << dist[N - 1] << endl; } } }
Bioinformatics Contest 2021 Final Roundに参加しました。
バイオインフォマティクスコンテスト2021 bioinf.me
問題文とか
Bioinformatics Contest 2021に参加しました。30位以内には届きませんでした。来年リベンジします。
簡単に方針を記します。
1. Genotype Imputation
二つの既知配列の組み合わせの中で未知配列との編集距離が最も小さいものを採用する。全探索のみ。
2. Causative Mutation
変異の頻度が多いかどうかを計算。よくわからなかったので偏差値とか使って標準化した値を用いた。ある程度絞ったら手動で二分探索すると満点が得られる。時間がなくて手動できなかった。ここで800点くらい損してるのかなしすぎ。
よく考えると計算で絞らなくても全部手動で答えが決まる。なにこれ。
3. Superspreaders
シミュレーションする。確率1のみのテストケースはシミュレーション1回で良い。 計算が重いが、寝てる間に回せば終わる。
4. Minor Haplotype
ある座標である変異が、全体で何回起こっているかを調べ、その数が有意っぽかったら採用する。有意っぽい変異が少なかったら、エラーだと判断する。有意っぽさはなにかしら標準的な値を使いたかったが、目で分布を確かめてエスパーした・・・。
5. Isoform Matching
読解が難しい。問題文を正しく理解して愚直に回せば、easyは満点が出る。6時間とか回してたけど。誰か高速化方法教えてください。 hardはうまい計算方法があるのかわからなかった。誰か教えて。
これを読んだ日本人の皆さんへ
まあまあ楽しいので次回があったら一緒に戦いましょう。
また、興味を持った方は、2021年8,9月に日本バイオインフォマティクス学会でプロコンがあるらしいので、ぜひ。
AHC004に参加しました
AtCoder Heuristic Contest 004に参加しました。
107位でした。
方針
文字列を重ねて詰め込む問題です。
簡単な考察として
- 文字列が被さったり、包含されているものは、優先的に配置したい
というのがあります。
被さりは、suffixとprefixの一致なので、dpなどを使って前計算できます。包含関係も同様です。この値を使って文字列に優先順位をつけ、配置します。
配置する場所は全て試して、他の文字列と被さりがある場合に加点します。
配置の場所は無限にあるので、時間の許す限りランダム要素を入れながら探しました。ここをもっといい感じにしたかったです。
AtCoderで青色になるまでにやったこと
AtCoder Beginner Contest 197（Sponsored by Panasonic）にて、AtCoder青色になりました。
競技プログラミング界隈の風習にならい、色変記事を書きます。
naga on Twitter: "初参加から2年半、やっと青コーダーになりました！！！！！！！！… "
水色の記事はこちら。
自己紹介
21卒の大学院生で、来る4月からエンジニア職として働き始めます。専攻は生物で、研究で必要になり勉強していたところプログラミング自体にハマって今に至る、という感じです。
最近はマラソン型コンテストにお熱で、HTTF2021予選で64位になったり、ハル研究所プログラミングコンテストで18位入賞したり、AHC001で108位になったりしました。トップには全く敵わないものの、個人的には楽しんで取り組んでいます。
精進
AtCoder Problemsのスクショがわかりやすい気がします。 令和ABC-Eは割と埋めていて、Fに手がついていません。緑diffまでは埋まっていますが、水diffのめんどくさそうなのは放置しています。青diffもたまに解説ACする、という気まぐれ精進が見て取れますね。 2020年後期からほとんど精進ができていないのは、マラソンにハマり始めたり修論で忙しかったりしたためです。修論の追い込み期間はコンテストに出るのをやめていました。
それでもレートが少しずつではあるものの伸びているのは、コンテストにはかかさず参加するという習慣を維持できたのが大きかったのではないかと思っています。コンテストで結果を出す力は、コンテスト（orバチャ）でしか養われないと思うので。
コンテスト
上述のように、AtCoderのコンテストにはほとんどかかさず参加していました。土曜の夜は何よりもコンテストを優先していました。その結果、コンテスト参加回数は122回(全体でランキングで119位)になっていました。何も考えずにとりあえずコンテストに参加するのは、モチベーションを切らさない意味でも大切だったと思います。
勉強していたこと
高校数学も競プロに関係するような範囲は苦手で、大学数学もほとんど手がついていなかったため、競プロに必要なことは競プロで学んでいます。特に、場合の数確率、整数の範囲は、段々成長しているのかなと思っています。場合の数、整数ともにマスターオブシリーズがおすすめです。苦手で困っている人は、最初の数ページだけでも読んでみると捉え方が変わるんじゃないかと思います。
勉強したことで好きな考え方は、決めうち二分探索、拡張ダイクストラ(グラフを拡張したダイクストラ）、主客転倒です。最近は形式的べき級数の考え方に魅了されていましたが、役に立てるほど身についていないので、いつかマスターしたいです。
DP
- LIS
- 耳DP
- 数え上げDP
- 木DP
- 全方位木DP
二分探索
- 決めうち二分探索
- 単調性を見つけるのがうまくなった
貪欲
- 区間スケジューリング問題
- 解法の一部に含まれる貪欲要素に気を配れるようになった(DPのときとか)
数え上げ
- 主客転倒
- 包除原理
- 期待値の線形性(というかだいたい数え上げだと思って解いてる)
- マスターオブ場合の数を読んだのがよかった
データ構造
- BIT
- セグ木
- 遅延伝播セグ木
整数関連
- 中国剰余定理
- 拡張ユークリッドの互除法
- エラトステネスの篩
- 高速素因数分解
文字列
- Suffix Array(使ったことない)
- Z-algorithm(使ったことない)
- manachar(使ったことない)
ゲーム
- Nim(XORが大事)
- 真似するやつ
- 過半数が大事
- min-max法?
グラフ
フロー
- 最大流
- 最小費用流(使ったことない)
- 二部グラフのマッチング(使ったことない)
その他テクニック
紙に考察を書くこと
コンテスト中、紙にどの程度メモしますか？
touristの精進配信をみたときに、彼らが紙には何もメモせず、画面を睨みつけながら考察しているのが印象的でした。
私は、競プロを始めたばかりの頃、メモをしないで考察するということが理解できませんでした。暗算も苦手、すべて書かないと理解した気にならない、という癖があったのではないかと思います。レッドコーダーは、簡単な問題は紙に書かないということを知って、驚いたと同時に、自分もできるのかな？と挑戦しました。最初は確かに苦しいのですが、段々と頭の中だけで動かせるものが増えていきました。今となっては、メモをすると無駄な考察が増えるばかりだなと思うことも増えました。
この紙に書かずに考察する能力は、早解きに必須だと思いますが、精進の量を増やす上でも役に立ちました。頭の中に問題をセットして、歩きながら解くということも可能になり、いつでも精進ができるようになったことで、問題を解かなければならないというプレッシャーも減りました。
2x105の数列を頭に浮かべながら生活するのも悪くないです。
レーティングを気にすること
レーティングを気にする人は多いと思います。色変記事みたいなのがあるように、400刻みには何の意味もないのに色を気にする人は多いです。
結論からいうと、レーティングは気にしても上がらないので、考えないようにしていました。
こう考えるきっかけになったのは、コドフォでした。コドフォはAtCoderに比べるとレートの変動が激しいため、レートは溶けるときは溶けるという、当たり前のことを教えてくれました。
レートが溶けるのを気にしているとコンテスト中問題以外にメモリを奪われるので、無視するのが賢明だと最近は思い込んでいます。実際ここ数ヶ月はレートの浮き沈みが激しいですが、実力が上がればいつかは戻るので、気にしていません。今後も水色に落ちたりするとは思いますが、長い目で見て実力が向上していれば問題ないという気持ちでいます。
マラソンの影響
マラソンにハマってから、実装力が格段に上がりました。マラソンは令和ABC-B,Cレベルの問題を自作して解くという流れで進むので、アルゴ型にもいい影響があったのではないかと思っています。計算量を意識して作問しなければならないので、アルゴの問題でも受け身にならずに考察を進める力がついたような気もします。何より、アルゴの競争に疲れていたとき、マラソンで自分との戦いに挑戦した結果、悩みが馬鹿らしいものだということに気づけました。みんなもやろう、マラソン。楽しいよ。
最後に
最後まで読んでいただきありがとうございました。競プロで必要になったことはその場で学び直してなんとか這い上がった人間なので、そういう悩みを抱えている人に少しでも役に立っていたらいいなと思います。
まだ伸び代はあると思っているので、黄色になるまでは続けたいと思っています。黄色になりたい理由は、マラソンでできることを増やしたい、ただそれだけです。
マラソンに興味を持った人は、以下の記事などもどうぞ。最近は入門記事も増えているので、気軽に参加してみましょう！
マラソンマッチで気をつけるべきこと
今までHTTF、ハル研プロコン、AHC、などのマラソン型競技プログラミングコンテストに参加してきました。初参加から一年以上が経ったでしょうか。個人的には普段のアルゴと呼ばれる分野のコンテストよりマラソンの方が向いている(相対的な順位がよい)と感じており、比較的力を入れてきました。
本記事では、マラソンに取り組むときに考えていることを自分の振り返りも兼ねてまとめます。
短期型では制限時間以内に実装できる範囲の中で得点の期待値が高そうなものを選ぶことが重要になりますが、今回は長期型、2週間ほどのコンテストにおける戦略にフォーカスします。
有名問題との類似性
まず問題を読むわけですが、その問題が、有名問題と似ているか考えます。例えばハル研プロコンでは、経路最適化問題が出題されましたが、上位陣の解法をみると所謂TSPの知見が多く利用されています。AHC001では、長方形の詰め込み最適化を求められましたが、これも長方形詰め込み問題と呼ばれる情報科学で有名な問題と似ていることがわかります。もちろんそのままの形式で出ることはあり得ませんが、知見が活きる可能性が高いです。そもそも出題者側には情報科学のバックグラウンドがあることは容易に想像できるため、教科書的な有名問題をもじったようなものは出題されやすいと思います。某講演でも、コンテスト期間中に論文を読みながら勉強するという話が出ていましたが、そのくらい巨人の肩に乗ることは重要だということだと思います。私自身学生時代の専門は生物学で、知見が不足している部分はありますが、情報科学に対するアンテナも常に張っておくべきだと感じています。
最も簡単な解
次に、最も簡単な解を書きます。経路最適化問題なら、直線で結ぶだけ、長方形配置なら、正方形を置くだけなど、とにかく正の得点が得られそうなものを書きます。この点数から上げていきましょう。ここで最も意識すべきことは、コードの再利用性と、拡張性です。先日の技育祭でchokudaiさんがマラソン実装の実演をしていましたが、そこでも強調されていました。最も簡単な解を得るからと言って、コードを雑に書くとすぐに後悔します。例えば長方形の配置をするなら、端の2点を入れたらセットできるメソッドを作ったり、長方形を管理する構造体も持つべきでしょう。こうすることで、余計な思考リソースを取られないようになります。向き合っている問題の中で、最も基本的な構造は何か考え、それにアクセスする回数が多そうなら、なるべくアクセスしやすいように書くのがコツです。
テキトーに書くと、改善する気がなくなります。触りにくいと、触らなくなります。最後には、触りたくても触れなくなります。私も何度も失敗して学びました。綺麗に書くと、愛着が湧きます。改善したくなります。長期型マラソンで最も大切なのはやめないことです。PDCAを高速に回すことです。2週間付き合っていくコードなので、スタートから未来を見据えて書いていきましょう。
単純な貪欲
最も基本的な解が構成できたら、山登り法や焼きなまし法を考える前に、単純な貪欲を考えます。貪欲が最も重要だと言っても過言ではないです。貪欲が弱いなら、後述する山登り法や焼きなましがうまくいくとは考えにくいです。マラソンマッチは制限時間内に全てのパターンを列挙できない問題から良さそうな一部の状態を探し当てる宝探しなのですから、闇雲に探しても見つかるわけがありません。数え上げお姉さんの二の舞になります。ある程度よいと思われるところに降りてから、探し始めましょう。
ハル研プロコンならダイクストラ法で距離を算出したり、AHC001なら目標面積目一杯、ギリギリまで広げるアルゴリズムを考えます。これだけでも十分よさそうな解が得られていそうなことに気づくでしょう。ただ、決定的アルゴリズムでは探しきれていない状態がたくさんあります。そこで、山登り法の出番です。
山登り法
山登り法は、状態にランダムな変異を入れて良くなったらそちらに進む方法です。ランダムな変異の取り方も無限にあるので、考えます。考える前にテキトーなところで手を打ってとりあえず実装するのも手です。それをベンチマークにして改善していきましょう。よく、ここで選んだ解法に固執してマラソンマッチ戦略の局所最適解に落ちてしまう人がいますが(私のことです)、無限にアイデアを試しても怒られることはないわけですから、遠慮せず解を壊しましょう。間違ってもここでパラメータガチャに走ってはいけません。パラメータガチャをするのは最後でも間に合います。稀にパラメータガチャで結果がめちゃくちゃ変わることもあるので、ある程度試す価値はありますが、固執すると時間だけが過ぎていきます。気をつけましょう。
山登り法の問題点は、局所最適解に落ちやすいことです。別にそこまでよくないのに居心地がいいから穴から出てきてくれなくなります。もっといい世界があるのに。まるでマラソン開始2日目でパラメータガチャに走る私のようです。局所最適解に落ちているかどうか判断する方法としては、実行時間を長くして、さらに解が改善するかどうかを見るというのがあります。5秒では見つからないけど、500秒で見つかるよりよい解があるなら、局所最適解に落ちてる可能性があります。救ってあげるにはどうしたらいいでしょうか。私はよく、突然変異を大きくしています。解の一部を壊して、局所最適解から逃してあげましょう。山登りなので、いい状態が見つかればそちらに向かってくれます。どういう変異を追加するべきかは、ビジュアライザをよく観察して考えます。「ここで改善できそうなのにいつまでも動かない」と思ったら改善のチャンスです。
その他
焼きなましは、局所最適解に落ちにくくなります、たぶん。焼きなましでスコアを伸ばしたことがないので言及を避けます。
以上、反省会でした。 これはあくまで個人的なメモなので、間違っていると思われる記述があったら教えていただきたいです。長期型マラソンでの注意点を意識し、楽しいマラソンライフを！
AtCoder Heuristic Contest 001 AHC001に参加しました
AHC001に参加しました。
結果は、システムテスト前最終118位、489億6千万点でした。簡単にですが、採用したアルゴリズムに関して記します。
AHC001お疲れ様でした！！！
— naga (@long_ng_cp) March 14, 2021
上から順に貪欲に面積を割り当てた初期解から山登りをしました。長方形を移動するほかに、1x1の正方形にリセットする摂動を入れることでスコアが伸びました#AHC001 pic.twitter.com/aOe3ngQE0k
アルゴリズム
- 各企業の初期位置に1x1の正方形を割り当てる(初期化)
- 各企業に長方形を割り当てる。(貪欲)
- ランダムに領域を移動し、ランダム要素を追加した貪欲を加え、解がよくなるなら採用する(山登り)
- ランダムの中である確率で、1x1の正方形にリセットする摂動を入れる(kick)
初期化
1x1の正方形を割り当てます
貪欲な長方形
まず、x, yともに両方向に同じ距離ずつ広げる正方形を割り当て、その後x, yそれぞれに関して乱数を用いてランダムに伸ばす方向を設定し割り当てる。面積は、目標を超えないように、また他の長方形と交差しないように貪欲に割り当てる。
ランダム山登り
ランダムに長方形を選び、3 ~ 200だけ移動させる。方向もランダム。これを20回繰り返す。
kick
20%の確率で、長方形をリセットする。状態を壊して局所解に落ちないようにするため。
パラメータ
パラメータは勘で選んだ。本当は検証するべき。いくつか試して、解の上昇が最もよさそうなのを採用した。
実装
貪欲の実装は、二分探索で行ったが、交差判定でO(N)かかるので、全体でO(NlogH)かかる。logがついて遅い。高速化するには、Dynamic AABB Treeというものを用いるといいらしいです。
何が最も改善に効いたか
- 貪欲時にランダム要素を含ませたこと
- kick(長方形リセット)
貪欲は決定的なアルゴリズムになってしまいがちなので、その中にもランダム要素を生やすことで、局所解から脱出しやすくなると思います。また、kickも同様で、長方形の辺の比が偏ってる場合他を邪魔する可能性があるので、高確率でリセットを行うようにしました。
改善したい点
- Dynamic AABB Treeで交差判定を高速化する
- パラメータを勘で設定しない
