この記事はCodinGameの一人用最適化ゲームの紹介記事です。 CodinGameといえば対戦ゲームが定番ですが、一人でやる最適化ゲームも実はけっこう充実しています。このたび全ての最適化ゲームをプレイし終えたので、それらの紹介記事を書いてみることにしました。 Optimizationカテゴリ CodinGameにはOptimizationというカテゴリがあり、最適化ゲームはそこに分類されています。このカテゴリのゲームは一人でプレイし、ハイスコアを競います。 Optimization ゲーム一覧 この記事で使う指標 ・公式評価 CodinGameユーザーによる投票の５段階評価の平均点（2021年3月14日 現在） ・私の評価 私が好きかどうか ★１～★５（好きでない～好き）の５段階で評価 ・問題の単純さ 問題の内容が分かりやすいか ★１～★５（分かりにくい～分かりやすい）の５段階で評価 ・

3月19日に第9回 SamurAI Coding の決勝戦が行われた。私はチーム Monk1 の一員として参加させてもらった。期間が (他のコンテストと比較すると) 長めだったこともあり、すべて終わった今としては多少の悔しさと軽い達成感がある。せっかくなので、記憶が薄れないうちに参加記として残しておこうと思う。 なお、チームメイトの montplusa くんによる参加記もあるので是非どうぞ。私のこれはタイトルの通り日記なのであまりおもしろいものでもないと思う。彼の参加記は AI そのものや戦略の話に重点を置いているので有益だと思う。 montplusa.hatenablog.com そもそも戦略については多少のアイデアを加えたのみでほとんど彼に任せっきりだったので、なんと決勝ラウンドに提出された AI の仕様変更を完全には把握していない。でもこれは日記なのでそれはいい。私の視点から見た各時

興味深いサイエンスニュースをお伝えする「理系通信」。 今回のテーマは「競技プログラミング」です。 「競技プログラミングなんて自分には関係ない」と思うことなかれ。 実は競技プログラミングは、「プログラミングに興味はあるけどやる気が出ない」というような人に最適だというんです。 そんな競技プログラミングのコンテストに、プログラミングのド素人・橋本ディレクターが挑戦。 果たして初心者でも本当に戦えるのか、一体どんな問題が出るのか、そしてなぜ多くの人が熱中するのか。 知られざる競技プログラミングの世界を詳しくお伝えします。 ＃AtCoder＃高橋直大＃chokudai＃競技プログラミング＃プログラミング＃アルゴリズム＃鹿島建設＃競プロ#アットコーダー ◆「ワールドビジネスサテライト」「ガイアの夜明け」などが見放題！ 「テレビ東京ビジネスオンデマンド」はコチラ↓（入会月無料） https://tx

AtCoder Heuristic Contest 001 (AHC001) の参加記を書くはずだったのですが、記念すべき第1回ということで「マラソンに初めて参加したけど、感想戦TLで周りが何を言っているか分からない……。」という方が多そうな気がして、気付いたら初心者向け解説記事*1を書き始めてしまっていました。 ふぁぼ圧、強すぎませんか https://t.co/DuGViXzI80— TERRY (@terry_u16) 2021年3月15日 参加記はまた後日書きます。→書きました。 www.terry-u16.net 問題概要 はじめに 正の得点を得る（823,090点） 山登り法を導入してみる（452億点） ちょっと改善してみる（469億点） 焼きなまし法を導入してみる（477億点） さらなる改善 Tips 手元でテストケースを回す コンテスト序盤は特に丁寧にコードを書く 愚直判定

この記事は、Competitive Programming (1) Advent Calendar 2020 - Adventarの17日目の記事です。 読んでも競技プログラミングの実力は上がりませんので、ご注意ください。 過去の分はこちらです。 Advent Calendar 2016 : ABC#001のA問題をコンパクトに解く - kmjp's blog Advent Calendar 2017 : CPHBを少しだけ和訳してみた(前編) - kmjp's blog Advent Calendar 2018 : ブログを書く速度を少しだけ上げる - kmjp's blog Advent Calendar 2019 : 高橋君は何問登場したか？～高速に問題をブラウズする - kmjp's blog 目次 目次 はじめに 実験結果 プレッシャーがないとき ◆ABC185とLeetCode

