2023年2月7日
あけましておめでとうございます。
近況
気づくと前に記事を上げてから2か月弱経っていて本当に驚く。
毎日ちゃんとpythonには触るようにしていて、AtCoderとかは理工系の友達を誘って最近ではABCのコンテストが終わった後に内容について話したりしている。
AtCoderで言えば灰色の問題は殆ど解けるけど、茶色の問題は解けないくらい。灰色の問題を解くスピードがある程度早くて安定しているから、等間隔でレートは上がり続けている状況。
Kaggleで言えば、理工系の友達とタイタニックを一緒に解いた。現在開催してるなにかしらのコンテストに参加したいねって話してるけど、難易度と面白さが釣り合ってるコンペがなくてどうしようという状態。
AHCに参加した
AHCっていうのは、AtCoderのコンテスト実績を見る「Algorithm」の横にある「Heuristic」っていうあれ。
AHCは普段やってるコンペとは違って、一週間とかの長い期間で完璧な答えが無いor完璧な答えを出すのが難しい問題をみんなで解こう！ というもの。Kaggleの機械学習じゃないバージョンと捉えてもいいのかもしれない。
あと、AHCは普段のコンペと違って毎週開催されなくて結構不定期っぽい。その代わりにAHCのレーティングは順位が低くても下がらないらしく、かなり気軽に参加できる。
今回の問題を自分なりに解釈するとこんな感じ。
問題の解釈
高橋市は、N個の交差点とそれを繋ぐM個の道から道路が出来ている。
しかし、道路は全て老朽化しておりD日間の間に全ての道を丁度一回ずつ工事したい。
ただし、一日に工事できる回数はK回と決まっている。
また、それぞれの交差点を結ぶ道には道の長さ（距離）が設定されており、交差点からは必ず3本以上の道が出ている。
工事中の道は通行止めとなるため、目的地に行くには遠回りする必要があり、それだけ市民の不満が溜まってしまう。出来るだけ市民の不満が少なくなるように、各道を何日目に工事するのかの計画を立ててほしいっていうもの。
不満度のスコアを出す計算式とかもあってそういうのもちゃんと理解しようとすると本当に数時間かかった。
試しに「頂点791,辺2277」のグラフをビジュアライズすると
こんな感じになる。
正の得点を得る
初心者が一番初めにAHCでやることは正の得点を得るらしいので、辺全てに均等に工事日を指定するプログラムを作り無事WA。辺の数/日付 で余りを全部最後の日に押し付けてたので、一日の工事回数を超えちゃったらしい。全部均等に割り振るようにして無事AC。ここまでで2日とかかかってた気がする。難しいけど面白い。
山登り法を導入する
AHCには王道の解き方なるものがあって、その中でも理解しやすかったのが山登り法というもの。簡単に言うと、
- とりあえず解を適当に作ってスコアを出す
- 解を少しだけ変えてスコアを出す
- もしスコアが改善したら新しい解を採用。改善してなかったら不採用。
- 解を少しだけ変えてスコアを出す
- もしスコアが改善したら新しい解を採用。改善してなかったら不採用。
っていう感じで改変と採点を繰り返すものらしい。
この山登り法を採用したんだけど、初心者には2つの壁があった。
- スコアの計算方法が難しい
- そもそもスコア計算が重すぎて山登りできない
スコア計算には全点対最短経路問題っていう全て頂点と全ての頂点の最短距離を出して合計するっていう過程を経なきゃいけない。まずこの結論に至るまでが初心者には難しい。
色々調べるとワーシャルフロイド法っていうのがあってそれを使うことで頂点の数の3乗、つまりO(N^3)で解けるらしいことが分かる。でも今回はN<=1000だからワーシャルフロイド法を使うと計算時間が間に合わない。実際にスコア計算を実装してみたけど頂点数989で19秒かかった。今回は制限時間が6秒なので余裕で間に合わない。
違う方法を模索する
とりあえず、ここから初心者の私が出来ることとしては
1. 計算スピードを速くする
2. 素早く動く独自のスコア関数を作る
3. そもそも山登り法をやめる
という感じ。
計算スピードを速くするにはpypy3を使う必要がある。でもpypy3だとnumpyが対応してないから実装難易度がめっちゃ上がる。だから今回はぺけ。
素早く動く独自のスコア関数を作るっていう考え方は、上位の方の解法を見ると間違ってはなかったみたい。しかし、自分の実装力のなさとpythonということからそもそも山登り法が厳しい。あと、今回のコンペはグラフの連結性が無いと圧倒的にスコアが悪くなるのでそもそも連結性を確実に作るところからだろというところで、山登り法はしないことに。
結論として、私は
1. もし辺数/日数を満たしてたらその日の指定は終わり
2. 一番工事していない辺を持ってる頂点を見つける
3. その頂点が今日、辺数を2で割った以上の工事をしてるかの判定。ダメなら次
4. その頂点と繋がってる頂点の中で、今日もっとも工事していない頂点を選ぶ
5. その頂点が今日、辺数を2で割った以上の工事をしてるかの判定。ダメなら次
6. 大丈夫なら、その辺を工事指定
7. これを繰り返し、全ての頂点を見てまだ辺数/日数を満たしてなかったら、一番工事してない辺を持ってる頂点を選んで、その頂点が持ってる辺と繋がってる頂点の中で、最も工事していない辺を持ってる頂点を選ぶのを繰り返す。
という実装をした。こんな規模のプログラムを一から書いたことが無かったから本当に苦戦した。
最終結果
最終結果はまあまあだった。
とりあえず2000問のテストケースでACが取れて、やれることはやれたから良かったと思う。
初めてのAHCを通して
このAHCを通して
- 大きなプログラムを作ることの難しさ
- 上位の方の解法を見ると意外と解法が単純なこと
- 粘り強さである程度は戦えること
- AHCが面白い
ことがわかった。
とにかく長期コンペが面白かった。はやくKaggleにも参加したいところ。
