HackerEarth December Circuits '17 参加日記

2017年最後のプロコン。57位/5713人で風邪を引いていた割には悪くない。長期型プロコンだと、二桁順位がたまに取れるくらいの実力にはなったようだ。


Two Arrays

同じ長さnの整数列X, Yについて、マッチング数を以下のように定義する。
・X[i] = Y[j], (1 <= i, j <= n)となるインデックス(i, j)のペアの数
整数Kと、長さNの整数列A、および長さMの整数列Bが与えられる。AとBから同じ長さの部分列を抜き出し、マッチング数がK以上になるパターン数を答えよ。
1 <= N, M <= 2000
1 <= A[i] <= 1000000000
1 <= B[i] <= 1000000000
1 <= K <= NM

次のような二次元配列を用意する。
table[i, j] = A[i] とB[j]が等しいなら1、それ以外なら0
すると、table[,]の正方形(i, j)~(k, l)は、A[i, k]とB[j, l]でマッチする組み合わせに等しくなる(1の部分がマッチするところ)。
よって、すべてのi,jの組み合わせについて、(i, j)を左上とした正方形をどんどん大きくしていって、中の1の数がK以上になったところから、限界までの正方形の数を足したものが答えとなる。これは累積和と二分探索で効率よく求めることができる。
https://www.hackerearth.com/submission/13789952/


Left or Right

国Xには、0からN-1で番号付けされるN個の都市があり、サイクルのようにつながれている(都市iは、都市(i + 1)%Nと都市(i - 1 + N)%Nとつながっている)。また、各都市にはタイプA[i]がある。次のQ個のクエリに答えよ。
タイプ1: 都市YからタイプZの都市まで、左回りで移動したときの最小ステップ数
タイプ2: 都市YからタイプZの都市まで、右回りで移動したときの最小ステップ数
たどり着けないときは-1を返すこと。
1 <= N <= 3000
1 <= Q <= 500000
0 <= Y < N
1 <= A[i], Z <= 200000

都市のタイプごとに、位置をリストでもてばよい。それぞれYの位置をLowerBound()で求め、その次または前のIndexとの差分を返す。
https://www.hackerearth.com/submission/13790214/


HP and Splitting of Array

数列Aについて、A[i] > A[j]かつi < jなら、そのペアはinversionである。すべてのinversionであるペアの合計をinversion countと呼ぶ。長さNの整数列Aが与えれたとき、Aを左にiだけローテーションしたときのinversion countを求めよ。iは1からNのすべての数である。
1 <= N <= 100000
1 <= A[i] <= 1000000
Aに重複する要素はない

ある状態Aのinversion countがすでに求められていたとする。Aを左に1つローテーションしたもののinversion countは、
現在の値 - (A[0]の順位 - 1) + (N + A[0]の順位)
となる(『A[0]の順位』はAを昇順ソートしたときの要素A[0]の位置)。
あとは、初期状態のinversion countを求めれば良い。これはBITを使って効率よく求められる。
https://www.hackerearth.com/submission/13828080/


Berland Programming Contests

N個の都市があり、それらをつなぐ道は全体でツリーを構成している。M種類のコンテストが各都市で開催される(1つのコンテストが複数の都市で開催されうる。ある都市では、あるコンテストが開催されないこともある)。ここで、
・連結したサブグラフを選び
・選んだサブセットで開催されるすべてのコンテストタイプに出場する
とする。この時、コンテストタイプの種類数kだけパスを購入しなければならない。
すべてのサブセットについてこのルールを適応したとき、パス数に対するサブセットの数を、すべてのkについて答えよ。
1 <= N <= 5000
1 <= M <= 10

