競プロをしていて役に立ったこと

はじめに

この記事は 競プロ Advent Calendar 2022 八日目の記事です。 卒業研究の中で競プロをしていてちょっとだけ役立ったことを書きます。

競プロ要素がどこにあったか

現在自分が進めている卒業研究では、処理にかかる実行時間を測定することでうまくいったかどうかの評価を行います。同じ研究室の先輩が書いた論文を読んだところ、プログラムを100回程度繰り返し動作させた場合の処理時間の最大値、最小値、平均値が記載されていたので、自分もそれにならって最大値、最小値、平均値を求めることにしました。その中でも、平均値を求めるところで落とし穴があったのでそれを書きます。

実行時間を測定する

研究ではC言語を使っているので、C言語で細かい単位で時間を測定できる方法を探しました。その結果、 timespec という構造体と clock_gettime() という関数を使うことでナノ秒単位で時間を測定できることが分かったため、これを採用しました。 疑似的なソースコードで表現すると下のようになります。

#include <stdio.h>
#include <time.h>
int main()
{
    struct timespec before, after;
    clock_gettime(CLOCK_REALTIME, &before);
    // ここに処理時間を測定したい関数を入れる
    clock_gettime(CLOCK_REALTIME, &after);
    printf("%ld.%9ld\n", before.tv_sec, before.tv_nsec);
    printf("%ld.%9ld\n", after.tv_sec, after.tv_nsec);
    return 0; 
}

あとは after - before を計算するだけ、と言いたいのですが、構造体なのでそう簡単には計算できません。timespec は時間を秒で表現したときの整数部分を表すメンバ変数と小数点以下を表すメンバ変数に分かれているので、繰り上がりが起きた場合のことを考慮する必要があります。これを踏まえた上で、 after - before を計算するコードを書くと以下のようになります。

#include <stdio.h>
#include<time.h>
int main() { 
    struct timespec before, after, result;
    clock_gettime(CLOCK_REALTIME, &before);
    // ここに処理時間を測定したい関数を入れる
    clock_gettime(CLOCK_REALTIME, &after);
    printf("%ld.%9ld\n", before.tv_sec, before.tv_nsec);
    printf("%ld.%9ld\n", after.tv_sec, after.tv_nsec);
    if(after.tv_nsec < before.tv_nsec) {
        result.tv_nsec = after.tv_nsec - before.tv_nsec + 1000000000;
        result.tv_sec = after.tv_sec - before.tv_sec - 1;
    } else {
        result.tv_nsec = after.tv_nsec - before.tv_nsec;
        result.tv_sec = after.tv_sec - before.tv_sec;
    }
    printf("%ld.%9ld\n", result.tv_sec, result.tv_nsec);
    return 0;
}

平均値を求める

実行時間を測定することができたので、それを元に平均値を求めます。

WAになる実装

研究では100回繰り返して平均値を求めるのですが、この記事の中では10回だけ繰り返して計算することにします。

#include <stdio.h>
#include <time.h>
#include <unistd.h>
int main() { 
    struct timespec before, after, result[100], average;
    int i;
    average.tv_sec = 0, average.tv_nsec = 0;
    for(i = 0; i < 10; i++) {
        clock_gettime(CLOCK_REALTIME, &before);
        // ここに処理時間を測定したい関数を入れる
        usleep(999499);
        clock_gettime(CLOCK_REALTIME, &after);
        if(after.tv_nsec < before.tv_nsec) {
            result[i].tv_nsec = after.tv_nsec - before.tv_nsec + 1000000000;
            result[i].tv_sec = after.tv_sec - before.tv_sec - 1;
        } else {
            result[i].tv_nsec = after.tv_nsec - before.tv_nsec;
            result[i].tv_sec = after.tv_sec - before.tv_sec;
        }
        average.tv_sec += result[i].tv_sec;
        average.tv_nsec += result[i].tv_nsec;
        printf("%ld.%9ld\n", result[i].tv_sec, result[i].tv_nsec);
    }
    average.tv_sec /= 10, average.tv_nsec /= 10;
    printf("%ld.%9ld\n", average.tv_sec, average.tv_nsec);
    return 0;
}

これを実行すると

1.   328800
0.999643800
1.   716000
0.999598500
0.999711900
0.999845900
0.999581600
0.999785400
1.   607300
1.   112100
0.599993130

という結果となりました。このように、1.0秒以上のケースと0.9秒のケースが混ざると明らかに間違った答えが返ってきてしまいます。

ACになる実装

timespec の変数を一度 long long 型に変換してから平均値を求めることで、このバグを修正できます。

#include <stdio.h>
#include <time.h>
#include <unistd.h>
int main() { 
    struct timespec before, after, result[100];
    long long average;
    int i;
    average = 0;
    for(i = 0; i < 10; i++) {
        clock_gettime(CLOCK_REALTIME, &before);
        // ここに処理時間を測定したい関数を入れる
        usleep(999499);
        clock_gettime(CLOCK_REALTIME, &after);
        if(after.tv_nsec < before.tv_nsec) {
            result[i].tv_nsec = after.tv_nsec - before.tv_nsec + 1000000000;
            result[i].tv_sec = after.tv_sec - before.tv_sec - 1;
        } else {
            result[i].tv_nsec = after.tv_nsec - before.tv_nsec;
            result[i].tv_sec = after.tv_sec - before.tv_sec;
        }
        average += (long long)result[i].tv_sec * 1000000000;
        average += (long long)result[i].tv_nsec;
        printf("%ld.%9ld\n", result[i].tv_sec, result[i].tv_nsec);
    }
    average /= 10;
    printf("%lld.%9lld\n", average / 1000000000, average % 1000000000);
    return 0;
}

これを実行すると

0.999956600
1.   362300
0.999662700
0.999860000
1.   495200
0.999632900
0.999929000
0.999637000
1.   339900
1.   311800
1.    18740

という結果となりました。これは信用できそうです。

まとめ

感想

解法自体は特に難しくないのですが、研究ではジャッジサーバは存在しないため、バグが生まれそうなケースを自分で考えなければなりません。バグが残っている状況を考えるところで競プロが役に立ったと感じました。

その後

教授に相談した結果、ソースコードの中に平均値を求める実装を書くのではなく、

  1. 1回ごとに実行時間を画面に出力し
  2. 結果をExcelに貼り付けて計算

したほうが良いということでした。そのほうが実行時間の分布も見ることができる上に、実行時間を記録として残すことができるというメリットもあるそうです。(実は競プロは役に立たない???)

最後まで読んでいただき、ありがとうございました。

ICPC 2022 国内予選 参加記

はじめに

今年もICPC国内予選に参加しました。今年のチームメンバーはあめふり君とノブチ君です。 今年は対面でもOKだったようなのですが、去年同様オンライン形式で参加しました。去年から変わった点を挙げるとしたら、Zoomの教育機関向けの支援が終了したため、代わりにDiscordのグループ通話を使った点ですね。

開始前日

全く見ないのはどうかと思ったので、過去問をほんの少しだけ解きました。解いたのは「国内予選2017A」「国内予選2017B」「国内予選2018A」「国内予選2018C」です。本当はもう少し解こうと思ったのですが、前日だったので寝不足になるほうがデメリットが大きいと思い、切り上げて寝ました。

当日

ノブチ君はA問題、あめふり君はB問題、自分はC問題を読んで、実装できそうなら実装を進めることにしました。 今年は去年のように開始した途端にシステムが落ちるといったことがなくて安心しました。 以下、各問題の感想です。

A問題

ノブチ君が特に詰まることなく通してくれました。なので、コンテスト中は問題を読んでません・・・

B問題

あめふり君が、「実装が重い」と言ってました。実際に問題を見ると何だか面倒な感じでした。ただ、解法が全く分からないという訳ではなさそうだったので、バグ等で詰まるまでは任せることにしました。

C問題

自分が担当した問題です。練習日が連続するとn2に比例してパワーアップして、休息日が連続するとn2に比例してパワーダウンするので、上手いことスケジュールを組んだときの実力の最大値を答えてね!という趣旨の問題でした。 何となく休息日-練習日-休息日の順にすると良さそうな気がしたので実装したところ、ほとんどのサンプルは通りました。しかし、練習日が7日で休息日が9日の場合だけ答えが合いません。

20分以上考えても分からないので、bit全探索で答えを探したところ、最初の考えは間違いであることが分かりました。どうやら休息日を小分けにする形で練習日を入れて、余った練習日をひとまとめにすることが最適であるようです。ここで、休息日をどれくらい小分けにするか悩んだのですが、制約を踏まえると休息日をk個に分割するとしてkを全探索しても問題ないと気付きました。

これを踏まえて実装し、何とか正解することができました。ただ、ここまでで1時間半近く経過していました。

D問題

恐らく列の中で切っては(別のゲートに誘導しては)いけない人達がいて、逆に自由に切ってもいい場所があるんだろうなぁということは予想できました。なぜなら、そうでないと答えが非常に大きくなることがないためです。

ただ、どこが1つのゲートに誘導すべき人達なのかがさっぱり分からず、手も出ませんでした。

E問題

自分がD問題を考えている間にノブチ君がある程度まとめてくれていました。正気度は最初0であること、正気度が途中で負になると村から出られないことを考えると、村から出られた人のところは最初に「美しい像」があるということまで考察してくれていました。

次に、村から出るときに正気度が正の場合は村から出られなくなるという条件を踏まえると、最後に通る交差点には「恐ろしい像」があることが分かりました。この2つを合わせると、リストと矛盾しない像の配置があるかどうかを判定できそうです。実際に実装するとサンプルではYes/Noのみを正答できるようになりました。

ただ、リストから確定できない中間部分にどちらの像を配置するべきか分からず、正解にはたどり着けませんでした。

F問題

あめふり君が構文解析できるということだったので、任せました。ただ、復号する際に先頭と末尾のどちらを消すのかが決められず、正解には至りませんでした。一見サンプルなら通りそうな考察まではあめふり君がしていたのですが、自分が反例を見つけてダメだということが分かりました。

G・H問題

難しそうだったので深く読んでいません・・・

感想

終了時の順位表

結果は3完、109位となりました。欲を言えばもう1問通したかったのですが、難しいですね。反省点としては、どの問題を通すのにも予想以上に時間がかかっていたので、練習量が明らかに足りない点が挙げられそうです。また、オンラインでは進捗状況が共有しにくかったので、対面で参加したほうが有利なのではないかと思いました。

去年の時点では今年参加するのか不確かな状況でしたが、引退したにも関わらず部の人達が誘ってくれたお陰で無事参加することができました。本当にありがとうございます!!

自分は院進しないので、今回が人生最後のICPCとなりました。悔いの残る結果でしたが、これからも別の形で競技プログラミングを楽しんでいきたいです。

AHC011参加記

AHC011に参加した感想です。

はじめに

まず問題文を読むと、空きマスを上手く動かして木を作る問題のようです。 もちろん木とは言ってもグラフの木です。 そんなことできるのか?というのが始めに思ったことでした。

ビジュアライザを見る

文章で読んでもよく分からないので、次にWeb版ビジュアライザを見に行くことにしました。 seed=0の初期状態でもscoreが71429となっていました。どうやらどこかが木になっていればOKのようです。

初期状態のビジュアライズ結果
また、共有された画像を見ると木が完成している画像が多数出てきました。どうやら木を作るのはアルゴリズム的に可能なようです。

このパズル、どこかで見覚えあるような?

空きマスを動かして絵を完成させるパズルをどこかで見たはずなのですが、名前が分からないので検索できないことに気付きました。ただ、OpenSiv3Dのサンプルプログラムの中に載っていたことを思い出したので、それを確認しました。どうやら「15パズル」と呼ばれるもののようです。15パズルで検索すると、解法が色々出てきました。完成図さえ分かれば、木を完成させることは可能ということでした。 ただし、木を作ることができなかったので、15パズルの解法を使うことはありませんでした。

ランダムに動かす

木を作る方法が分からないので、とりあえずランダムに動かしてみて得点が上がるならその操作を採用するという方針で実装してみることにしました。

まずは何も操作しない場合を試してみます。

Submission #32106280 - AtCoder Heuristic Contest 011

得点は2869199でした。

次に、試しに操作して点数が上がるならばその操作を採用し、どの操作でも点数が同じならばランダムに操作するように実装しました。ここまで来ると、最初に空きマスがどこにあるか探す関数を作ったり、評価関数を作ったりとヒューリスティックっぽく?なってきました。 評価関数については木のサイズが大きいほどスコアが上がるという条件だったので、UnionFindでそれぞれ木のサイズを求めて、最大値を返すようにしました。すると、得点は5695968になりました。 最初は実行時間制限に間に合うか分からなかったので操作回数を上限の1/3に抑えていたのですが、どうやら余裕で間に合うようです。上限まで操作するようにしたところ、得点は6502898になりました。

ビジュアライザで確認する

これはかえでさんのブログを読んで、この方法は良さそうだな~と前から思っていた方法です。

実録!MC Digital プログラミングコンテスト2022(AtCoder Heuristic Contest 008)参加記 - 競プロ始めました

ビジュアライザを活用し、seedの値を色々変えてバグを探すというものです。本来ならseedを0から100まで全部試すほうが良いのですが、面倒なので切りの良い数字だけ試しました。 明らかに得点が低かった例は、seed=10の場合です。

seed=10の場合

このように閉路を持つグラフがある場合、その部分が塊のようになって、スコアが下がってしまうようでした。 そこで、閉路を解消するように評価関数を変えました。幸い、UnionFindを使っていたので閉路検出は簡単に実装できました。

閉路検出を使った実装を提出すると、得点は6656767になりました。期待したほど伸びていません。ただ、もう一度ビジュアライザを確認すると、確かに閉路はなくなっていることが確認できました。(なぜ得点が伸びなかったのかは不明ですが……)

seed=10、閉路検出を実装した場合

回数を増やす

ここで、実行時間に注目するとわずか30~40ms程度で終了していることが分かりました。そこで、「与えられた初期の盤面から空きマスを移動させて得点を伸ばす」という処理を複数回(20回程度)独立して行い、その中で一番高得点だったものを解答として出力することにしました。その結果、得点は8852284になりました。この方法は上手くいったようです。

移動を効率化する

ここまでランダムに空きマスを動かしてきたのですが、よく考えると上に移動した直後に下に動かしたり、左に動かした直後に右に動かしたりするのは無駄ということに気付きました。 そこで、直前の移動を打ち消してしまうような移動となった場合は移動させず、操作回数としてもカウントしないという実装にしました。 また、評価関数の実装を変えて閉路が存在する場合は得点を減点するようにしました。これにより、より積極的に閉路を解消するようになりました。

提出したところ、最初はバグで操作回数を超えてWAになったり、実行時間制限に間に合わせる目的で試行回数を20回から 10回に減らしたために得点が下がったりしました。しかしそれらを修正した結果、得点は約9000000点(システムテストによって得点が書き換えられたので正確な点数は不明)となりました。

まとめ&反省点

システムテストの結果、得点は547024686点、順位は486位となりました。 反省点としては、問題文をよく読むことが挙げられます。実行時間制限を2秒だと思い込んでいたり(本当は3秒なのに、終わってから他の人の解説を見るまで気付かなかった)、パネルの規則性を読み落としていたり(自力で思いついて勝手に感動していたけど問題文にちゃんと書いてあった)、木ではなくただの連結グラフを作っていたり……

次回は、もう少し順位を上げたいですね。

ZinniaをRaspberry Piにインストールする

オンライン手書き文字認識エンジンのZinniaをRaspberry Piにインストールする。

本体のインストール

前提条件は次の2つ。

  • g++が使える。
  • 文字コードはLFにする。(CRLFではconfigureが壊れる)

次のコマンドを実行する。

$ git clone https://github.com/taku910/zinnia.git
$ cd zinnia
$ ./configure -build=arm
$ make
$ sudo make install

認識モデルのインストール

Zinnia download | SourceForge.netから、認識モデル(zinnia-tomoe-0.6.0-20080911.tar.gz)をダウンロードする。

$ tar zxfv zinnia-tomoe-XXXX.tar.gz
$ cd zinnia-tomoe-XXXX
$ ./configure

Makefileの中から、handwriting-zh_CN.modelhandwriting-zh_CN.model.txtなどを消す。

$ make
$ sudo make install

以上でインストールは完了。

実際に使う

taku910.github.io

上の記事を参考にコードを書く。コンパイル時は

g++ Main.cpp -lzinnia

として、zinniaをリンクさせる。

参考資料

taku910.github.io

www.servernote.net

qiita.com

ICPC2021国内予選参加記

今年もICPC国内予選に参加しました。

今回のチームメンバーはあめふり君とパーシー君です。

去年と同様オンライン形式だったので、メモ帳代わりにhackmd、通話はzoomを使ってやり取りしました。

A問題

恐らく簡単だろうと思って問題を読まずにパーシー君に押し付けました。ごめんなさい。特に引っかかることなく通してくれたので助かりました。

B問題

あめふり君が解きたいと言ったので任せました。ここで時間を浪費してしまいました。何もアドバイスできなくてごめんなさい。

C問題

去年や一昨年のC問題はそこまで難しくなかったので、今年も解けるだろうと思ったら全然違いました。がっつり構文解析で困りました。+のところはどうしようもないですが、-のところは入れ替えることで値が変化します。引く数をできるだけ小さくすることで最大化できそうですが、それ以上のことは分かりません。

D問題

C問題とは違って問題文も比較的単純で一見解きやすそうでした。実際、A, Bの次に正解チーム数が多かったので、ずっと考えていました。

まず風船を多い順に並べてみました。しかし、実装してサンプルを試すと1人少ない結果が返ってきてしまいました。そこまで単純ではなかったようです。サンプルを手作業で実験したところ、

4 3 3 3 3 4 3 3 1
↓3人に渡す
1 0 0 3 3 4 3 3 1
↓1人に渡す
0 0 0 2 2 4 3 3 1
↓2人に渡す
0 0 0 0 0 2 3 3 1
↓2人に渡す
0 0 0 0 0 0 1 1 1
↓1人に渡す
0 0 0 0 0 0 0 0 0

とすると、9人に渡せるようです。残念ながらここまでしか分かりませんでした。何か法則性がありそうなのですが……

 

E問題

ここが一番時間をかけるべき問題だったのかもしれません。問題文を一通り読むとダイクストラ法で解けそうです。そこで、手元にあったダイクストラ法のライブラリをこの問題の形式に合うように改造していきました。

途中でpairをtupleに書き換えるところで詰まりました。pairでは.firstなどを使えたのにtupleにはそのようなものは存在しなかったのです。ここで、tieを使えばいいとあめふり君が教えてくれたので、その通りに実装することで要素を取り出すことができました。ただ、最初tie(pf, v, pt) = p; とすべきところをtie(pf, v, pt) としていて、segmentation faultが発生していました。

実装が終わってサンプルを試したところ、答えは合いませんでした。残念ながらここで時間切れとなってしまいました。

 

結果

2完、151位でした。去年より順位が下がってしまいました。

感想

ICPCは実装が重めなので、簡単なA, B問題だけでも過去問を解いて慣れておくべきでした。また、構文解析をある程度練習しておけばと後悔しました。

今年まではサークル[*1]のメンバーと出ていたのですが、今年で引退なので来年はどうなるか分かりません。いずれにしても、これからも競技プログラミングを楽しんでいけたらと思っています。

 

最後まで読んでいただき、ありがとうございました。

*1:正確には部らしいです

デスクトップウィンドウマネージャーのメモリ使用量が増えた時の対処法

Windowsのデスクトップウィンドウマネージャー(dwm.exe)のメモリ使用量が極端に増えた時の対処法を忘れないように記録した記事です。試す時はバックアップを取ったり不要なアプリケーションを終了した後で自己責任で行ってください。

対処法

メモリ使用量が増える問題を解決するには、dwm.exeを終了させる必要があるようです。しかし、タスクマネージャーの「プロセス」タブからタスクの終了を行うと、「Windowsが使用できなくなるかシャットダウンされ、保存されていないデータが失われる」という警告が出てきます。

そこで、デスクトップウィンドウマネージャーの項目を右クリックして「詳細の表示」を選び、「詳細」タブからdwm.exeのタスクを終了します。こうすることで、シャットダウンすることなくデスクトップウィンドウマネージャーを再起動することができます。タスクの終了を行うと少しの間画面が真っ暗になりますが、しばらく待つと元に戻ります。

ICPC国内予選参加記

この記事はTCU-CTRL場外乱闘 Advent Calendar 2020のために書きました。

 

ICPC国内予選に参加しました。その時の様子を書きます。今年の国内予選はマキアさん(茶色)、あめふりてる君(緑色)、自分(緑色)で参加しました。

開始まで

今年は流行りのあれによって集まることが難しくなったので、ルールが大幅に変更されました。

・ライブラリのコピペが可能

・使用できる計算機は1人1台まで

・ネットワークへのアクセスはできないが、SNSでチームメンバーと連絡をとるためならOK

つまり、3人がそれぞれ別の問題のコードを書くことが可能になりました。というわけで、マキアさんがA問題、あめふり君がB問題、自分がC問題を担当することになりました。

通話はDiscordを使いました。画面共有はDiscordに付いているものではなく、あめふり君が作った画面キャプチャソフトを使いました。こうすると自分の画面全体を見せながら、他の人の画面を見ることができるようになります。

github.com

題意や解法の共有にはHackMDを使いました。

開始後

本番のシステムにログインしようとしたら、1行だけエラーメッセージらしきものが書かれた画面が出てきました。2,3回試しても変わりません。3人とも同じ状況で何もできないので、マキアさんが審判に電話をかけてくれました。残念ながら、他のチームの人も電話をかけていたのか、繋がることはありませんでした。普段のコンテストなら、Twitterでつぶやいたり他の人のツイートを見ることができるのですが、今回はそれができなかったので少し不安でした。

しばらくリロードを繰り返していたら、16時40分ごろ(本来の開始時刻から10分後)に突然見られるようになりました。A問題は2020を見つけ出す問題、B問題は皆さんがスマートフォンにインストールしたかもしれない、とあるアプリに関する問題でした。

自分が担当するC問題を見たら、約数列挙と同じような方法で解けそうでした。すぐに実装を始めました。

ところが、バグがあって無限ループしているような状態になったり、8を入力すると7(正解は6)が出てきたりしてました。しばらく悩んでいたらあめふり君がB問題を通したので、コードを送って解いてもらいました。

 

あめふり君が解いている間、D問題以降を見ていました。

・D 実装が重そう。全探索しか思いつかない。

・E どこが条件を満たすのか分からない。サンプルすら手作業でも解けない。

・F グラフを書けばどういうことかはわかりそう。

マキアさんとしばらく考えていて、あめふり君から通ったという連絡が来ないので聞いてみたら、一つの入力につき5秒くらいかかっているとのことでした。n<=10^15なのにO(√n)以上の計算量*1アルゴリズムなので仕方ないですね。実行時間の制限がないという国内予選のメリットを活かすことになるとは思いませんでした。

 

最後はFを主に考えていました。あめふり君が色々とグラフを書いてくれたので、それを基に試行錯誤していました。仮説を出してその反例を見つけることをしていたら、時間がきて終わりました。

終了後

f:id:polyester-kpr:20201202230458p:plain

順位表

結果は112位でした。Cにかかる時間が短ければ予選突破だったらしいので、少し悔しかったです。並列処理するようにしたり、(今年限定ですが)3人が各自のパソコンで分担して実行して*2、時間を短縮することもできたはずなのでもったいないです。終わってから言っても仕方ないので、精進して来年頑張ります。

余談
  • 6時過ぎぐらいに突然自分のPCの電源が切れました。原因はよく分かりません。流石学科PCだなと思いました。
  • 回線速度が落ちたのか、途中から他の人の画面を見ているとDiscordにつながらなくなってきました。何か見たいものがあるときは、Slackにスクリーンショットを貼り付けてもらうことで対処しました。
  • 今年限定ですが、B問題はUnion-Findを貼り付けたほうが実装が速かったかもしれません。

 

最後まで読んでいただきありがとうございました。明後日は、ぱらなさんがボイロか動画か就活の話あたりを書いてくださるようです。

*1:厳密には分かりません

*2:競技ルールには記載されてないようですが、もしかしたらだめかもしれません