Chokudai Contest 001にて

シェアする

  • このエントリーをはてなブックマークに追加

こんばんは。

昨日ニコ生で「月刊少女野崎くん」の一挙放送を見たのですが、めちゃくちゃ面白いですね。

りえりー(高橋李依さん)の次に好きな声優である亜李ちゃん(小澤亜李さん)がヒロインの女の子をやってて、演技がとても良かったです。全キャラ立っててハズレ回が無くて素晴らしかったです。

今は「ちはやふる」の前半一挙を見ながら書いてます。これも思った以上に面白い。

なんか宮野真守さんの声をいっぱい聞いてる気がする。

それはさておき、本日AtCoderにて開催された試験的マラソンマッチ「Chokudai Contest 001」にて、koukiというアカウント名で873615点で最終順位6位を取ることができました。

我ながらなかなか健闘できたと思うので、強い人っぽく自分のやり方を解説などしてみたいと思います。

言語はC#です。chokudaiさんのマネです。嘘です。

準備

ルールはこちらです:http://chokudai001.contest.atcoder.jp/tasks/chokudai_001_a

とりあえず何をしたらいいのか分からないので、色々考えてみます。

紙の上で色々試して、分かったことを書いていきます。

分かったこと:1つずつ下がっていく経路をまとめて1減らせる

4 3 2 1 → [3] 3 2 1 → 3 [2] 2 1 → 3 2 [1] 1 → 3 2 1 [0]

([]が選択して1減らしたマス)の変化(1手)は、

4 3 2 1 → [3 2 1 0]

([]が選択した、連続して1下がっていく経路)の1手と考えられます。

分かったこと:経路は、最大値の手数で全部0にできる

4 3 2 → [3 2 1] → [2 1 0] → [1 0] 0 → [0] 0 0

は、

4 3 2 →4手→ [0 0 0]

と考えられます。

分かったこと:分岐は関係ないっぽい

これ面白いです。

4
5
6 5 4 3 2 1 (他全部0)

は、右方向を先に消して、残った上の4,5を消すと、6+5=11手。

上方向を先に消して、残った右の5,4,3,2,1を消すと、6+5=11手。

変わりませんね。

つまり、「最長経路を探索して消す」という戦略は不要なのではないか?と思いました。

(もっと複雑な場合にどうなるかは分かりません)

以上の準備を踏まえて、私が考えた作戦を順番に解説していきます。

作戦5まであります。長いです。

作戦1:貪欲法っぽい作戦!

とりあえず色々考えてみました。

5 4 3 2 1 が並んでるとき、絶対に5から消すのが良いですね。

4から消すと、4で始まる経路を消す4手+5のみを消す5手=9手必要です。

したがって「常に最大値のあるマスから消していく」という戦略をまず思いつきました。

3 2 1 0 0
5 4 3 2 1

を考えましょう。おそらく、上段3手+下段5手=8手が最小でしょう。

最大値選択でシミュレーションしてみます。

左下の5を選んで、5,4,3,2,1を1減らす操作を2回したとき、

3 2 1 0 0
3 2 1 0 0(現在2手)

となって、次に、先に見つかる最大値である左上の3を選んで

2 1 0 0 0
3 2 1 0 0(現在3手)

となりますが、次に3を選んだとき、上の経路を選ぶかもしれません。そのとき、2回引いて

0 0 0 0 0
1 2 1 0 0(現在5手)

となります。次に、2から始まるどちらかの経路(どちらでもいい)を選んで2回引いて、

0 0 0 0 0
0 0 1 0 0(現在7手)

最後に1を引いて、合計8手です。

おや、なんか途中で経路がぐちゃぐちゃでしたが、結果は8手で理想の経路選択と同じになりましたね。

①選択マスに最大値マスをセット
②選択マスを経路に追加
③選択マスの上下左右に1小さいマスがあればそれを選択し、②へ。無ければ④へ
④経路に沿って座標を出力し、経路上のマスの数値を1減らす

というアルゴリズムで良い感じっぽいです。③で「複数あるけどどっちが良いだろう?」と考えなくていいっぽいのがありがたいです。

私は②で選択マスを1減らして座標を出力するようなプログラムを書いたのですが、後の作戦で上のような「経路保存→一気に実行」変えました。経路はListでやってます。

0になったら経路を確定させないといけないということに注意です。1の隣に0のマスがあるからそれも下げよう!とならないように。

「貪欲法っぽい作戦」のコードはこちらです(一発目の提出で815581点。瞬間11位になれました)→ http://chokudai001.contest.atcoder.jp/submissions/667526

コメント無いので見づらいですね。PairはKeyValuePair<int,int>のことで、KeyとValueでint型の2つの値を用意できます。int[2]で良くね?って思いますが、まあこれでやってます。

作戦2:壊れた坂道を修復作戦!

