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を眺めてる感じ落ちてそうで怖い~~

予選通りました！！！！！

spadyのメモ帳

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