スコア問題の解答の評価を行う環境をAWSで組んでいます。どのようなシステムになっているかを紹介します。 費用はそこそこ抑えられていると思っていて、AHC031での実績は 1000ケース*2秒のテスト実行を165セット行って$5くらいのコストでした。 概要 AWS Bat…

あまり広まっておらず知る人ぞ知るテクみたいになってる気がしたので。グリッド上でBFSをするときに、単純に書くとこのような感じになると思います。 bool bfs(const vector<vector<int>>& grid, int r, int c) { vector<pair<int, int>> queue = { {r, c} }; vector<vector<bool>> visited(H, vector<bool></bool></vector<bool></pair<int,></vector<int>…

HACK TO THE FUTURE 2022 本選 に参加して、2位になりました。 このコンテストで高いスコアを取っていた参加者の多くが、「右手法や左手法を実現するコマンド列を作って、その繰返し回数の組合せを探索する」という解法でした。 c7c7さん terry_u16さん chok…

画像は AtCoder Marathon Rating History より AHC 001〜005 の5回連続で1桁順位を取ってレーティング（β）が2800を超えました。 各コンテストでどういったことを考えて方針を定めていったのかを書きます。 AHC001 5位（長期） 焼きなませるので焼きなます。…

しばしばマラソン（ヒューリスティック）コンテストで使うやつです。 値の追加・削除・存在確認が、最悪時間計算量が定数倍の軽い O(1)、 空間計算量が O(n) でできます。 入っている値を他の値で置き換えるとか、入っている値からランダムに1つ返すとかも簡…

これは 色変記事 Advent Calendar 2020 19日目の記事です。 色変できませんでした 第17回あーだーこーだー にて 「（ヒューリスティックの）ratedコンテストは年内にやります！」 という発言がなされたのを見て色変記事アドベントカレンダーに登録しましたが…

Competitive Programming (1) Advent Calendar 2020 11日目の記事です。 Topcoder Open 2020 について書きます。 tco20.topcoder.com Topcoder Open(TCO) とは Topcoderが年に1度開催している、世界最強プログラマー決定選手権です。 1年ほどかけて予選が行…

■ [ICFPC] ICFP Programming Contest 2019 02:13 https://icfpcontest2019.github.io/https://github.com/tomerun/icfpc2019 一人で参加した。一人でフル参加したのは何気に初めて。 2009: 途中で萎えた（同時に開催されてたマラソンマッチに移行した） 2010…

■ [部活]プログラミングコンテストに参加し始めて10年が経ちました 03:02 これは Competitive Programming (1) Advent Calendar 2018 10日目の記事です。 僕が初めて参加したプログラミングコンテストは Google Code Jam 2008 なので、今年でプロコンに参加…

■ [部活] 北大日立新概念マラソンでやった高速化色々 23:59 Competitive Programming Advent Calendar 2017 16日目の記事です。 北大日立新概念マラソン、1回目も2回目も、Simulated Annealingの良い近傍を適用できた人が上位になったという結果でした。僕は…

■ [部活] マラソンマッチは役に立つ 18:29 Competitive Programming Advent Calendar 2017 2日目の記事です。近年のAdvent Calendar執筆ハードル上昇に対抗するため簡単な記事にします。皆さんご存じのように競技プログラミングは役に立ちませんが、マラソン…

■ [TCO][MM] TCO17 Onsite 20:44 10月20日（金） 16時の飛行機で成田から出発。空港に着いたのは2時間弱前で、サンドイッチ食べるくらいの余裕はあったこういう話があるので今後はもっと早く行った方が良さそう http://www.afpbb.com/articles/-/3148112?cx_…

■ [MM] Marathon Match 95 CirclesMix 16:10 https://community.topcoder.com/longcontest/?module=ViewStandings&rd=16959 1日目（木曜） 問題を読んだ 2日目（金曜） テスターをカスタマイズ（いつもの） マルチスレッドでのバッチテスト 結果の出力を良い…

■ [TCO][MM] TCO17 Marathon Round2 20:55 https://community.topcoder.com/longcontest/?&sc=5&sd=desc&module=ViewStandings&rd=16928 準備フェーズ とりあえず、感覚をつかむために次の2つの自明解を作った。 毎ターン一番近い敵に攻撃 990人まで貯まった…

■ [CodeChef] June Challenge 2017 20:49 https://www.codechef.com/JUNE17/ A Good Set (GOODSET) 500,499,498,... を出力するhttps://www.codechef.com/viewsolution/14009670 Xenny and Coin Rankings (XENRANK) やるhttps://www.codechef.com/viewsoluti…

■ [TCO][MM] TCO17 Marathon Round1 01:11 https://community.topcoder.com/longcontest/?&sc=5&sd=desc&module=ViewStandings&rd=16903 やったこと 3段階で焼きなましをした。 35*35のグリッド上で、ランダムな頂点をランダムな位置に動かす遷移。評価値は…

■ [CodeChef]January Challenge 2017 18:13 https://www.codechef.com/JAN17 Cats and Dogs(CATSDOGS) やるhttps://www.codechef.com/viewsolution/12432868 Reservior(RESERVOI) やるだけだけど問題文で網羅されていない仕様があって1WAしたhttps://www.cod…

■ [CodeChef]December Challenge 2016 13:40 https://www.codechef.com/DEC16週末1つが他の用事で埋まっていたのでつらかった Train Partner(ANKTRAIN) 問題文が難しいので適当に推測https://www.codechef.com/viewsolution/12173217 Kirito in labyrinth(KI…

■ [部活] AtCoderの昔の問題を難易度推定する 00:09 これは Competitive Programming （その2） Advent Calender 2016 1日目の記事です。 先日、Twitterでこのような発言を見かけました。 AtCoderの過去問が今の基準だと何点になるのか知りたいhttps://twitt…

■ [CodeChef]November Challenge 2016 00:48 https://www.codechef.com/NOV16最後の問題までやる時間とれないですねえ… Task for Alexey(ALEXTASK) 最小公倍数https://www.codechef.com/viewsolution/12015223 Chef and squares(CHSQR) F(K) の上界が K/2 で…

■ [CodeChef]October Challenge 2016 17:35 http://www.codechef.com/OCT16ひさしぶりに参加した。ちょうど良い難易度だった。 Chef and Keyboard(CHEFKEY) やるhttps://www.codechef.com/viewsolution/11712752 Chef and Three Dogs(CHDOGS) Three Dogs Pro…

■ [ICFPC] ICFP Programming Contest 2016 12:46 例年のように会社の人たちと参加した（チーム名：fixstars）。6人で合宿。 やったこと ソルバ作成 紙を開いていくという王道な方針のソルバは他の人がやっていたので、違う方法を考える。入力のskeltonを最小…

■ [部活]すごいサブミット 00:42 これは Competitive Programming （その2） Advent Calendar 2015の1日目の記事です。 Advent Calendarの基本に返って、すぐ書ける記事にします。これまでにコンテストで見た、印象に残ったサブミットを列挙します。他人のコ…

■ [ICFPC]ICFP Programming Contest 2015 01:58 例年のように会社の人と合宿して参加した。5人チーム。 やったこと テトリスAIだったので、まあビームサーチかなということでまずは下に落とすだけのソルバを書いた。2日目の午前中くらいには回転なし版がそれ…

■ [CodeChef]March Challenge 2015 20:34 http://www.codechef.com/MARCH15使える時間が 週末×1 だけでは難問まで手が出せなくてつらい… Chef and Notebooks(CNOTE) やるhttp://www.codechef.com/viewsolution/6418160 Sign Wave(SIGNWAVE) 実験すると規則性…

■ [CodeChef]Februray Challenge 2015 18:06 http://www.codechef.com/FEB15これがchef longのガチ問か Chef and Chain(CHEFCH) 010101... とxorをとってbitcounthttp://www.codechef.com/viewsolution/6128122 Chef and Equality(CHEFEQ) 最頻値の個数を数…

■ [CodeChef]January Challenge 2015 21:24 http://www.codechef.com/JAN152年ぶりくらいに参加した。このコンテスト形式、マイペースに取り組めて良いので今後も出ようと思う。 Chef and Stones(CHEFSTON) やるhttp://www.codechef.com/viewsolution/571332…

■ [部活][MM] MarathonMatchトレーニングのための過去問レビュー 01:01 これは Competitive Programming Advent Calendar 2014 1日目の記事です。 MarathonMatchで成績を上げていくには、他のスポーツと同じく実践が不可欠だと思います。しかし、最近は通常…

■ [TCO][MM] TCO14 Marathon Round2 18:45 http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15982&pm=13189 問題 ランダムな大きさの長方形がN個与えられる。長方形の各辺の長さは[1,1000]、Nの範囲は[100,1000]の一様分布。こ…

■ [TCO][MM] TCO14 Marathon Round1 21:23 http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15938&pm=13132 問題 yowaさんのスライドを参照。http://topcoder.g.hatena.ne.jp/yowa/20140424 やったこと 問題読む→はい、いつもの…