Competitive Programming (1) Advent Calendar 2020 11日目の記事です。 Topcoder Open 2020 について書きます。 tco20.topcoder.com Topcoder Open(TCO) とは Topcoderが年に1度開催している、世界最強プログラマー決定選手権です。 1年ほどかけて予選が行われ、そこで勝ち抜いた各部門*1の10人ほどが、例年11月くらいにアメリカで行われる決勝に招待されます。 TCO20 今年はパンデミックのせいで例に漏れずオンラインでの開催になりました。かなしいね まあプログラミングコンテストなのでオンラインでも十分実施可能… と思いきや、Marathon部門は決勝は例年 10時間コンテスト で、オンライン開催で10時間コンテストやろうとすると時差が困ったねということに。 これは無理みたいな感じ 色々協

データ分析と機械学習の国際的なコンペティションプラットフォーム「Kaggle（カグル）」のシミュレーションコンテスト「Halite by Two Sigma」で、株式会社バンダイナムコ研究所の技術開発本部のAI（人工知能）研究開発エンジニア會田 翔がGold メダルを受賞しました。 Kaggleでは、オンライン上で企業や政府機関などによるさまざまな課題のコンペティションが開催されており、世界中のデータサイエンティストが参加し、データ分析や機械学習などを用いて課題に挑んでいます。 Haliteは、Two Sigmaが制作したAIプログラミングチャレンジで、複数の船を製造・操作して「Halite（岩塩）」を採取し持ち帰るという４人同時手番のターン制対戦ゲームです。参加者は、このゲームをプレイするAIを開発し、提出します。Kaggle上では、登録されたAIのうち実力が近い者同士がマッチングされ、

問題概要 長さ N の数列が与えられる。下記の操作を任意回行って、コストをできるだけ抑えつつ昇順ソートせよ。 数列中の連続する区間を好きに選んで、その区間内の数列を反転する。コストは floor((区間の長さ)X)（X は入力で与えられ、0.0 ≦ X ≦ 3.0）。 全文はこちら。 解法 以下の 4 つの解法を試して、一番良かったものを採用する。 アルゴリズム概要 有効な X ① バブルソート 2.2 ~ ② 選択ソートっぽいやつ ~ 0.1 ③ 選択ソートっぽいやつ改 1.8 ~ 2.3 ④ 隣り合う要素の差の合計を最小化する貪欲 0.1 ~ 1.8 ① バブルソート X が大きい場合、バブルソートが最適解になる。 最適解になるのは X ≧ 2.71 くらいからのはずだが、他のアルゴリズムがかしこくないせいか X = 2.2 くらいでこれが採用されることもあった。 1 1 1 0 3

