あいねむの競プロ雑記

AHC002 Walking on Tiles 〜問題文読解編〜

AHC002 Walking on Tiles 〜問題文読解編〜

AHC002 Walking on Tiles 〜問題文読解編〜

問題文

大きさが $50 \times 50$ マスの床に、大きさが $1 \times 1$ , $1 \times 2$ (横長), $2 \times 1$ (縦長)の３種類のタイルが敷き詰められている。スタート地点の座標 $(si, sj)$ から移動し、移動経路上のマスに書かれた数字の合計を得点として得ることができるとき、できるだけ高い得点を得られる移動経路を求めよ。ただし、移動には以下の条件がある。

$(i, j)$ から移動できるのは $(i-1, j), (i+1, j), (i, j-1), (i, j+1)$ の４方向
同じタイルは2度踏めない
条件を満たす移動

マニュアルモードで遊ぼう！

Web版ビジュアライザにmanual modeが実装されているときがあります。その場合はまずマニュアルで遊んでみましょー！
百聞は一見にしかず！！！
すぐに問題文を理解できることでしょう。

ビジュアライザ画面

Seed:に適当な数字を入力し、Visualizeボタンを押下します。
□ manual modeにチェックを入れると、方向キーで遊べます！！

私はこれぐらいで飽きました…

入力

TeXで書いたのがはてなに反映されず諦めの境地で問題文のスクショです

$0 \le si, sj \le 49$
タイルの総数を $M$ とすると
$0 \le t_{i, j} \le M-1$
$0 \le p_{i, j} \le 99$

入力具体例

このケースは説明のため床の広さが $3 \times 3$ になっている。本番では $50 \times 50$ となることに注意。

入力受け取り

上記の入力はこのような盤面を表しています。

出力

$(i,j)$ からの移動をそれぞれ $(i−1,j):U$
$(i+1,j):D$
$(i,j-1):L$
$(i,j+1):R$
として、移動経路を文字列で表し、1行で出力せよ。

得点の計算

正の得点を得る

この記事の目標です。
どのAHCでもまずは最初に高い点数を得ようとせず、最小限の点数を得ることをオススメします。
今回の出力は移動経路ですが、WAにならないように、ただ得点を得るだけならば…？

答えはこの問題のFirst AC

おわりに

いよいよ第2回みんなでAHCを解く会コンテスト（a9ua1i0nさんの皆解会という略称をつかっていきたい）が始まりました。今回はサンプルコードの時点でいろいろなことできるようになっている予定です。次回、実装編をお楽しみに！