解けそうで解けなかった問題。
dp[i, j] := 根をiとする木で、状態jになるサブグラフ数
と定義する。初期値を
dp[i, (開催されるコンテストマスク)] = 1
として、葉以外のノードについて、
dp[i, j] = dp[i, j] + \sum_{k\&l=j}^{} dp[i, k] * dp[x, l] \: (xはノードiの直接の子)
のようにマージしていけば求められる。
計算は次のテクニックを使ってスピードアップできるらしい。
http://codeforces.com/blog/entry/45223(整数列のすべてのサブセットに対して、その合計を効率的に求める方法)


Buggy Bot

ノード数nの有向グラフ上を、Botがk個のインストラクションにそって移動する。インストラクションは、「現在地がノードxならノードyに移動せよ」というものであり、始めBotはノード1にある。ただし、移動中1回のみ、ランダムに隣のノードへBotが移動してしまうことがある。これは、インストラクションの前後いずれでも起こり得る(1度も起こらないこともある)。
このとき、最終到達地点としてありえるノードを答えよ。
1 <= n <= 100000
1 <= m, k <= 100000

本番ではDFS+メモ化で部分点だった。
ランダム変化がない場合の、ステップごとの位置を最初に算出する。そして、「現在のステップで最終的に到達する場所」をノードごとに保持しながら、うしろから処理していく。
(実装は省略)

2017年振り返りと2018年の抱負

2017の抱負と結果

  • SRMで黄になる → LongContestで二桁安定 (30%)

Topcoderがアレなので途中で変更した抱負。二桁順位は30%くらいの確率なので達成率も30%。

  • 熱で寝込まない (100%)

風邪は引いても寝込んではいない。すばらしい成果。

  • ちゃんと寝る (20%)

連続で5時間睡眠を何度かやってしまった。



2018年の抱負

  • 一日7時間睡眠

いいかげん睡眠不足になっていい歳じゃない

  • 年収+15%

去年は+8%だったのでかなりアグレッシブ

  • 低レイヤ分野でレジュメにかけるレベルのアウトプットを何か

具体的には30日OS本と熱血アセンブラ本



プロコンはちょっと控えめにする予定。

HackerRank Week of Code 35 参加日記

1044位/9458人の酷い結果。以下、易問は省略。


3D Surface Area

HxWの平面上の各セル上に、立方体がいくつか積み重なっている。外部に面している面積を求めよ。

X面からみた面積、Y面からみた面積、Z面からみた面積をそれぞれ求めて足せば良い。
https://www.hackerrank.com/contests/w35/challenges/3d-surface-area/submissions/code/1304126485


Matrix Land

n行m列のマトリックスがあり、各セルには点数が設定されている。1行目の任意のセルから、n行目の任意のセルまで移動したとき、得られる合計得点の最大値を求めよ。ただし、セルの点数は通過後にゼロになる。また、セルからの移動は左右と下のみ可能である。
1 <= n x m <= 4 * 10^6

3日考えて解けなかったDPの問題。これは悔しい。
移動制約により、ある点に到着するルートは2通りしかない。
f:id:yambe2002:20171122071240p:plain
パターン1:ある点より左いずれかに降りてきて、点を通過して右から戻ってくる(通過しない場合も含む)
パターン2:ある点より右いずれかに降りてきて、点を通過して左から戻ってくる(通過しない場合も含む)
パターン1だけ考えてみる。
f:id:yambe2002:20171122071615p:plain
上の矢印で表されるのは、「その行だけを考えたときの、(x, y)より右の合計最大値」であり、
msr[x, y] = Max(msr[x, y + 1] + A[x, y], 0)
と表すことができる。
f:id:yambe2002:20171122071605p:plain
上の矢印で表される部分をmslit[x, y]と定義すると
mslit[x, y] = Max(mslit[x, y-1] + A[x, y], dp[x - 1, y] + A[x, y] + msr[x, y + 1])
と表すことができる(dp[x,y]は点(x,y)に来るルートの最大点)。
この合計値を求めて、最大のものを解答すればよい。パターン2も同様。

Codechef November Challenge 2017 参加日記

