問題 結果 解法 準備 要約 ベースとなる乱択アルゴリズム MCTS を使う動機 MCTS を使う上での課題 工夫の一覧 ブロックの方向をシルエット被覆面積が多い1方向に限定 MCTS のノードを「ブロックの体積」「ブロックの位置」に分割 ブロックの開始位置の片方を…

はじめに 先日行われたRECRUIT 日本橋ハーフマラソン 2022夏(AHC013) に参加しました。自分にしてはいい順位を取れたので、 嬉しかった記録ということで参加記を残します。 問題 atcoder.jp 成績 最終 2000 テストケースで 13,808,196 点 (平均 6904 点)、 1…

記事の概要 「まわしてそろえる」とは、第3回 RCO日本橋ハーフマラソン 本戦Bの問題です。 atcoder.jp本記事は、以下のmaspy さんの記事を見て復習していたのですが、コストの効率的な導出をきちんと理解するために、ちゃんとゴリゴリと式展開をした過程をメ…

問題 www.codingame.com いなにわさんのわかりやすい日本語訳があり、ありがたく利用させてもらいました。 inaniwa.hatenablog.com 結果 Gold 1116位でした。 もうちょっと頑張りたかったけど、何もわからなかったのでどうしようもない。 やったこと 1日単位…

問題 結果 やったこと 自明解 自明解の改善① 自明解の改善② 考察 アルゴリズム選択 最大の長方形を置き直す 制約違反をしても OK な方法 局所解を脱出する方法 やり残したこと 所感 問題 atcoder.jp 結果 70 位でした。1ケースだけ TLE していたらしく、少し…

はじめに やったこと 3次元ベクトルを Expression Template 化 ポリゴンの当たり判定を正規化した空間でやる(名前がわからない) 三角形をなさない polygon の除去 Top Down な SAH ベースの BVH の並列構築 std::stable_partition を使った O( n log n ) 構…

はじめに この記事は、レイトレ合宿7 アドベントカレンダーの記事です。 様々なタスクをマルチスレッドで処理するために Task Queue を使う場合があります。 OpenMP 等のように気軽に並列化できる処理もたくさんありますが、例えば BVH を構築する場合、 こ…

要約 はじめに 本番前 5月 6月 7月 8月 本番 初日 2日目 所感 要約 レイトレ合宿6 に参加した めちゃくちゃ面白かった アセットは適当に作っても美しくならない はじめに 9/1(土)〜2(日)にかけて、レイトレ合宿6 に参加してきました。最終的に、僕はこんな絵…

要約 BVH のような AABB を用いた Polygon 管理用のデータ構造と、複数の Ray をまとめた Ray Packet の交差判定を高速化する方法を調査した [Overbeck 08] Ray Packet 内の Ray が 1つでも AABB と交差するか否かを基準に、 幅優先探索(BFS) により BVH の…

だいぶ遅れてしまいましたが、自分の記録用に書きました。 先日、 Weathernews Programming Contest (お天気コン)に参加しました。 wn2017_1.contest.atcoder.jp 結果は4位でした。全体的にかなり強実装なのが辛かったですが、動くenc/decを初めて作ったし超…