US_cube’s blog

AHC016(HTTF予選) 参加記

目次

コンテストの結果
解法
得点別の解法
感想

コンテストの結果

暫定結果は相対スコアが9,695,567,980点(絶対スコアは693515946点)で225位でした

システスでの絶対スコアが27,135,329,698点(絶対スコアは422181214166点)で217位でした

解法

i番目のグラフは頂点0~iまでそれぞれ0~n-1まですべて辺を張ったグラフを作成
matrixで見た時のL字の部分に含まれている0の数と、L時以外の領域に含まれている1の数がなるべく少なくなるようなグラフを全探索

送られてきたグラフを次数の大きい頂点順にソートして山登り法みたいな方法で2頂点をスワップしながらスコアスコアがなるべく少なくなるところを適当に探す
その中で一番与えられたグラフと近かったものを採用する
$\varepsilon$ がかなり小さい(0.00~0.05くらいの値)時はN=4~6にして同型ではないグラフをM個作って理論値を狙いにいく

というような解法で解きました

Visualizer ↓

seed=0(M=10, $\varepsilon$ =0.00)

\varepsilon — seed=0(M=10, $\varepsilon$ =0.00)

seed=3(M=48, $\varepsilon$ =0.34)

\varepsilon — seed=3(M=48, $\varepsilon$ =0.34)

seed=16(M=32, $\varepsilon$ =0.40)

\varepsilon — seed=16(M=32, $\varepsilon$ =0.40)

得点別の解法

ここからコンテスト中の考察を得点順に分けて書いてあります(メモ代わりなのでかなり適当です)

54097055点

頂点を二つランダムに選んで辺を張るという操作でグラフの作成をしてみました

Nは20固定で、辺の数は各グラフについて0~N(N-1)/2までの等差数列になるように設定してみました

提出コード: https://atcoder.jp/contests/ahc016/submissions/36384936

174271158点

Nはmaxの100に固定

それぞれの頂点のペアに対して辺を張る/取り除くということを確率的に行うのでi番目のグラフ( $G_i$ )での辺の数を $e$ とすると、そのグラフの辺の数の期待値は $e$ から $\varepsilon e$ だけ減って、 $\varepsilon (N(N-1)/2-e)$ だけ増えた値なので、その期待値とノイズ入りのグラフにある辺の本数が一番近いグラフを探すようにしてみる

そこから少し頑張ってみて176408919点までは取れた

Visualizer(174271158点): seed=3

提出コード: https://atcoder.jp/contests/ahc016/submissions/36395001

そろそろ辺の数という情報だけじゃ厳しそうなので、グラフを利用した解法を考えていくことに

333075586点グラフの数を数えてみる

頂点の数がN個のグラフの種類数(頂点を入れ替えて同じになるものはすべて同じ種類とする)を数えるプログラムを適当に作ってみた

少しだけしか探せなかったけどこんな感じになりました(これ以上は時間がかかりすぎた)

(N, 種類数) = (1, 1), (2, 2), (3, 4), (4, 11), (5, 34), (6, 156)

割と少ない頂点数でもグラフの種類がたくさんあることがわかる(N>=6の時点で100超える)

とりあえず、 $\varepsilon = 0.00$ の時だけに特化したプログラムを書いてみる

上から2~3桁目のスコアしか変わらないと思ったら2倍くらい伸びてびっくりした(ただし相対スコアは伸びず...)

提出コード: https://atcoder.jp/contests/ahc016/submissions/36473676

439238657点

必ずしも $\varepsilon = 0.00$ でないといけないわけではないので辺の数も考慮して0.02~0.08くらいまで許容してみた

思ったより上がる

提出コード: https://atcoder.jp/contests/ahc016/submissions/36474305

535391293点

このあたりから得点を上げるのにかなり時間がかかった

i番目のグラフは頂点0~iまでそれぞれ0~n-1まですべて辺を張ったグラフにしてみる

受け取ったグラフは次数順でソートして次数の差が一番大きいところを探してそのindexを出力する。という感じでやってみた

(このあたりでVisualizerにグラフをmatrixで表示させることができるのを知る)

提出コード: https://atcoder.jp/contests/ahc016/submissions/36522240

578834111点

一部のテストケースでランダムに辺を作って解いていたのでそれをやめて基本的に上の解法で解くようにしてみる

スコアはあんまり上がってないけど、順位は思ったより上がった

今回訂正したのが $\varepsilon$ が高いテストケースで、そのケースのスコアを見ると相対的にかなり高くなってたかもしれない -> 正答率をとりあえず上げることを目標にする

Visualizer(578834111点): seed=3

提出コード: https://atcoder.jp/contests/ahc016/submissions/36530599

670527986点

$\varepsilon$ の値によって右下に余らせる頂点の数を変えるように改善

提出コード: https://atcoder.jp/contests/ahc016/submissions/36546380

693515946点(最終提出)

2頂点をランダムに入れ替えて作成したグラフと近くなるかを適当に試した(が、あまり効果がなかった)

提出コード: https://atcoder.jp/contests/ahc016/submissions/36583530

感想

今回のAHCは、実装がどうこうというよりも、考察ができないから実装すらできないみたいな感じでコンテストが終わってしまった...

ヒューリスティックも黄色目指して頑張ります。