【AHC042】AHC042に参加しましたが悔しかったので振り返ります【AtCoder】

AHC042 の参加しましたのでその感想を

1 週間遅れですが AHC042 を振り返ります
結果としては 982 人中 631 位でパフォーマンスは 1110 でした
こう見ると低いですがもっと上の順位に行ける可能性がありそうでした (後半で触れます)
https://atcoder.jp/contests/ahc042/submissions?f.User=yoto1980yen

結構シンプルな問題で理解は簡単ですが実装が結構大変な問題ですね
Web 版のビジュアライザで動きを試しやすく見ていて面白いので AHC 始めたての人にはよいかもしれません

自分の点数は 433,853 点でした
この点数で 631 位ですが 1 位は 468,807 点 と大きな差はありません
というのも理論値が 480,000 点のためこれ以上伸ばすのが難しいのでしょう
少しでも改良できればそれだけ順位が大きく変わってくるのは短期コンテストならではですね

ちなみに自分の動きとしては以下のようになってます

ではどのように解いたか振り返っていきます

A - Oni wa Soto, Fuku wa Uchi

節分にふさわしい問題ですね！
20 * 20 の盤面があり鬼と福が各 40 人散らばっています
この盤面の列は上下に、行は左右に動かすことができるので盤面外に鬼だけを上手く取り除くようにする問題
配点として全ての福を盤面に残しながら全ての鬼を取り除くことができれば多くの点数がもらえるのでまずはその状態を目指し出来れば少ない回数で行う様に改良していきます

自分の解法

1. とりあえず外周にいる鬼を取り除く
   どのように解くとしても外側にいる鬼を 1,2 回で取り除けるのであればお得じゃん！という考えで実行しました
   具体的には以下の"＊"にいる鬼を外に取り除きました
   
   ※福が邪魔をして外に出せない場合は実施していません

2. 適当な行に鬼を集めまとめて取り除く
   適当な行を選び上下3マス以内にいる鬼を列を動かすことで一つの行に集め左右に動かすことでまとめて鬼を取り除こうとしました
   
   例えば5行目を選んだ場合
   上下 3 行( 2 ~ 4, 6 ~ 8 )にある鬼を 5 行目までずらします
   また、5 行目に福がいる場合は上下どちらかにずらし 5 行目には鬼だけになるようにします
   あとは5行目を左右にずらして鬼をすべて取り除きます
   ただ、上下に動かす際福が取り除かれないようにするため実装が大変でした

工夫

• 列を動かす処理
  行を左右に動かすのみであれば以下のように簡単にできますが

  # 右に動かす
  list.pop
  list.unshift(".")
  # 左に動かす
  list.shift
  list.push(".")
  

  列を上下に動かす場合結構面倒になります
  rubyではtransposeという二次元配列の行と列を入れ替えるメソッドがあります
  初めにtransposeで列と行を反転させた後に行を左右に動かすことで簡単に列を上下に動かすことができます
  ※再度transposeで行と列を入れ替え忘れないようにする
• 行にまとめた鬼を取り除く方法
  初めは行を20回右に動かし確定で行を空にする方法にしました
  しかし、この方法だと無駄な動作が多くなります
  これを解決するため行の左右から最も近い場所にいる鬼を位置を割り出し
  どちらから削除すれば少ない数で鬼を取り除ききれるか判定を用意しました

ソースコード

汚すぎて見せられません
それでも見たい人はどうぞ

時間切れだったがやりたかったこと

今回行に鬼を集めて外にまとめて取り除く方法をとりましたが行は自分が適当に設定しました

# 433,853 点の場合
[5, 11, 15, 3, 9, 13, 4, 10, 16, 6, 12, 18, 2, 8, 14].each do |x|
# 418,246 点の場合
[4, 10, 16, 5, 12, 17, 2, 8, 18, 14, 6, 15].each do |x|
end

本来であればどの行に鬼を集めるかをランダムに設定し実行制限時間が許すまで何度も試行錯誤して最も良いパターンを出力したかったですが今回はできませんでした
なんとこの問題の初回提出がコンテスト終了10分前！

試してみる

ではランダムに行に鬼を集めて取り除く処理にしたらどれだけ点が上がるのか試したいと思います
自分の最終提出からの変更点は以下になります

• 鬼を集める行をランダムに設定する
• 実行時間制限である 2s ぎりぎりまでパターンを試しもっともよいものを出力する

はたして...

あれ？おかしいですね
全然点数が上がりませんでした

考察

点数が伸びない原因として 2 つ考えました

1. 試行回数が少ない
   1 回実行しただけのパターンでも 100ms かかっているので試行回数が少ないのが点数が伸びないのではと考えました
   transposeで行と列を入れ替える方法は実装としては簡単ですが実行時間が長くなっている要因でもあります
   試行回数を積むのであればtransposeは使うべきではなかったのでしょう
2. デバック不足
   いくつか出力を確認すると福を取り除いてしまっているケースがありました
   はじめに述べましたがこの問題では全ての鬼を取り除く且つ全ての福を取り除かない事が大事です
   操作の回数が増えようとも上記の状態になれば点数は高くなるため福が取り除かれないようにする事が先決でした

たらればでのんきに恵方巻食ってなかったらもっと順位伸びたのではと考えてましたが今回点数が伸びなかったので救われましたね
いいえ、救われてはないですね