キミは「AtCoder Heuristic Contest」を知っているか！？
この記事は琉大AdventCalender2022、12/21参加記事です！
前日記事はYoshisaurさんの記事です!
Twitterとアカウントが違うって？このアカウントは競プロ用に作ったものだから許してヒヤシンス
以下、CV:ずんだもんでお送りします
AtCoderHeuristicContest(AHC)の話
Competitive Programingのジャンルの一つにマラソンというのがあってだな、Algoと比べて厳密解を出せないもののより高精度なプログラムを作成することを目的としたコンテストなのだ
競技プログラミングを日本語でやろうとしたときに上位の選択肢に出てくるAtCoderもそういったコンテストをやっているのだ。昔はマラソン型というジャンル分けだった(TopCoder Marathon Match 略:MM)のが公式レート導入に伴いHeuristicと名前を変えているのだ！
企業主催でAHCの名を冠していないこともあるけどまぁここはマラソン形式のコンテストのことをAHCって言っているのだ！
楽しさ
アルゴとくらべて厳密解がでないことにモヤッとボールを投げる人もいると思うのだ。それもわかるのだ！ただ、自分で考えた方針で順位表の順位が一気に上がったときの快感はAHCぐらいじゃないと味わえないのだ！
ずんだもんはゲノコンでいい感じの順位を取れてからAHCの快感を求めて参加するようになったのだ！
まとめ
AHCは楽しいのだ
明後日からは日立北大ラボプログラミングコンテスト2022っていう問題読解/実装/激重コンテスト(予想)が開催されるのだ！
頑張るのだ！
焼き鈍しのビジュアライズ
さて、SuperConで盛大に焼き鈍しの実装に失敗したので勉強しようと思います。
Wikiみると良さげなgifがありますね。これを再現してみることにします。
まず、このグラフはなんぞやってことなんですが、調べてもわからなかったのでそれっぽいグラフを設定します。
今回は地形の断面図の標高で代用します。国土地理院の地理院地図でカラチ(パキスタン)からイスタンブール(トルコ)の断面図を用意しました。この最高点を探すことにします。
実装で参考にした記事はこちらです。 gasin.hatenadiary.jp
実装コードはこちら
#include <bits/stdc++.h> using namespace std; const int INF = 1 << 30; //カラチからイスタンブールまでの断面図標高 by 国土地理院 int elevation[] = { 30, 35, 95, 26, 3, 81, 87, 144, 217, 234, 101, 956, 268, 447, 500, 662, 574, 895, 1071, 979, 1016, 1398, 1107, 1043, 998, 920, 962, 1002, 940, 1351, 768, 1051, 1000, 905, 819, 780, 759, 723, 860, 959, 1052, 1251, 1309, 1105, 1368, 1415, 1841, 1625, 1543, 1556, 2037, 2228, 1939, 2157, 2087, 1796, 1591, 1526, 1474, 1459, 1359, 1567, 810, 518, 475, 500, 524, 508, 402, 298, 272, 269, 303, 320, 352, 289, 336, 323, 313, 310, 301, 383, 511, 1388, 1159, 1228, 2458, 1750, 1413, 1583, 2066, 2445, 2663, 1976, 2040, 1890, 1920, 1956, 1789, 1433, 1200, 1034, 929, 925, 1006, 1358, 1808, 2037, 1861, 1533, 1440, 1070, 968, 963, 965, 986, 1042, 1183, 1312, 1486, 1801, 1973, 2060, 2349, 2029, 1449, 1313, 1324, 1296, 1499, 1412, 2006, 2061, 1867, 2429, 1614, 2828, 2329, 2342, 1676, 1383, 1421, 1948, 1785, 1863, 1884, 1861, 1824, 1870, 2036, 1741, 1715, 1617, 1719, 1847, 1968, 1697, 2012, 2292, 2049, 2037, 1801, 1773, 1741, 1968, 2027, 1997, 1911, 2067, 2116, 2308, 2421, 1817, 1717, 1957, 2040, 2146, 1650, 1974, 1197, 1469, 1922, 2286, 1406, 1360, 820, 1450, 855, 670, 673, 1094, 1344, 1613, 1721, 1185, 881, 982, 968, 913, 1484, 868, 1343, 1991, 900, 1275, 1247, 908, 848, 928, 660, 909, 710, 656, 667, 575, 695, 734, 704, 743, 889, 948, 875, 1016, 1343, 1440, 1475, 1285, 1372, 1394, 1657, 1179, 707, 796, 1198, 1157, 1254, 1511, 1410, 1622, 1505, 1571, 1764, 1741, 1873, 1535, 1379, 1252, 1179, 1663, 1702, 1641, 1185, 1094, 1155, 1122, 1061, 1193, 1122, 922, 953, 931, 863, 761, 1000, 1120, 1144, 884, 1383, 1166, 1022, 1041, 963, 1249, 1075, 1390, 1543, 1159, 1503, 1438, 1154, 948, 1226, 1311, 1648, 426, 33, 30, 36, 315, 196, 210, 368, 277, 107, 150, 76}; struct Timer { public: Timer() { restart(); } void restart() { m_start = std::chrono::steady_clock::now(); } auto elapsed() { std::chrono::steady_clock::time_point en = std::chrono::steady_clock::now(); auto dur = en - m_start; return std::chrono::duration_cast<std::chrono::milliseconds>(dur) .count(); } private: std::chrono::_V2::steady_clock::time_point m_start; }; int main() { Timer tim; std::random_device seed_gen; std::default_random_engine engine(seed_gen()); // 0以上9以下の値を等確率で発生させる std::uniform_int_distribution<> dist(0, 295); const int TIME_LIMIT = 2 * 1000; double start_temp = 1000, end_temp = 10; // 適当な値を入れる（後述） long long start_time = tim.elapsed(); // 開始時刻 int pre_score = elevation[dist(engine)]; // mountain while (tim.elapsed() < TIME_LIMIT) { int d = dist(engine); int new_score = elevation[d]; long long now_time = tim.elapsed(); // 温度関数 double temp = start_temp + (end_temp - start_temp) * (long long)(now_time - start_time) / TIME_LIMIT; // 遷移確率関数(最大化の場合) double prob = exp((new_score - pre_score) / temp); if (prob > (rand()%INF)/(double)INF) { pre_score = new_score; cerr << d << "\n"; cout << "Score : " << pre_score << "\n"; } } cout << "Final Score : " << pre_score << "\n"; }
これをmatplotlibでビジュアライズしました。 コードはこちらです。
from matplotlib import pyplot as plt from matplotlib import animation as animation fig = plt.figure() ims = [] x = list(range(296)) x1 = [30, 35, 95, 26, 3, 81, 87, 144, 217, 234, 101, 956, 268, 447, 500, 662, 574, 895, 1071, 979, 1016, 1398, 1107, 1043, 998, 920, 962, 1002, 940, 1351, 768, 1051, 1000, 905, 819, 780, 759, 723, 860, 959, 1052, 1251, 1309, 1105, 1368, 1415, 1841, 1625, 1543, 1556, 2037, 2228, 1939, 2157, 2087, 1796, 1591, 1526, 1474, 1459, 1359, 1567, 810, 518, 475, 500, 524, 508, 402, 298, 272, 269, 303, 320, 352, 289, 336, 323, 313, 310, 301, 383, 511, 1388, 1159, 1228, 2458, 1750, 1413, 1583, 2066, 2445, 2663, 1976, 2040, 1890, 1920, 1956, 1789, 1433, 1200, 1034, 929, 925, 1006, 1358, 1808, 2037, 1861, 1533, 1440, 1070, 968, 963, 965, 986, 1042, 1183, 1312, 1486, 1801, 1973, 2060, 2349, 2029, 1449, 1313, 1324, 1296, 1499, 1412, 2006, 2061, 1867, 2429, 1614, 2828, 2329, 2342, 1676, 1383, 1421, 1948, 1785, 1863, 1884, 1861, 1824, 1870, 2036, 1741, 1715, 1617, 1719, 1847, 1968, 1697, 2012, 2292, 2049, 2037, 1801, 1773, 1741, 1968, 2027, 1997, 1911, 2067, 2116, 2308, 2421, 1817, 1717, 1957, 2040, 2146, 1650, 1974, 1197, 1469, 1922, 2286, 1406, 1360, 820, 1450, 855, 670, 673, 1094, 1344, 1613, 1721, 1185, 881, 982, 968, 913, 1484, 868, 1343, 1991, 900, 1275, 1247, 908, 848, 928, 660, 909, 710, 656, 667, 575, 695, 734, 704, 743, 889, 948, 875, 1016, 1343, 1440, 1475, 1285, 1372, 1394, 1657, 1179, 707, 796, 1198, 1157, 1254, 1511, 1410, 1622, 1505, 1571, 1764, 1741, 1873, 1535, 1379, 1252, 1179, 1663, 1702, 1641, 1185, 1094, 1155, 1122, 1061, 1193, 1122, 922, 953, 931, 863, 761, 1000, 1120, 1144, 884, 1383, 1166, 1022, 1041, 963, 1249, 1075, 1390, 1543, 1159, 1503, 1438, 1154, 948, 1226, 1311, 1648, 426, 33, 30, 36, 315, 196, 210, 368, 277, 107, 150, 76] m = [] cnt = 0 fig, ax = plt.subplots(figsize=(15,7),dpi=50) while True: if cnt > 0: plt.cla() cnt += 1 try: input_ = input() except EOFError: break im = plt.plot(x,x1,color="gray") im2 = plt.plot([int(input_),int(input_)],[0,3000],color="red") text = ax.text(0,3000,cnt,size=15,color="green") text2 = ax.text(20,3000,x1[int(input_)],size=15,color="green") ims.append(im +im2 + [text] + [text2]) plt.savefig("./img/{}".format(cnt))
TLを２秒にしたんですがそれでも6000枚の画像が出力されました。
ビジュアライズした結果は下の動画にしました。 youtu.be
用意したデータの最高値が2828であるので、焼き鈍しで確かに最高値が得られています。
ちなみに、今回のデータでは量が少なすぎたのか山登り法でも最高値を見つけられています。 ただ、ビジュアライズが目的だったので目的は達成できました。
SuperCon21敗退記
さて、SuperCon21本選に参加しました。
予選についてはこちら spady.hatenablog.jp
焼き鈍しの実装失敗したんですが、なぜなんでしょう。温度変数の調整と近傍のとり方に問題があった気がします。
焼き鈍しもまともに実装できないのに戦えるわけが無いんですよね。
対戦ありがとうございました。
SuperComputing Contest 2021 参加記
What is SuperCon?
悲報
筆者の居住地、沖縄県では多くの市町村で6/7 ~ 6/18まで休校措置が取られ、期間中の部活動が一切認められないようだった
問題公開(6/3)から6/6(Sun)までの3,4日しか参加できてない ->制約違反で差し替えを1回行った
やらかし
出力制約 ($k \geqq 1$)を見ていませんでした…
運営さんに差し替え可能か聞いたところ、再提出で可能なようなので$k \geqq 1$に対応(出力個数を0にしたいときにはコマンド１個だけ出力)して最終提出(06/17)
-algo.txt
提出物そのまま記載
#方針
YES/NO判定については、行くべき場所と行ける場所の比較を行うことで判定ができる。
行ける場所の探索中に使用コマンドをメモすることで、使用したコマンドを出力することもできる。
# 実装方針
まず、与えられた障害物の情報をもとに、グリッドの(y,x) = (1,1)の連結成分の大きさを求める。
求める際は、全マスに対して{上,下,左,右}をチェックしUnionFindを用いてまとめた。
Unionfind上での座標の扱いは(y,x)ではなく(y*N + x)として整数で持っている。
この値が後のコマンドを用いて到達すべきマスの個数となる。
また、コマンド長でコマンドが格納されている配列をソートしているが、これは移動距離の少ないコマンドがより汎用性があると考えたためである。
BFSで使うグリッド(コードではvector v)は隣接リストで情報を持っており、BFS中でははじめに入れたものから使用可能か確認するため、汎用性の高いと思われるコマンドから隣接リストに入れる必要があった。
実際に到達できる箇所を求めるにはBFSを使う。
そのためにはまず、グリッドグラフの辺をはらないといけないため、まず辺を張る。
張り方は全マスに対してそれぞれのコマンドが実行可能かどうかを調べる。
手法としては、ランレングス圧縮をかけたコマンド文字列と、グリッドの縦横方向それぞれの累積和を使用する。
こうすることで愚直にシュミレーションする場合と比較して高速化が可能
BFSを行う際に、遷移のときに使用したコマンドをsetに順次入れていくことで、使わなかったコマンドを出力しないことができる。
初めはコマンド文字列を愚直にシュミレーションしていたけれど、そんなことしてたら実行時間が10s超えが当たり前になったので累積和＆ランレングス圧縮で乗り越えた。
-env.txt
提出物そのまま記載
# 時間 generator.c で0-100までのランダム生成したテストケース100個、N=200指定して生成したテストケース20個について、 平均実行時間 0.973 s, 最大実行時間 4.817 s,最小実行時間 0.01933 s (python subprocessで一括実行し、処理時間をtimeモジュールで計測) # 使用コンパイラ g++ (Ubuntu 10.3.0-1ubuntu1~18.04~1) 10.3.0
今回のローカルジャッジ
import subprocess import sys import time def compile() : subprocess.run( "cd /mnt/e/Marathon_Comp/SuperCon/2021/ && g++ -std=gnu++17 -Wall -Wextra -O2 ./submit.cpp -o ./submit.out", shell=True) def main(): Score = 0 TestCase = 200 average = 0.0 max_time = 0.0 min_time = 100 for i in range(TestCase): #subprocess.run("touch ./out/output{}.txt".format(i+1), shell=True) print(i+1) start = time.time() subprocess.run( "/usr/bin/time -v ./submit.out < ./input/qual_random_{:02}.in > ./output/qual_random_{:02}.out 2> ./stderr/qual_random_{:02}.log ".format(i+1, i + 1, i + 1), shell=True,stderr=subprocess.PIPE) elapsed = time.time() - start average += elapsed max_time = max(max_time,elapsed) min_time = min(min_time,elapsed) subprocess.run("./mem_check.out < ./stderr/qual_random_{:02}.log".format(i+1), shell=True) print("Elapsed time : ",elapsed) print("Execute Done!") print("average time = {}, max_time = {}, min_time = {}".format(average / TestCase,max_time,min_time)) if __name__ == "__main__": compile() print("Compile Finished") if len(sys.argv) < 2: main() elif sys.argv[1].isdigit(): i = int(sys.argv[1]) runner = subprocess.Popen( "./submit.out < ./input/qual_random_{:02}.in > ./output/qual_random_{:02}.out ".format(i, i), shell=True) print(runner.stderr) else: print("Argument may be not correct")
実行時間とメモリ使用量(KB)も取れるようになった
特に今回はメモリ使用量が気になったから取れるようになって割と楽できた。ただ、python的には合法な書き方かどうかは知らない
ローカルジャッジで出力が条件満たしてるかのチェックがpython技能低くてできなかったけど大丈夫かな…？
最後に
TLを眺めてる感じ落ちてそうで怖い
予選通りました！！！！！
Oculus Rfit S が認識しなくて1年、原因はUSBポートでした
3行でまとめて
2020年春ごろからOculusRiftSがOculusソフトウェアに認識されない状態が続いていた。 USB3.0増設ポート(PCIe x1)を使用した場合、正常に認識するようになった。
ことの発端
RiftSの使用を始めたのが2019/05/22頃でした。当時の環境がIntel core i5 4440/Geforce GTX960だったと思います。 当時は正常に認識し、動作も正常でした。
以降、何度かUSBの認識がうまく行かなかったりしましたが、USBポートを変えたりOculusSoftwareの再インストールなどで解消されていました。
2020年の7月頃に認識しなくなってからは放置するようになりました。
いい加減RiftSを復旧させたい
— Spady (@Spady_JP) 2020年7月25日
最近になってから久しぶりにVRをしたくなって出してきたはいいもののやっぱり動作せず、色々試してみることにしました
環境
OS : Windows10 Home
CPU : Ryzen 3700X
RAM : 16GB
GPU : Geforce 1660Ti
ながれ
- OculusSupportに泣きつく
サポート切れ(サポート期間は1年)で修理・交換は無理 メールの中で、USB 3.0じゃないと正常に動かないかもしれないということが書いてあった (←!?)
フロントパネル(USB 3.0)に試しに挿してみたらどうやら正常に認識してそう
バックパネル(USB 3.1gen2以降)はだめっぽい
USB拡張カード(PCIe)を買ってきました
PCショップでUSB拡張カードを買ってきました
www.kuroutoshikou.com
今の所はこれで正常に動いています(2020/05/02現在)
まとめ
私の場合は動作不良の原因がUSB3.1gen2以降のUSBポートにありましたがあくまで一例であり原因が異なることもあります。自己責任でお願いします
また、正直なところ、新しく買う場合にRiftSとQuest2を比較するなら、Quest2が断然いいような気がします(未所持)
最後に、今回の事例が何らかの手助けになれば幸いです
#AHC001 参加記
結果
AtCoder環境
[50ケース]37736498710
[システムテスト] 754,636,906,454 (2021/03/16追記)
手元環境
[50ケース]37541990842
[1000ケース]751978903768
- 手元の点数推移
横軸は時間経過と見てください。あと桁が飽和してそうなのは目をつむってください
方針
まず、入力で与えられる点(以下:基点)を必ず一つ含むようにグリッドを組む
そのあと、基点のマスから要求面積を超えないように左にのばせるだけ伸ばしたあと、同様に右に伸ばして、ちょっと多かった分は内側方向に縮めることで対応する。それでも多い場合は下端をずらすことで調整した
反省としてはスコアリング関数も使わなかったし、まともな探索もしないため動作が46msぐらいで終わってしまってもったいないこと。どう探索したらいいのかは終わったあとに#AHC001で他の人の考察を参考にする予定
以下はビジュアライザ(seed = 49)
やったこと
ローカルジャッジの作成
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、楽しかったです！次回は短時間コンみたいなのでそっちも楽しみ
あと、いい加減マラソン解説をみて学んでいきたい
