TopCoder Marathon Match 120 "ReversalSort" - iwashi31’s diary
問題概要 長さ 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
AI と共に闘うカードゲーム ゼノンザード - iwashi31’s diary
最近ドハマリしているゼノンザードというカードゲームについてご紹介します。 ※この記事は プログラマーのオススメのゲームの話をする Advent Calendar 2019 の 1 日目の記事です。 ゼノンザードとは バンダイが今年 9 月にリリースした、カードゲームのスマホアプリです。 www.aicarddass.com マナを溜めてモンスターを召喚してバトルして、先に相手のライフを 0 にした方が勝ちという感じのやつです。 特徴 バトルシステムも大変絶妙で面白いのですが、この記事では別の核である AI に関連するシステムに注目して推していきます。 公式が「AI と共に、AI と闘う」と謳っているとおり、このゲームでは相棒のバディ AI とコンビを組んで他人と対戦します。 ゲーム内では "クロスバトルルール" と呼ばれているシステムです。 クロスバトルルール プレイヤーは互いに相手の A
TopCoder Marathon Match 99 "BrokenSlotMachines" - iwashi31’s diary
参加しながら考えたこと試したことの源泉かけ流し。 問題文はこちら 1 日目 問題文を読む。 へ～今回はカジノが題材かぁ。 学生時代オンライン学習の研究やってた身としてはスロット → 多腕バンディット問題を連想するよね～……って、エッこれまんま多腕バンディットやん！！（ここで取り乱す） 僕の卒論は「部分的なフィードバックに基づくオンライン離散最適化」って題目だったんですが、まさにこういう問題だよねっていう。 えー勝たなきゃ恥やろコレ…。 多腕バンディット問題とその考え方については下のスライドにすごく分かりやすくまとまっているのでそちらを読めば良いと思います。 バンディットアルゴリズム入門と実践 from 智之 村上 www.slideshare.net ひとまずスタートダッシュということで、C++ でのテスタ作成と以下のアルゴリズムを実装して提出した。 総時間の 1/3 で notePlay
TCO2017 Marathon Round2 "AbstractWars" - iwashi31’s diary
参加しながら考えたことの源泉かけ流し。 1日目 所感 いや 2 月にあった CodinGame の Ghost in the Cell まんまやないか～い。 真面目にやったつもりだったがあまり良い順位が取れなかったコンテストなので、ちょっとブルーな感じ。 それにしても、Round1 に続いて Round2 でも似たような実装やったことある問題が出るとは…。 Ghost in the Cell との相違点 ボムや生産性向上とかのスキルがない。 基地にいるユニット数が多いほど生産性が向上する。 一つの基地のユニット数に上限がある。 敵の troop についても行き先が(ある程度)分かる。 最終的な勝ち負けだけでなく、スコアの概念がある。 しばらくはビジュアライザ内蔵 AI に勝つことを目標に進めることになるけど、最終的にはスコアの最適化もしないとだろうなぁ。 実装したこと とりあえず「半分投げ
ゲームAIコンテストのすすめ - iwashi31’s diary
ゲームAIコンテストに興味はあるんだけどなー、って方向けの記事です。 （Competitive Programming （その2） Advent Calendar 2015 15日目の記事として書いたものです。） はじめに 僕はCODE FESTIVAL2014でのAI ChallengeをきっかけにAI系のコンテストにハマり始めました。 で、周りの競プロerにも勧めるんですが、よく「ハードルが高そう」という声を耳にするわけですね。 今日はそんな幻想をぶち壊した上で、少しでも参加したい気にさせてみせます！ ゲームAIコンテストって？ ゲームAIコンテストはいわゆるマラソン系のプログラミングコンテストになります。 コンテストが始まるとお題となるゲームとそのルールが発表されるので、参加者はそのゲームで動作するAIを1週間～2ヶ月ぐらいの期間で作成し提出します。 予選等での順位付けの方法は、参加
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
