spadyのメモ帳

技術ブログにしたいけどどうなることやら。まだ素人

#AHC001 参加記

結果

AtCoder環境

[50ケース]37736498710
[システムテスト] 754,636,906,454 (2021/03/16追記)

手元環境

[50ケース]37541990842
[1000ケース]751978903768

  • 手元の点数推移 f:id:spady:20210314185716p:plain
    横軸は時間経過と見てください。あと桁が飽和してそうなのは目をつむってください

方針

まず、入力で与えられる点(以下:基点)を必ず一つ含むようにグリッドを組む
そのあと、基点のマスから要求面積を超えないように左にのばせるだけ伸ばしたあと、同様に右に伸ばして、ちょっと多かった分は内側方向に縮めることで対応する。それでも多い場合は下端をずらすことで調整した

反省としてはスコアリング関数も使わなかったし、まともな探索もしないため動作が46msぐらいで終わってしまってもったいないこと。どう探索したらいいのかは終わったあとに#AHC001で他の人の考察を参考にする予定
以下はビジュアライザ(seed = 49) f:id:spady:20210314192554p:plain

やったこと

ローカルジャッジの作成

bashで作成
一応コードを置いておきますがbash的に良いコードかどうかはわかりません

#!/bin/sh

score=0
penalty=0

g++ -Isrc -std=c++17 -O2 ./submit.cpp -o ./submit.out

for ind in {0..49}
do
    "touch" "./tools/out/00${ind}.txt"
    "./submit.out" < "./tools/in/00${ind}.txt" > "./tools/out/00${ind}.txt" 
    "./tools/target/release/vis"  "./tools/in/00${ind}.txt" "./tools/out/00${ind}.txt" > "./tools/stderr/00${ind}.log"
    DATA=`cat ./tools/stderr/00${ind}.log`
    INT=${DATA}
    score=`expr ${score} + ${INT}`
    ZERO="0"
    if [ ${INT} = ${ZERO} ]; then
        penalty=`expr ${penalty} \+ 1`
    fi
    echo "${ind} gets ${INT} points"
done

echo "Total Score : ${score}"
echo "Total Penalty : ${penalty}"

d=`date "+%Y/%m/%d %H:%M:%S"`
echo "${score} , ${d}" >> "./result_manage.csv"
#echo "${score} , ${d}" >> "./system-expect.txt"

プレテストではペナルティが影響するのでペナルティカウント(提供Judgeが0点を返すとき)を途中追加しました

実装

方針は前述の通りです いらないところを削ってないのでちょっと見づらいと思いますが最終提出貼っておきます
提出コード

良かった点

  • ほとんどマラソンの典型を知らなくて貪欲でもないのにメイン層(体感)(プレ45G点)より10G下ぐらいに持っていけたこと
  • Gitをローカルで使っていて快適だった(実際に最終提出は一回Gitでコードを差し戻してから書いた)
  • VSCodeの拡張に助けられた(主にGitHistoryとSVGViewer)

改善点

評価関数の作り方がよくわからなかった
たぶんグリッドの貼り方に問題がありそう

最後に

AHC、楽しかったです!次回は短時間コンみたいなのでそっちも楽しみ
あと、いい加減マラソン解説をみて学んでいきたい