143位/8136人で目標の2桁順位は達成できず。回答人数の多いCSUBQで部分点だったのが痛かった。以下、易問は省略する。


Periodic Palindrome Construction

長さNの文字列Sについて、Nが整数Pの倍数であり、かつSをPごとに分割したときすべてのP[i]が一致しているものを、周期がPである、と定義する。NとPが与えられたとき、文字aとbのみを使って、周期がPかつ全体で回文になる、長さNの文字列を作れ。ただし、文字列にはaとbの両方を使う必要がある。
1 <= P, N <= 10^5

UnionFindを使う。最終的な文字列をSとすると、全体で回文なので、
S[0] = S[len-1]
S[1] = S[len-2]...
とグループ化できる。
また、各分割文字列A,B...について
A[0] = B[0] ...
A[1] = B[1] ...
とグループ化できる。
全ての文字が同一グループになってしまったらImpossible、そうでないならグループごと適当にabを当てはめればよい。
https://www.codechef.com/viewsolution/16049370


Chef Hates Palindromes

アルファベットの最初のA文字のみを使い、長さNの文字列Sを作成せよ。このとき、最長の回文部分文字列をなるべく短くせよ。
1 <= N <= 10^5

まず明らかな観察として、A=1のときはaのみの文字列を返すしかなく、A>=3ならabcabcabc...を返せばよいことがわかる。よって、A=2の場合のみ考えればよい。
なるべく部分的な回文を短くしたいので、Nがある程度大きいなら
a|ab|b|ab|a|ab|...
のように構築すれば、最長の回文文字は長さ4になって最小となる。
("ab"で囲んでしまえば、その内部にある文字を中心とした回文は、それ以上大きくは作れないので)
Nが小さい(<=8)場合の回答はすべて列挙してしまうのが早い。
https://www.codechef.com/viewsolution/16058582


Chef and Intersection Line

チャレンジ問題。整数の配列A[M][N][N]が与えられる。このとき、二次平面上の点P[1],P[2],P[3],...P[M]を回答せよ。ただし
・P[i] - P[i - 1]の線は、それ以前のいずれの線とも交差してはならない(隣の線と一点でのみ一致する)
・k番目の点に(i, j)ついて、得点A[i][j][k]が加算される
・合計点をなるべく多くするのが目標
N = 50
1 <= A[k][i][j] <= 100
M = 50のテストセットと、M = 500のテストセットがある
制限時間は2.5秒
(テストケースの生成ロジックは省略)

以下の方針で90点程度の結果だった。
・有効解を貪欲的に作成する(点数はあまり気にしない)
・ランダムに点を選んで山登り
・次の点は、M=50のセットでは盤面のほぼすべてから、M=500は狭いので上下3ポイント以内くらいから選ぶ
盤面が100x100しかないので、M=500はかなり狭くあまり改善の余地がなかったように思う。
https://www.codechef.com/viewsolution/16235791


Chef and Subarray Queries

長さNの整数列Aと、整数L、Rが与えられる。Aの初期値はすべてゼロである。次のクエリに答えよ。
・タイプ1:A[x]をyに更新する
・タイプ2:Aの範囲[l, r]にあるサブ配列すべてにおいて、最大値がL以上R以下となるものの数を出力
1 <= N <= Q <= 5 * 10^5
1 <= L <= R <= 10^9
1 <= x <= N
1 <= y <= 10^9

本番では平方分割と二分探索を駆使して52ptの部分点だった。想定解はセグメント木を使う。以下の解説がわかりやすかった。
hamayanhamayan.hatenablog.jp
セグメント木のノードごとに
・Count: 対応する要素数
・Answer:ノード単体での解答
・MinLeft/MinRight:ノード左(右)端に続く、連続するL未満の数の数
・MaxLeft/MaxRight:ノード左(右)端に続く、連続するR以下の数の数
の情報を持つ。すると、Answerは以下のように計算できる。