ながら見してるちはやふるが12話の良いシーン(切り抜きのシーン)です。泣ける。

さて、作戦1で1位が取れないのはなぜだろう?と考えて考えて、思いついたのがこれです。

7 6 5 5 4 2 1

作戦1だと、

[7 6 5] [5 4] [2 1]

となって、7+5+2=14手ですが、先に[5 4]を一回消すと

[7 6 5 4 3 2 1]

になって、1+7=8手で済みます。凄い!

(真っ直ぐな坂道だったらいいのに一部の地面が隆起したせいで高い段差ができており、これを修復して真っ直ぐな坂道にしてから消す、という感覚での作戦名です。)

でも、こんな都合の良いパターンを判断するのも難しいです。

7 6 5 5 4

だとどうでしょう、これも、[5 4]を先に消すと1+7=8手となり、12手よりも大きく下がります。

つまり、「最大値から下って行って詰まった時に、同じ数字と隣接してたら、その隣接マスから始まる経路を先に消す」というルールが良さそうです。

これは、作戦1の「③選択マスの上下左右に1小さいマスがあればそれを選択し、②へ。無ければ④へ」において、後半を「無ければ同じ数字のマスが上下左右に無いか探して、あればそれを選択マスにして経路をリセットして②からやり直す。無ければ④へ」にしてやると大丈夫です。

ちなみに、一度選択したマスを「選択済み」として再び訪れないようにしないと、

0 3 3 0

みたいなので、永遠に左の3と右の3を行き来します。bool visited[30,30]を用意し、選択マスをtrueにしました。経路を出力するたびにfalseでリセットしています。

提出コードがこちら。842075点で瞬間2位になれました。→http://chokudai001.contest.atcoder.jp/submissions/667736

作戦3:壁壊し作戦!

作戦2のちょこっと改良版です。

作戦2では、同じ高さのところの場合のみ地ならしをしましたが、高い壁であっても有効なようです。たとえば、

9 8 7 6 5 8 7 6 5 4 3

に対して、作戦1だと

[9 8 7 6 5] [8 7 6 5 4 3]

で9+8=17手ですが、右の経路をさきに4回下げると

9 8 7 6 5 [4 3 2 1 0 0]

となり、4手+一気に9手=13手で全部0にできます。

つまり、最大値から下がって行って、詰まったときに壁があったら、その壁が低くなるまで下げていけば良いのです。だから壁壊し作戦!。

しかし、注意点があります。

9 8 7 6 5 4 7 6 5 4 3
.             0 8 0

となっている場合(8が7の下です)、壁壊し作戦!を適用して[7 6 5 4 3]を4回下げると、下の8が取り残されて、それを消すのに8手必要で、合計4+9+8=21手必要になります。

一方、[9 8 7 6 5 4]と折れ曲がった[8 7 6 5 4 3]を別々に消すと9+8=17手になります。

したがって、壁が他のマスからの坂の一部になっている場合、壁壊しはダメです。

そこで、「壁マス(上記の例でいう右の7のマス)が周囲4マスのどれよりも高い場合のみ、そのマス始まる経路を下げる」というルールにしました。

それがこちら。864553点でした。→http://chokudai001.contest.atcoder.jp/submissions/668125

(上記コードで「極高」というのは、周囲どのマスよりも低くない、という意味で使ってる造語です。極大でいいんですが、高さのイメージでやってたので。周囲と同じ高さまで許容されているということを示すために、最高ではなく極高と書いています)

作戦4:壁巻き込み作戦!

作戦3で最適にならないケースを探しました。

9 8 7 6 5 8 7 6 5 4 3
.          0 9 8 7 6 5 4

(8の下に9があります)です。

この場合、作戦3では「下の9が取り残されて損だから壁壊しは行わない」でしたが、そうすると[9 8 7 6 5]と折れ曲がった[9 8 7 6 5 4 3]と下に残った[8 7 6 5 4]で9+9+8=26手掛かります。

(この場合、壁マスは左上の9から右へ下がっていった先の5の右にある8です。8から先の経路を4つ下げるのが壁壊しです)

しかし、この場合は、[8 7 6 5 4 3]を壁壊しで4つ下げて、上段を9手で一気に消して、下段を9手で消すと4+9+9=22手になります。

今回は、壁壊しをしてもしなくても下段に残るので、大した損は無く、壁壊しの得が大きいということになります。難しいです。

なんやかんや考えた結果、「壁マスを含む別方向からの経路がある場合は、その経路全体を必要分下げる(壁を巻き込む経路を下げる)」というのが良さそうです。

上記の例では、壁マス8の下に9があるので、9から始まって壁の8以降を巻き込む経路[9 8 7 6 5 4 3]全体を4つ下げて、上段を一気に消すと、4+9=13手で下図になります。

