spadyのメモ帳

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

焼き鈍しのビジュアライズ

さて、SuperConで盛大に焼き鈍しの実装に失敗したので勉強しようと思います。

en.wikipedia.org

Wikiみると良さげなgifがありますね。これを再現してみることにします。

まず、このグラフはなんぞやってことなんですが、調べてもわからなかったのでそれっぽいグラフを設定します。

今回は地形の断面図の標高で代用します。国土地理院地理院地図でカラチ(パキスタン)からイスタンブール(トルコ)の断面図を用意しました。この最高点を探すことにします。 f:id:spady:20210828121930p:plain

実装で参考にした記事はこちらです。 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を2秒にしたんですがそれでも6000枚の画像が出力されました。

ビジュアライズした結果は下の動画にしました。 youtu.be

用意したデータの最高値が2828であるので、焼き鈍しで確かに最高値が得られています。

ちなみに、今回のデータでは量が少なすぎたのか山登り法でも最高値を見つけられています。 ただ、ビジュアライズが目的だったので目的は達成できました。

SuperCon21敗退記

さて、SuperCon21本選に参加しました。

予選についてはこちら spady.hatenablog.jp

焼き鈍しの実装失敗したんですが、なぜなんでしょう。温度変数の調整と近傍のとり方に問題があった気がします。

焼き鈍しもまともに実装できないのに戦えるわけが無いんですよね。

対戦ありがとうございました。

IdeaPad Duetでスタサプを見ながらノートも取りたい

せっかくNoteShelfもスタサプも使えるようになったんだから端末で完結するノート取りの環境を整えたくなりませんか?僕はなりました

結論を3秒で

chromePinP拡張を入れてchromeからスタサプを見ればPinP再生ができるからNoteShelfに浮かべながらノートが取れる!!!

以上

問題は聞き逃すと巻き戻すのがめんどくさいけどしょうがない

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にしたいときにはコマンド1個だけ出力)して最終提出(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月頃に認識しなくなってからは放置するようになりました。

最近になってから久しぶりに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

  • 手元の点数推移 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、楽しかったです!次回は短時間コンみたいなのでそっちも楽しみ
あと、いい加減マラソン解説をみて学んでいきたい

JOI2020/2021 二次予選 参加記

結果は?

f:id:spady:20201213204601p:plain
はい、だめでしたね
(2020/12/18追記:ボーダー188点で予選落ちでした)

振り返り

去年参加して0点を決めたあと、1年間でAtCoderレートを緑まであげられました。

ただ、演習量が圧倒的に足りてないのはそうで、せめて難易度6埋めとか7まで持っていければもうちょっと戦えたんじゃないかという後悔もあります。

いま高2なので今回で最後のJOIでしたが、まあ1年で頑張れるところだったのかなという感じでした。できるなら中学とかから参加してみたかった…

これからどうしよ

高3で参加できそうな大会(競プロ)だとSuperConとPCKですかね。ちょっとマラソン系に興味が出てきたのでそれに挑戦していきたい。 あと何らかの開発をしたいな

まとめ

いかがでしたか?

ガチ精進勢じゃないしほぼ0からの競プロで成長を実感できたのは良かったです. もっと早くからJOI挑戦して行きたかった…