こんにちは、ganariyaです＞＜ 主に競技プログラミングを嗜んでいます。 先日、改善型コンテスト（マラソン）がAtCoderに定期開催されるとのことで、その導入コンテストとして「Introduction to Heuristics Contest」が開催されました。 今回は、その参加記ならびに焼きなましに対する自分の理解やマラソンでの個人的な方針をまとめようと思います。 ganariya 問題ページ 自分の提出 公式解説 コンテスト中の方針 問題を読むと分かりますが、問題B、CをやってからAをやるといいと書いてあります。 僕はマラソン系初心者なので、Bから解き始めました。 Bは、Aでのスコア計算プログラムを書こう！というものでした。 これはそんなに難しくなく、300点ぐらいの内容でした。 公式解説はRustのため、C++で書く場合はどうなるか載せておきます。 LL get_score(

https://atcoder.jp/contests/intro-heuristics/standings 20 位。ギリギリ1ページ目に乗った ~21:00 テンプレートの準備。 rdtsc と焼きなましテンプレはコピペして、ONLINE_JUDGE があるので input() の受け取りをするかどうかを環境で切り分ける部分も先に書いておいた。 cat /proc/cpuinfo で CPU が 3.00 GHz に上がっていることを確認して rdtsc の定数をちょっと書き換えたりした。 21:00~ 21:09 A を読んでから B を解く。 やりたいことはなんとなくわかったけど、サンプルが D=5 なせいでちょっと手間取る。こういうのは const int D=365; したくなる人間なので……。 なんとか直して提出！ なんで？ 毎行出力させるのを忘れていました。ちゃちゃっと直し

Topcoder 初めてのTopCoderマラソンマッチ。34位/68人とちょうど真ん中の成績でした。 問題概要 のグリッドの各マスが 色のうちいずれかで塗られている。 人のダンサーがいて、 単位時間かけてグリッド上を移動する。このとき各マスが1回踏まれるたびに、周期 で色が変化する。色変化のローテーションはマスごとに異なる。 各ダンサーについて、「ある時刻にこのマスにいなければいけない」という制約条件がいくつか与えられる。同一ダンサーの、時系列で見て隣り合う2つの制約条件を両方満たすことができること（つまり、指定時刻の差が指定マス間のマンハッタン距離以下であること）は保証される。 全てのダンサーの移動が完了したグリッドにおいて、各色それぞれの連結成分の個数を数える。色 の連結成分の個数が であるとき、 がスコアとなる。 スコアが小さくなるようなダンサーの移動経路を出力せよ。 方針 焼きな

何も分からん、になった回でした。 問題 問題文(原文)はこちら 要約すると、 N*Nのグリッドと、D人のダンサーの位置が与えられる。 ダンサーは1ステップごとに上下左右に隣り合うマスに移動することができる（移動せずにそのマスに留まってもよい）。また、ダンサー1人ごとに、あるステップ数目の終了時点で居なければならない位置が入力として与えられる。 グリッドの各マスにはC色のうちどれかの色がついており、ダンサーが別のマスに移動すると、移動先のマスの色が別の色に変化する（移動しなかった場合は変化しない。また、複数人が同時に同じマスに移動した場合は、移動した人数と同じ回数だけ変化する）。どの色からどの色に変わるかはマスごとに入力として与えられる。 Sステップ終了後、(ある1色の連結成分の数)2の、全色についての総和が小さいほど良いスコアとなる。 という感じです。 やったこと 最後に提出したコードはこ

はじめに CodinGameのコンテスト（CodinGame Spring Challenge 2020）に参加しました 結果は世界61位（LEGEND）、日本12位と健闘出来たかなと思います Legendリーグは114人いて日本人が18人なのでLegendのうち6人に1人くらいが日本人だったみたいですね みんな強い ルール 詳しいルールはツカモさんが記事にしているのでそちらを参照するのが良いと思います 簡単に言うと、パックマンで相手よりたくさんポイント（ペレット）を集めたほうが勝ちで、パックマンのタイプによってじゃんけん要素が加わった感じです tsukammo.hatenablog.com やったこと リーグ別に段階を踏んで改善していったものも書きますが、ここでは最終的にどんなことをやったのかだけ簡単にまとめておきます 基本的には貪欲とルールベースで評価関数によって行動を決定していました

"CodinGame Spring Challenge 2020"に参加しました。 CodinGameにはリーグという階級分けの制度があり、各リーグのBOSSを基準にWood2, Wood1, Bronze, Silver, Gold, Legendと登っていきます。今回のコンテストで初めてSilver(の上位)まで到達することができました。 作成したAIも自分より強い敵にぶつかりに行ったり、同じ場所を往復したりはしない状態になりました。 Gloval rank 702/4976、Silver rank 57/999と満足のいく結果となった。 参加経験 CodinGameへの参加は2018年のXMAS RUSH, 2019年のUNLEASH THE GEEKに続いて３度目の参加で、今回のコンテストで初めてSilver Leagueへの進出を果たしました。 これまでに参加したコンテスト 取り

ツイッターで何度か流れてきたので途中から試しに参加してみたらめちゃくちゃ熱を上げてしまった。わりとしっかりしたメモを残していたうえ、思いがけずかなり気持ちになってしまったので感想を書いておくことにする。 まずコドゲに登録した日が1週間くらい前になるらしい。正直に言うと最初にルールを読むだけで疲れてコードを初めて書いたのは何日か経ってからだった。 13日にコードをいじり始めたが、そもそもAtCoderしかしたことがないので初期コードを読むだけで一苦労だった。とりあえずwoodでは使わないとコメントされているスキル周りの受け取りを削った。これで受け取りはできていると思ったので、出力をいじるためにペレットの情報を受け取ったら、スーパーペレットから順に一番近いペレットにそれぞれのパックを向かわせることにした…ところ見事に出力が壊れた。パックをちゃんと指定できていないのかなあと思って色々試しても何も