0 0 0 0 0 0 0 0 0 0 0
.          0 5 8 7 6 5 4(現在13手)

(壁巻き込みによって下段の9が5になっています。)

次に、[8 7 6 5 4]を4回下げて、5から一気に消すと、13+4+5=22手。これで最適です。

4+9+9が4+9+4+5になっていますが、結果は同じですね。

さて、下の図を見てみましょう。

6 5 4 3 5 4 3 2
.     9 7 6 5 4 3

(上段右の5の下に6があります)

このとき、壁を巻き込む経路に2回折れ曲がった[7 6 5 4 3 2]がありますが、これを壁巻き込みで3回下げて、上段を6手で一気に消したら、下図になります。

0 0 0 0 0 0 0 0
.     9 4 3 5 4 3(現在9手)

次に、9を4回下げて5にして、、右の[5 4 3]を壁壊しで3回下げて、下段の[5 4 3 2 1 0]を一気に消すと、合計で9+4+3+5=21手掛かります。

しかし、壁巻き込みの経路のことを考えて、先に9を一つ下げて

6 5 4 3 5 4 3 2
.     8 7 6 5 4 3(現在1手)

にすると、[8 7 6 5 4 3 2]を壁巻き込みで3つ下げて、上段を6手で消して、

0 0 0 0 0 0 0 0
.     5 4 3 5 4 3(現在10手)

になり、さっきと同じように壁壊し2手と下段一掃の5手で、10+2+5=17手になります。これが最適っぽい。

ということで、「最大値から1ずつ下がっていく経路を辿り、壁にぶつかったら、そこから上下左右に高い方へ登っていき、もう登れないマス(極高点)に着いたらそこを起点として同じ探索をする。ただし一度訪れたマスはもう訪れない」というアルゴリズムにします。

それがこちら。873615点で、私の最終得点です。最終6位。→http://chokudai001.contest.atcoder.jp/submissions/668755

かなり高い点数が出ました。そして、ここから先はどうやったら点数が伸びるのか分かりませんでした。あきらめムードです。

でもここで足を止めないのが知波単精神です(違う)。

最後の最後まで突っ走ります。

作戦5:わるあがき作戦!

最後の作戦です。

作戦4の最後に「私の最終得点です。最終6位。」って書いてますが、終わりじゃないんですね。

さて、「もうここからは点数を上げられないよ~」と思ってたまたまやってたがっこうぐらし!の一挙を見始めた私ですが(りえりーと亜李ちゃんがメインキャストやってる俺得アニメです)、最後に思いつきました。

私のコードに、

int[,] d = new int[,] { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };

という行がありますね。

これは、上下左右の4方向を表すベクトルです。「周囲4マスを確認」という操作を、for文で4回まわしてa[現在行+d[i,0],現在列+d[i,1]]とするためにあります。

つまり、これは「上、左、右、下」の順に見ていく、ということになっています。

そして、この順番を変えると、周囲に同じ高さのマスが複数あったときなどに結果が変わり、得点が変わるはずだということになります。

したがって、4の階乗=24通りを全て試せば、新しいアルゴリズムを考える必要なしに点数をちょびっと上げられるのでは!?と思いました。

しかし、Chokudai Contest 001には、「提出は5分以上間隔をあけて」とあります。残り時間は90分程度。しかも途中で風呂に入らなければいけない(我が家では風呂に入る順番が決まっている)。

そこで、色んな順番で試してみて、その結果から点数が上がりそうなまだ試してない順番を考えて提出することにしました。

そして、とにかくたくさんやった結果、なんと!

最初の順番を超えるものは現れませんでした。

……

なぜだ!なぜ最初にあの順番を選んだ私は運が良かったんだ!!

と思いましたが、まあこれも仕方ないこと。最後の提出が惜しくも871773点で更新ならず、最終順位6位が確定しました。

しかし、224人が得点を取った中で6位は大健闘ではないでしょうか。

以上が私の戦略の全てです。お疲れさまでした。

感想

最初に問題を見たときは「どうすりゃいいんだ?」という疑問と、「工夫のしようが無さそうじゃないか?」という感想を抱きました。

しかし、とりあえずの提出で11位になってテンションが上がって、でも「これが11位なら、これが最適じゃないパターンがあるってことだよな……どんな形だ……?」と思って考えてるうちに色々見えてきて、自分のプログラムの弱点を自分で見つけたときがとても嬉しかったです。

そこから自分のプログラムとの闘いで、徐々に順位が上がったり下がったりしながら、ツイッターでの参加者の反応も見ながら、途中でデレステの新イベに参加しながら(絶対特権MASめっちゃ楽しい)、じっくり頭を使えて、楽しかったです。

チームで参加するともっと楽しそう。

ということで、大根001、お疲れさまでした。

chokudai先生の次回作に期待しながら、今日はもう寝ることにします。おやすみなさい。

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする