ブログ

ICPC2024 国内予選参加記

2024年7月5日

チーム

メンバーはshogo314（自分）、besukohu、littlegirl112です。出場時のAtCoderのレートはそれぞれ1848, 1902, 1805でした。今年も阪大の3軍です。阪大ではざっくりレート順に決まるチームが多いです。

チーム名

kotamanegi_marukajiriになりました。

JAG

いくつかのチームで集まって参加しました。結果は27位でした。力を出せなかったわけではありませんが、一昨年の基準では通過できない基準。なかなか厳しいです。

当日

早めに行って設営を手伝ったりしました。

本番

A

考察: littlegirl112 実装: shogo314 言われたとおりに実装しました。

AC 2:25

B

考察: littlegirl112 実装: shogo314 言われたとおりに実装しました。

AC 6:34

C

考察: besukohu 実装: shogo314 言われたとおりにO(1)を書いたけど、嘘でした。何回か書き直して、駄目だったので、littlegirl112に見てもらいながら前計算で中心からBFSするのを書きました。バグらせて大変でした。

AC 34:04

D

考察: littlegirl112 実装: shogo314 言われたとおりに実装しました。バグらせながらなんとかACしました。

AC 1:08:22

E

考察: littlegirl112, besukohu 実装: littlegirl112 嘘を書いたり、嘘じゃなかったかもだったり。僕はほとんど関わっていません。サンプルは通ったけど絶対WAですと言われたので、とりあえず出しましょうとだけ言いました。

ACならず

F

考察: besukohu 実装: shogo314 頑張りました。頑張ったのですが実装しきれませんでした。少し理解の浅い部分もありました。

ACならず

感想

調子がかなり良ければ6完の可能性が見えてくるけど、正直難しかったです。最後の方はlittlegirl112とパソコンの取り合いをしていましたが、6完する必要があったので、そのムーブは間違っていなかったと思っています。双子が11位な時点で魔境コンテストだったと思います。

来年は僕が院試に落ちていなければ1軍か2軍で出場しているはずです。がんばります。

AtCoder Heuristic Contest 030 参加記

2024年2月19日

AtCoder Heuristic Contest 030に参加し、275位でした。

FAチャレンジ

なるべく早くサンプルを提出するチャレンジです。（無意味）負けました。問題を開くのが少なく見積もって3秒は遅れていたのが敗因です。

やったこと

雛型を作る

サンプルと同じことをするコードを今後の修正を加味しながらきれいに書き直します。この中でコストの計算方法の理解が正しいかなどを確認していきます。

https://atcoder.jp/contests/ahc030/submissions/50121556
絶対スコア：12696000000

$\sum_{t=1}^{50} {N}^2 = 12696$
であることがわかりますね。

ランダムにボーリングする

方針が立たないので適当にq1のクエリを繰り返しながら明らかに確定したタイミングで答えを決める形にします。答えが確定したかを確認するのを O(N² d M) かけるとして全部で O(N⁴ d M) 。間に合います。答えが確定したかは、0の場所と被らずに油田を置けるかの判定を全ての油田について行います。（かなり簡易な判定）

https://atcoder.jp/contests/ahc030/submissions/50122609
絶対スコア：11981000000

微差ですね。

判定を賢くする

油田の数が多くなるとほとんど判定が効いていないようです。特定のマスについて、そこに被るように置く方法が1通りであるかの判定を追加します。

https://atcoder.jp/contests/ahc030/submissions/50123560
絶対スコア：10678000000

多くのケースにおいて全て埋めきる前に確定させられるようになりました。実行時間が1.2sだったので、そろそろ気にする必要がありそうです。

順位表を見てみる

(2024-02-10T12:00:00+09:00)

2段になっておりサンプルの上に1段あります。既にここは超えていますが、見逃している自明解があるようなので、これを探ってみます。

発見しました。サンプルと同じように進めて、見つかっているものの総和を比べると、ここになるようです。

https://atcoder.jp/contests/ahc030/submissions/50127581
絶対スコア：11411000000

組み合わせる

稀に全てのセルを探索しているので、組み合わせると改善するはず。

https://atcoder.jp/contests/ahc030/submissions/50127994
絶対スコア：10220000000

一次元化する

実行時間を改善するためグリッドを一次元化したりいろいろ工夫します。判定をいろいろ賢くして、まだ調べていない部分も確定する部分をちゃんと記録して、調べるときはそれを除くようにします。かなり掘る回数を削減できました。

この過程で500回に1回くらいの確率でWAになるバグを見つけました。再現性がないとデバッグで困るのでrandom関数は決定的なものにしておいた方がいい気がします。

https://atcoder.jp/contests/ahc030/submissions/50255771
絶対スコア：5415000000

情報量を使う?

掘る場所を改善できる気がします。掘る候補についてそこを掘ったときに得られる情報量を考えて、エントロピーを計算すれば、いい場所を掘るようになりそうです。ただ、実装が面倒だし、TLEになる気もします。

同じ形のときがある

同じ形の油田が２つあるとそのどちらなのかが特定できません。このようなケースがだいたい7.5%ほどあります。２つあるなら２択まで絞れた時点でどちらかに決めるような処理を入れました。

候補が複数あるものを適当に決めて矛盾があれば候補からはずす

やりすぎるとすぐTLEするので候補が多いものに絞った上で、残り時間が少ないと判定を飛ばすようにした。

掘る場所の選び方を工夫する

確定していないものから一様ランダムに選んでいたが、確定している場所の近くは選ばれにくくした。

https://atcoder.jp/contests/ahc030/submissions/50275514
絶対スコア：4957000000

感想

結局占いは使えませんでした…

AtCoder Heuristic Contest 027 参加記

2023年12月10日

AtCoder Heuristic Contest 027に参加し、273位でした。

時系列

とりあえず

サンプルのdfsと同じものを実装する。スコアの計算を実装する。

以下、特に明記しない場合はシードが1~100のときの平均
Average = 21991473.54

`RDLU`の順番を変える

24通りを試し、最良を選択する

Average = 19521742.3

もっとランダム

各マスでランダムに優先順位を決める。 20000回程シミュレーションできた。

Average = 21251525.91

あんまりよくなっていない

現在の解からランダムに派生

ちょっと寄り道したり、省略したりしてみて改善するなら採用を繰り返す。変化が小さいのですぐに局所解になったり、広い盤面だと計算に時間がかかって十分に派生させられないので、いろいろ残念。大きい変化を頑張って採用できるようにする案もあるが、次の手に。

Average = 18365379.48

15000000くらいなら提出する気になるかな…

DFSから変更

DFSは実装が簡単だが、無駄な移動が多い。なるべく少ない移動ですべてのマスを少なくとも一回通る方法について考える。これは巡回セールスマン問題（TSP）なので、条件つきでの近似解法について調べる。三角不等式が成り立つときの問題をMetric TSPというらしい。この条件下ではDFSのルートから既に行ったことのある場所をとばしてルートを決定していくというのがあるらしい。クリストフィードのアルゴリズムはよくわからなかった。O(n³)らしいので今回の条件だと使えない？ RDLUの順に評価するDFSを変形する形で実装してみる。

Average = 16936320.88

思ったより改善した

24通り試す

Average = 16144839.97

まだTSPが不完全…。グリッド上のTSP解法は確実に論文があるはずだが、検索能力がないので見つけられない。 Bing AIにきいてみるとFutureの記事を提案されるがこれは一般的なグラフの解法。食い下がると、次数5以下の場合の多項式時間アルゴリズムを出してくれる。そんなものが存在するのか…。英語論文を読む気にならない

2-optを使ってみる

Average = 15892483.36

とりあえずTSPは十分と思って、ここから適当に遷移させる。

適当に山登り

Average = 14025677.55

結構改善した

遷移先をいい感じに評価

汚れが大きいところを通るものを選ぶようにする

Average = 13801249.45

局所最適解に陥ることが多い

探索幅を広げる

TSPの後、改善する手順を繰り返す。改善する段階は重みをつけているので一意だが、TSP解がランダムなのでいろいろな解がえられる。

Average = 13567886.96

TSPがいまいち

そもそもTSPが最適でないし、多様性もない

TSPの最善でないものもいろいろ採用してみる

Average = 13178283.81

遷移先を増やす

Average = 13213827.0

収束の速いケースでは改善したが全体としては悪化

汚れやすい場所を探す

入力生成方法を読むと、1~20の汚れやすいゾーンがある。汚れやすい場所でないところは10以下で汚れやすい場所は最大1000なので、かなり差がある。実際どのくらいかわからないが、汚れやすい場所をそうでない場所の10倍以上通るくらいがよさそう？

10より大きい場所だけでTSPを解けばいいのでは？

間に合わず悲しい

感想

結構いいアイディアが思いついたと思ったけど、実装しきれず… 参加賞が200人対象なので頑張ったが、さすがに届いてなさそう

AtCoder Heuristic Contest 025 参加記

2023年10月22日

AtCoder Heuristic Contest 025に参加し、185位でした。

やったこと（時系列）

適当に原型を作る

d[i] = i % D

とする。 https://atcoder.jp/contests/ahc025/submissions/46619584

AHCの順位表は作戦立てに有効な情報が多いので視覚的に把握できると便利です
例えば今日開催されたAHC024では現時点(10/13, 12:54)では10位付近に強い貪欲があるのがわかります。 pic.twitter.com/ndFWFVUZff

— pitP (@HISHO_NO_KISEKI) 2023年10月14日

上の並んでいる部分。みんな考えることは同じやね。

考える

原型を改良する方向で考える。Dが大きいときは、ソートして最小と最大を近づければそれっぽくなりそう。

2 \le D \le 25,

8D \le Q \le 1600D,

Qが最小のときでもギリギリ、ソート出来そう。

ソートの比較

ソートの候補は

マージソート
クイックソート
ヒープソート
二分挿入ソート

要素数25（一致する数字はなし）で、それぞれ10⁶回実行したときの比較回数。

二分挿入ソートは挿入ソートの挿入位置を二分探索で求めるもの。通常、挿入コストが重いので使われないが、比較コストはこの中で最も低いようだ。

最悪でも要素数の4倍未満なので必ずソート出来る。

N = 25
t = 0
for i in range(1, N):
    t += i.bit_length()
print(t) # 94

最悪の比較回数は上のコードで求まる。

大小関係の保存

Qが小さいのでちゃんと最適な質問の仕方をしたい。

x \le y \land y \le z \to x \le z

\operatorname{Weight} \{ a \} \le \operatorname{Weight} \{ b \} \leftrightarrow \operatorname{Weight} \{ a,c \} \le \operatorname{Weight} \{ b,c \}

みたいな性質は使いたい。

ソートしたあと上と下を近づける

大小関係についてきちんと保存して、上記の性質を利用して無駄なクエリを排除するコードを書いてみたものの、うまく動かなかったので、実装コストの軽い方針で進める。はじめに二分挿入ソートでソートしたあと、要素が2つ以上のなるべく大きいグループからランダムに1つ選び、最も小さいグループに移動させる。これで改善する場合は採用し、新しいグループの挿入位置を二分探索で調べる。

提出 https://atcoder.jp/contests/ahc025/submissions/46724103

結構いいスコア

繰り返す

上の方法では最も大きいグループのどれを移動させても改善しない状態に収束するので、収束が確認できたら初期解をランダムに作成し同じ操作をする。新しく作った解の最大最小のグループを元の解のものと比べて、どちらも改善しているなら採用する

提出 Submission #46742799 - AtCoder Heuristic Contest 025

収束するまでの操作は回しきれないものから30回程のものまである

D=2のときについて考えてみる

シード0~999の1000ケースについて--D=2で実験してみたところスコアの平均は31858.2だった。

解の探索範囲を広げるため、大きい方から小さい方に動かして悪化する場合もそれを採用することにした。スコアの平均は57360.4だった。悪化する場合は選択せずに選び直すという処理はよかったようだ。

単に2つを比べて近づけていくのはあんまり賢くない気がするが特によい方法が思いつかない。

問題の都合上、少し改善が難しい。力を出し切った感覚はないが、十分なスコアは出ていそうだし、疲れたのでここで終了。結局3回しか提出しなかった。

パソコンを買いました。

2023年9月2日

競技プログラミング用にパソコンを買ったので、環境構築を全部書きます。

目標はWSL+VSCodeでC++を実行できるようにして、atcoder-cliで提出出来るようにすることです。

パソコン

Lenovo IdeaPad Slim 170 14型 (AMD) 49,830円
プロセッサー: AMD Ryzen™ 5 7520U (2.80 GHz 最大 4.30 GHz)
初期導入OS: Windows 11 Home 64bit
グラフィックカード: AMD Radeon™ 610M グラフィックス
メモリー: 8 GB LPDDR5-5500MHz (オンボード)
ストレージ1: 512 GB SSD, M.2 PCIe-NVMe Gen4 QLC
ディスプレイ: 14” FHD液晶 (1920 x 1080)
重さ: 1.4kg

パソコンに詳しくないので、5万円以下でなるべく性能がいいらしいものを買いました。（参考）
普段使いは生協で買ったLIFEBOOKなので、重さに驚きました。

パソコンのセットアップ

地域を設定したりします。

デバイスの名前はLAPTOP-KP-shogoにしました（後から変更できます）。

Microsoftアカウントは既に持っていますが、新規にメールアドレスを取得してみます。名前を姓名別に入力させるフォーム…。

サインインしてPINを設定出来たらあとは全部スキップして完了。

WSLをインストール

PowerShellを管理者として実行

wsl --install

指示通り再起動する

Restart-Computer

これで再起動できる（手動でいい）。再起動すると、Ubuntuのターミナルが開かれた状態でusernameを入力するよう指示があるので入力する。次にパスワードを入力するよう指示があるので入力する（入力時、画面に文字が出ない）。もう一回パスワードを入力すると設定完了。パスワードは簡単にしておいた方がいい。

VS Codeをインストール

Microsoft Storeにもありますが、公式ページからインストーラーをダウンロードしている人が多いのでそっちにします。

https://code.visualstudio.com/download

にアクセスして、WindowsのUser Installerのx64をクリック。 VSCodeUserSetup-x64-1.81.1.exeがダウンロードされるので実行。

使用許諾契約書が出るので同意

インストール先を指定できますが、デフォルトの C:\Users\username\AppData\Local\Programs\Microsoft VS Codeにしておきます。

追加タスクを選択できます。せっかくなので全部チェックしておきます。

インストールを押して完了です。

VS Codeに拡張機能を追加

拡張機能の

WSL

をインストール

VSCodeとWSLの連携をとる?

左下の><みたいなのを押して、Connect to WSLを選択

左下が><WSL-Ubuntuになる

これでVSCodeからWSLのファイルを触れるようになる

ターミナルを開いて

shogo314@LAPTOP-KP-shogo:~$

のように表示されている

コンパイラをインストール

ターミナルで

sudo apt-get update
sudo apt install build-essential -y
sudo apt install gdb -y

を実行

g++ --version

で正しく表示されたらOK

VS Codeに拡張機能を追加2

C/C++

を入れる

試してみる

shogo314@LAPTOP-KP-shogo:~$ mkdir AtCoder/ABC/abc211/a -p
shogo314@LAPTOP-KP-shogo:~$ cd AtCoder/ABC/abc211/a
shogo314@LAPTOP-KP-shogo:~/AtCoder/ABC/abc211/a$

VSCodeで/AtCoder/ABC/abc211/を開いてa/にmain.cppを作る

#include <iostream>
int main()
{
    int A,B;
    std::cin >> A >> B;
    std::cout << (float)(A - B) / 3 + B << std::endl;
}

拡張機能が働いていることがわかる。ファイルを保存して下を実行

$ g++ a/main.cpp
$ ./a.out
300 50
133.333

g++がちゃんと使えている

atcoder-cliをインストール

Python3をインストール

sudo apt install python3

既にインストールされてる?

$ python3 --version
Python 3.10.12

Pythonをインストールするとpipもついてくるはずだけど、なかったのでインストール。

pip3をインストール

sudo apt install python3-pip -y

Node.jsをインストール

curlは既にインストールされている node.jsはバージョンが結構複雑らしい

Node Version Managerをインストール

https://github.com/nvm-sh/nvm

curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.39.5/install.sh | bash

Node.jsをインストール

ターミナルを開き直す

nvm install node
npm install -g npm

online-judge-toolsをインストール

pip3 install online-judge-tools

pip listだと表示されるがojが認識されない。ターミナルを開き直せば使えた。

atcoder-cliをインストール

npm install -g atcoder-cli

試してみる

oj login https://atcoder.jp
acc login

ログイン

$ cd ~/AtCoder/ABC
$ acc new abc210

abc210/aの中にmain.cppを作る

#include <iostream>
int main()
{
    int N, A, X, Y;
    std::cin >> N >> A >> X >> Y;
    std::cout << std::min(N, A) * X + std::max(0, N - A) * Y << std::endl;
}

oj t

が実行できないテストケースのディレクトリがtestsに作られたのにtestを参照している。とりあえずディレクトリ名を変更して実行。正常に動くことが確認できる。

acc submit main.cpp

提出成功。テストケースのディレクトリ名を変えたせいでテストしてないけど大丈夫?みたいなのが出た。

atcoder-cliの設定

$ acc config default-test-dirname-format test
$ acc config default-task-choice all

テストケースのディレクトリ名を変更する。コンテストを選んだときすべての問題のディレクトリが作成されるようにする。

$ acc config-dir

で設定用のディレクトリがわかるので、それを開く。 ~/.config/atcoder-cli-nodejs ここにcppディレクトリを作りtemplate.jsonを置く

{
    "task":{
        "program": ["main.cpp"],
        "submit": "main.cpp"
    }
}

main.cppも作る。テンプレートを適当に作る。

acc config default-template cpp

これで設定したテンプレートが使用できる。

ライブラリを使えるようにする

仮にac-libraryを使ってみる

$ cd ~
$ mkdir library
$ cd library
$ git clone https://github.com/atcoder/ac-library.git

$ cd ~/AtCoder/ABC
$ acc new abc206

abc206を開く d/main.cppを

#include <bits/stdc++.h>
#include "atcoder/dsu"

int main()
{
    using namespace std;
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i; i < N; i++)
        cin >> A[i];
    atcoder::dsu uf(200001);
    int ans = 0;
    for (int i = 0; i < N / 2; i++)
    {
        if (!uf.same(A[i], A[N - i - 1]))
        {
            uf.merge(A[i], A[N - i - 1]);
            ans++;
        }
    }
    cout << ans << endl;
}

にする

$ cd d
$ g++ main.cpp -I ~/library/ac-library
$ oj t

ac-libraryをコンパイル出来ている。

verification-helperをインストール

これだとAtCoderにしか提出出来ないので、インクルードしているものを自動で展開できるようにする。

$ pip3 install online-judge-verify-helper

これでインストールできる。念のためターミナルを開き直して

$ oj-bundle main.cpp -I ~/library/ac-library > a.cpp

展開したものが標準出力に出るので> a.cppを付けて出力先をファイルにする。展開したいものは<atcoder/dsu>のように<>で囲んでいると駄目で、""で囲む必要がある。

CPLUS_INCLUDE_PATHを設定

これまでだとVSCodeの拡張機能が”atcoder/dsu”を認識できておらずエラーが出ていた。ホームディレクトリに.bash_profileを作り

export CPLUS_INCLUDE_PATH=~/library/ac-library

と書く。2つ以上設定したい場合は:で区切るらしい。‘/home’から書いた方が確実かも。ここのファイルはbashを起動したときに実行されるのでターミナルを開き直す。

echo $CPLUS_INCLUDE_PATH

で表示されてたら成功。

これでエラーが出なくなった。またg++を実行するときに-I ~/library/ac-libraryを書かずとも動くようになった。しかし、oj-bundleは書く必要がある。

設定を調整

if(1)
{
}

より

if(1){
}

が好きなのでフォーマッタの設定を変える。設定を開く。Ctrl+,で開ける。 C_Cpp: Clang_format_fallback StyleがデフォルトだとVisual StudioになっているのでGoogleに変える。

トラブル発生

VSCodeを開き直すと急にojやoj-bundleが使えなくなった。acc check-ojは使えるし、動いているのでPATHの問題っぽい。 home/shogo314/.local/bin/oj --versionが動くのでこれを呼べるようにすればよい。 ~/.bash_profileに

export PATH="~/.local/bin:$PATH"

を追加する。

おわり

結構大変だった。

ライブラリを作る（執筆中）に続く…

チーム

チーム名

JAG

当日

本番

A

B

C

D

E

F

感想

FAチャレンジ

やったこと

雛型を作る

ランダムにボーリングする

判定を賢くする

順位表を見てみる

組み合わせる

一次元化する

情報量を使う?

同じ形のときがある

候補が複数あるものを適当に決めて矛盾があれば候補からはずす

掘る場所の選び方を工夫する

感想

時系列

とりあえず

RDLUの順番を変える

もっとランダム

現在の解からランダムに派生

DFSから変更

24通り試す

2-optを使ってみる

適当に山登り

遷移先をいい感じに評価

探索幅を広げる

TSPがいまいち

遷移先を増やす

汚れやすい場所を探す

感想

やったこと（時系列）

適当に原型を作る

考える

ソートの比較

大小関係の保存

ソートしたあと上と下を近づける

繰り返す

D=2のときについて考えてみる

パソコン

パソコンのセットアップ

WSLをインストール

VS Codeをインストール

VS Codeに拡張機能を追加

VSCodeとWSLの連携をとる?

コンパイラをインストール

VS Codeに拡張機能を追加2

試してみる

atcoder-cliをインストール

Python3をインストール

pip3をインストール

Node.jsをインストール

Node Version Managerをインストール

Node.jsをインストール

online-judge-toolsをインストール

atcoder-cliをインストール

試してみる

atcoder-cliの設定

ライブラリを使えるようにする

verification-helperをインストール

CPLUS_INCLUDE_PATHを設定

設定を調整

トラブル発生

おわり

`RDLU`の順番を変える