cur.Answer = left.Answer + right.Answer;
cur.Answer += left.Max_Right * right.Max_Left;
cur.Answer -= left.Min_Right * right.Min_Left;

MaxLeft/MaxRightを「連続するL以上R以下の数」にすると計算が面倒になってしまうようだ。
https://www.codechef.com/viewsolution/16282630


Product on the segment by modulo

長さNの整数列と整数Pが与えられる。以下のQ個のクエリに答えよ。
・区間[L, R]の要素すべての積 mod Pを出力
1 <= N <= 10^6
1 <= Q <= 2 * 10^7

本番では累積和(imos法?)的に解いたが、当然Pが素数でないと通らないので部分点だった。
想定解ではSparse tableのようにデータを持つ。
・A[k, i]: i以下で2^kの倍数となる最大のインデックスからiまでの積
・B[k, i]: iから、iより大きくて2^kの倍数となる最小のインデックスまでの積
こうすると、B[k, L]とA[k, R]で重複がないkを選ぶことができれば、各クエリに対してO(1)で回答できる。k=1から増やしていけば簡単に見つけることができる。(証明は公式Editorialにある:https://discuss.codechef.com/questions/116821/segprod-editorial)
Sparse tableはこちらが分かりやすかった。
http://tookunn.hatenablog.com/entry/2016/07/13/211148


Lovers Gift

N個の都市が、双方向に繋がった木の形のグラフで表される。都市はそれぞれ1からNでDistinctにスコア付けされる。次のクエリに答えよ。
クエリ1: 都市Cに銀行がオープンする
クエリ2: 都市Cから1つ以上の銀行を経由し、2番目にスコアの大きい都市を訪れる。ただし同じ道は通れない。このスコアを出力せよ
1 <= N, M(クエリ数) <= 100000

想定解は素集合を使って求める。この方法は本番でも思いついていたが、計算量が大きく不可能と判断してしまっていた。
・銀行がすべてオープンした状態にして、後ろからクエリを発行する
・銀行を経由しないグループを1つの集合とする
・集合ごと、「集合外で1番目と2番目に大きなスコア(m1とm2)」を管理する
・銀行がクローズするたび、集合をマージ
こうすれば、クエリ2ごとに
・Cに銀行があればN-2を解答
・それ以外ならm2を解答
すればよい。
マージ後のm1、m2は、単純にm1からデクリメントして探していく。これだと間に合わなそうだが、マージするたびにm1の初期値がどんどん小さくなるので問題ない。

Codechef October Challenge 2017 参加日記

78位/10487人。これくらいの順位で安定するのが今年の抱負(改)。
以下、易問は省略する。


Chef and a great voluntary Program

リンゴa個、バナナb個をn人にいずれか一個ずつ配りたい。このとき、リンゴを配られた人は、直前x人が続けてリンゴだったら不満に思う。同じように、バナナを配られた人は、直前y人がバナナだったら不満に思う。不満を解消するには、リンゴまたはバナナを配る直前にキウイを渡せばよい。キウイの数を最小にせよ。
1 <= n <= 10^5
1 <= x, y <= n

a<=bとすると、配布の方法は2パターンしかない。
1、a, bひとつ以上, a, bひとつ以上...
2、bひとつ以上, a, bひとつ以上, a...
よって、aを一個ずつに分けて、その間にbを入れていけばよい。
https://www.codechef.com/viewsolution/15764132


Chef and Cycled Cycles

無向グラフを考える。このグラフにはN個のサイクルがあり、それぞれA[i]個のノードで構成されている。各サイクルにおいて、i番目のノードは(i + 1) % A[i]のノードとつながっている。さらに、グラフ全体をみると、N個のサイクルによって大きな1つのサイクルを構成している。つまり、i番目のサイクルは、i % N + 1番目のサイクルと、いずれかのノードで繋がっている。
すべてのエッジに重みが付いているとき、サイクルc1のノードv1と、サイクルc2のノードv2の最小コストを求めよ
なお、クエリ(c1, v1, c2, v2の組み合わせ)はQ個発行される。
1 <= N, Q <= 10^5
1 <= A[i] <= 10^5
1 <= A[1] + A[2] + ... + A[N] <= 10^5

単純なノードのみで構成されるサイクルn[0], n[1], ... n[k]を考えたとき、次のようにエッジコストの累積和を求めておけば、任意の2点間の最小コストはO(1)時間で求めることができる。
n[0], n[0]+n[1], ... Sum(n[0:k]), Sum(n[0:k])+n[0], ... 2xSum(n[0:k])
これを小さいサイクルと外側の大きなサイクルに適用すればO(1)で回答できる。
https://www.codechef.com/viewsolution/15784456


Chef and Magic Arrays

N個の数列があり、それぞれの数列は好きなようにシフトすることができる。このとき、i番目の数列の末尾の値をx、次の数列の最初の値をyとしたとき、|x - y|*iの合計値を最大化せよ。
数列の長さの合計は10^6を超えない
1 <= 値 <= 10^6

まず自明な観察として、実際に数列をシフトする必要はない。使うのは数列の先頭と末尾だけなので、ある位置jを末尾に使うとすると、先頭になるのはi+1である。
あとは次のDPを立てれば求めることができる。
dp[i, j]: 0..iまでで、数列iについて位置jを選んだときの最大値
https://www.codechef.com/viewsolution/15799713


(Challenge) Connecting computers

チャレンジ問題。ノード数1000の連結グラフを構築したときの最小コストを求めよ。
・各ノード間のコストはすべてランダムに与えられる
・各ノードについて、Degreeに応じたコストがかかる(Degreeの大小とコストの大小は連動しない)
制限時間はT=5で5秒。

Editorial想定解は連結を保持したままの山登り法。これが正解かなとは思ったが、連結を保持したまま高速に回すやり方が分からず保留(したままコンテスト終了)。次点解がクラスカル法+αで、自分の実装もこれで平凡な得点に終わってしまった。


Shooting on the array

二次平面上にN本の部分直線がある。部分直線iは(i,0)から(i,A[i])へ引いてある。このとき、次のQ個のクエリに答えよ。
・+ i X => 直線iのA[i]をXだけ増やす
・? i L R => R-L+1本のX軸に平行なビームを発射する。j番目のビームは(i-0.5, L+j-1.5)から発射される。ビームは直線にぶつかると消える。このとき、ビームがあたる直線の本数をプリントせよ
1 <= N <= 10^6
1 <= Q <= 10^5
x <= X <= 10000
1 <= A[i] <= 10^9
1 <= L <= R <= 10^9

平方分割を使う。このとき、1つのセグメント内ではA[i]が増加している分のみ保持すればよい(それ以外のものはビームが当たりようがない)。するとセグメント内は単調増加になるので、現在のビーム範囲で当たる最も短い(左の)直線と、最も長い(右の)直線が二分探索で求められる。
計算量はO(QSqrt(N)LogN)でぎりぎり間に合う。
https://www.codechef.com/viewsolution/15803230

HackerEarch July Circuits '17 参加日記

HackerEarth初参戦。74位/6699人とまずまずの成績だった。
以下、易問は省略する。

Permutation and reverse

1~nの数字が書かれたn枚のカードがある。このランダムに並んでいるカードを、区間を指定して反転、を繰り返して昇順にソートせよ。
<採点方法>
配列a[]が与えられる。無限配列 { b_i = a_i \, mod\,n }と定義する。
i番目の作業区間の長さを {len_i} としたとき、 {len_i} と一致する次の {b} の位置をposとする。作業するごとposを更新したとき、最終的なposの位置が小さいほど、高得点となる。

上位10人くらいには入ったが、それでもトップの1/4程度のスコアだった。
<方針>
bの位置でループし、
・未ソート区間の左端または右端をうまく作れるときは作る
・それ以外なら、なるべく昇順または降順になるよう、一部を並び替える
を繰り返す
・候補手が複数あるときはランダムに選択
・時間いっぱいトライしてベストのものを回答する
https://www.hackerearth.com/submission/10398190/


Download file

サイズS(MB)のファイルをダウンロードしたい。時間t[i]におけるダウンロードスピードがD[i]で与えられたとき、ダウンロード時間を最小化せよ。
1 <= N <= 100,000
1 <= D[i], S <= 1,000,000
0 <= t[i] <= 1,000,000
t[0] = 0、tの値は昇順

必ず、ダウンロードの開始時間または終了時間がt[i]のいずれかになる。よって、t[i]をループして最短のものを探せばよい。ダウンロード時間は累積和を使えばO(1)で求められる。
https://www.hackerearth.com/submission/10349554/


Dreamplay and Upside Down

文字列Pがある。(1)末尾に文字を追加(2)文字を削除、のいずれかを繰り返し、なるべく少ないステップで回文を作れ。
1 <= Pの長さ <= 5000

文字位置でループ。その文字(もしくは文字間)を中心として回文を作り、最小ステップのものを回答する。あらかじめダミー文字('.'など)を挿入すると、文字間を考えなくてよいので楽。
https://www.hackerearth.com/submission/10285667/


Travelling Tom

n個の都市が双方向の道でつながっている。また、k種類のトークンがあり、それぞれ値段c[i]である。道にはそれぞれ、通過に必要なトークンの種類が設定される(トークンは使いまわせし)。すべての都市を訪れるために必要な、最小の金額を答えよ。
・すべての2<=i<=kについて、c[i] >= 2 * c[i-1]
・1 <= n <= 10^5
・1 <= m <= 10^5
・1 <= c[i] <= 10^18

本番では二分探索+UnionFindで解いて半分ほどTLEになっていた。
https://www.hackerearth.com/submission/10394484/
kの最大値が60程度なのがポイント。あるトークンだけが不足してるとき、全都市が連結でなければ、そのトークンは必須と判断していけばよい(実装は省略)。


MST revisited

ノード数N、エッジ数Nの無向グラフがある。エッジは重みづけされている。自己ループや並行エッジは存在せず、グラフは常に連結されている。エッジを1つ削除・追加するクエリをQ個実行する。このとき、クエリ実行ごとにMSTのコストを答えよ。
・3 <= N <= 300,000
・1 <= Q <= 300,000
・グラフは常に連結、かつ自己ループや並行エッジは存在しない
・1 <= エッジの重み <= 1,000,000

本番ではBICCで実装した。削除エッジがループ内かどうか判定し、計算量を節約してなんとか1サンプルのAC(3/4でTLE)だった。
https://www.hackerearth.com/submission/10374653/
上位陣はLink-cut木というデータ構造を使って解いていた。
https://www.hackerearth.com/challenge/competitive/july-circuits-17/algorithm/mst-revisited-3f9d614c/submission/10347662/
基本的には、ループを作ってしまう1つのエッジ(両ノードのrootが同じになっているもの)を保持し、他はLink-cut木で挿入・削除を繰り返しているようだ。そしてサブ木ごとにMaxコストを保持することで、ループ内の最大コストを算出する計算量を減らしている。
Link-cut木の解説はこちらが参考になる。
プログラミングコンテストでのデータ構造 2 ~動的木編~


Transportation network

n個の都市があり、1つのクエリで都市uとvを道路または鉄道で繋ぐ。クエリごとに、ネットワークがbalancedかどうかと答えよ。balancedなネットワークとは、
・すべての都市のペアu,vについて、u,vが道路で繋がれているときのみ、鉄道で繋がれている
ものをいう。
1 <= n <= 10^5
1 <= q <= 2x10^5
1 <= u, v <= n

本番ではUnionFindを2つ作り、グループに所属するノード数を比較して2/3ほどTLEだった。
https://www.hackerearth.com/submission/10375122/
2つのUnionFindの状態判定に工夫がいる。たとえば道路のネットワークに注目したときには、Queueに保持したエッジごとに鉄道側のUnionFindにおいて同じグループが判定する。分割は無いので同グループと判明したエッジは削除してOK。これを道路側・鉄道側両方で実施する。

var str = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToList();
var n = str[0];
var q = str[1];

var uf1 = new UnionFind(n);
var uf2 = new UnionFind(n);
var que1 = new Queue<Tuple<int, int>>();
var que2 = new Queue<Tuple<int, int>>();

while (q-- > 0)
{
    str = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToList();

    (str[0] == 1 ? uf1 : uf2).Unite(str[1] - 1, str[2] - 1);
    (str[0] == 1 ? que1 : que2).Enqueue(new Tuple<int, int>(str[1] - 1, str[2] - 1));

    for (int i = 0; i < 2; i++)
    {
        var uf = i == 0 ? uf2 : uf1;
        var que = i == 0 ? que1 : que2;

        //balanced?
        while (que.Count() > 0)
        {
            var n1 = que.Peek().Item1;
            var n2 = que.Peek().Item2;
            if (uf.root(n1) != uf.root(n2))
            {
                break;
            }
            else
            {
                que.Dequeue();
            }
        }
    }

    Console.WriteLine(que1.Count() == 0 && que2.Count() == 0 ? "YES" : "NO");
}

CodinGame - Wondev Woman 参加日記

二度目のCodingGameコンテスト。ボードゲームAIの強さを競うもので、結果は世界310位/2299人、アメリカ17位/179人(ゴールドリーグ中位)だった。前回のCodinGame参加日記にも書いたが、このコンテストは

  • ランキングはリーグ制
  • ウッドリーグ3部からスタート
  • リーグボスを倒すごと、ウッド2→ウッド1→ブロンズ→シルバー→ゴールド→レジェンドとランクアップする
  • ランクアップとき、ルールが追加されることがある

の特徴がある。マッチを美しいグラフィックで観戦できるのが楽しい。
https://www.codingame.com/replay/243115997


ゲームルール概要

  • ターン制の2Dボードゲーム
  • お互い1つ(上位リーグより2つ)の駒を持つ
  • 初期配置はランダム
  • ボード上の各セルは、高さ(0~4)を持つ
  • また、ボード上には移動できないセルもある
  • 駒は上下左右および斜めの8か所に移動できる
  • ただし、移動できるのは現在より低い地点か、1つだけ高い地点のみ
  • また、高さ4のセルへは移動できない
  • 各ターンで1つの駒へ、次の命令を行う
  • MOVE&BUILD …移動して、移動先の隣接セルの高さを+1する
  • PUSH&BUILD(上位リーグより) …隣接する敵駒を押して移動させ、その場所の高さを+1する
  • 下位リーグ:高さ3のセルに最初に到達したほうが勝ち
  • 上位リーグ:高さ3のセルに到着した回数の多いほうが勝ち
  • 敵の駒情報は、味方に隣接してる場合のみ与えられる(上位リーグより)


実装

  • 1手だけ読む
  • ゴール回数、現在地と移動可能な隣接セルでスコアを付ける
  • 現在地・隣接セルともに、高いほどよいスコアにする
  • 敵に近かったらペナルティ
  • 動けなくなったらペナルティ

敵の場所の予想、狭い場所を嫌う仕組みなどは思いついたが実装せず。2手読みさせたら弱くなったのが原因不明。
https://bitbucket.org/yambe2002/codingame-wondev-woman


反省
こんな感じに「それっぽく不具合なく動く」程度でゴールド中位くらいになるようだ。Topcoder MMの黄色下位と同レベルくらいか。
レジェンドリーグからが本番の雰囲気があるので、次回はそこを目指したい。