この広告は、90日以上更新していないブログに表示しています。

九州大学新入生の皆さん,合格おめでとうございます!
私たち九州大学 競技プログラミング部(旧称:ICPCチャレンジ部)はAtcoder・ICPCを始めとした競技プログラミングコンテストに取り組む大学公認サークルです!!
プログラミング力,アルゴリズム力の向上を目的に週1~2回程度参加しており,他サークルとの兼部も十分に可能です!

九州大学 競技プログラミング部は プログラミングコンテスト に取り組んでいる大学公認サークルです。この記事では弊サークルについて簡単に紹介していきたいと思います。

はじめに

はじめまして。autumn09といいます。 僕は1年半前くらいに競技プログラミングを初め、いつもはABC(Atcoder Beginer Contest)に参加しています。

今回はAHC(Atcoder Heuristic Contest)に初めて参加しました。 今更ながらですが*1、AHCの感想・自分の解法を紹介したいと思います。 最初の方はAHCの説明と僕の所感なので、解法だけ読みたい人は 問題概略まで読み飛ばしてください。

AHCとは

僕たちがいつも参加しているICPCやABCは、与えられた問題に対して最適解を求めるものです。 最適解を求めるプログラムでなければ、それがどれほど最適解に近くても、不正解(WA)とされてしまいます。

一方で、今回僕が参加したAHCは、「最適解を出すのが難しい問題に対し、出来るだけ良い解を作成するコンテスト」です(Atcoder公式HPより)。 まあ、語弊を恐れずに言うと、ミニゲームのようなものに対して、プログラムを組んで良いスコアを目指す、といったところでしょうか。

具体的にどのような問題を解くか、というところは毎回変わります。 今回のお題は、「たこやきをできるだけ少ない手で別の場所に移す」というものでした(詳しくは問題概略)。

AHCの楽しさ・魅力

初めて参加してみましたが、とても楽しかったです!! 今回感じた、AHCの楽しさ・魅力を語っていこうと思います。

楽しさその1:ビジュアライザを見る楽しみ

AHCでは、自分の組んだプログラムの出力を可視化できるもの(ビジュアライザ)が公式から与えられます。

これは今回のコンテストの、僕が途中提出したプログラムのビジュアライザです。

楽しさその2:自由な発想で、スコアを改善させていく楽しみ

普通の競プロでは、問題を解くことのできるプログラムの種類(解法の種類)はさほど多くありません。 そして、多くの問題は典型手法に落とし込んで解決するので、(一部の天才以外は)知らないと解けない、ということもあります。

一方でAHCは自由度が高く、さまざまな発想・手法を幅広く試すことができます。 そして、AHCの典型手法というのもあるようですが、それを知らなければまったく手も足も出ない、ということはありません。 実際、僕はAHCの典型手法(山登り法、ビームサーチなど)について知らずに参加しましたが*2、アイデアと考察で善戦することができました。

当然、選んだ手法によって良いスコアだったり悪いスコアだったりします。 そのため、「どうしてこの解法だとスコアが良い/悪いのか」ということを考察する必要があります。 多くの人はビジュアライザを見ながら考えているようです。 これがまた楽しくて、休日が溶けていきました。

問題概略

• ×ばつNの盤面があり、その中にM個のたこやきが置いてある。
• そのたこやきを、ロボットアームを使って目的のマスに置きたい。
• ロボットアームをうまく設計してうまく操作することで、できるだけ少ない操作回数でたこやきを移動させよ

上のビジュアライザでいうと、丸いのがたこやきで、赤くなっているマスがたこやきを置きたい目的のマスです。 そして、動き回っているのがロボットです。 ロボットは木構造をなしていて、その葉に当たる部分でたこやきを掴むことができます。 葉になっていない部分では掴むことができません。 以下、ロボットの葉に当たる部分を「手」と呼ぶことにします。

結果

約1000人中、154位(青performance)で入緑しました!!

[フレーム]atcoder.jp

解法の紹介(時系列順)

最初から完璧なプログラムを書ける人はおらず、多くの人は改善を重ねながら良いプログラムを作っていると思います。 僕もその1人で、改良・機能の追加・仕様変更を繰り返して徐々に順位を上げていきました。 時系列に沿って、僕がどういうプログラムを作り、それをどのように改良していったのか説明します。

今回のAHCはスコアが低いほど評価が高い(たこやきを少ない操作で移すことが目的であるため)です。僕のスコアの推移は下の表のようになります。

提出その1(1806429点)

最初は何から手をつけていいか全くわからなかったので、1回目の提出はとりあえず動くプログラムを作ろうというモチベーションで書きました。

まず、今回のAHCでポイントとなるのは、

1. ロボットの設計
2. 根(ロボットの手足が生えている中心の部分)の動きをどうするか
3. ロボットの関節の曲げ方

だと考えました。

1つ目については、どんなロボットが強いかという見当がつかなかったので、この段階ではテキトーに設計しています。

2つ目については、盤面を網羅できるようにジグザグに動くようにしました。

3つ目については、ロボットの関節の曲げ方を全探索して、最もたこやきを掴んだり離したりできるような曲げ方を実際に行う、という動かし方にしました。 単純な行動指針でしたが、実はこれはかなり有効でした。 最終提出においても、基本的にはこの方針のもと動いています。

ロボットの関節は、頂点数Vに対してV-1個あります。 それぞれの関節の曲げ方は、右に曲げる、左に曲げる、そのまま、の3種類です。 したがって、愚直に全ての曲げ方を試すと計算量はO(3^V)になります。 しかし、Vは最大15あるので、この実装では計算量が大きすぎて3秒という実行時間に間に合わせることができません。

ここで、ある頂点から生えている2つの頂点は互いに独立に動かすことができます。 この頂点の部分木を考えると、一方の部分木の動かし方がどうであれ、もう一方の部分木はそれに影響されません。 このことから、全探索は、根から生えているそれぞれの部分木ごとに行えばいいことがわかります*3。 したがって、計算量は、根から生えている頂点の部分木の頂点数の最大値を V_{max} として、 O(3^{V_{max}}) となります。 よって、 V_{max}を大きくしすぎなければ、高速に動きます。

ちなみに、ロボットが回転しているのは、掴む・離すたこやきの個数が同じような関節の曲げ方が複数ある場合、右回転を優先して取るようになっているからです。

提出その2(65926点)

1回目の提出のビジュアライザを見ると、根の動きにかなり無駄があることがわかります。 根が動いた先にない場合でもジグザグを続けてしまっています。 これを改善すべく、よりよい根の動かし方を模索したのが提出その2です。

根がどう動いてくれれば良いかというと、たこやきを持っていない手とたこやきのある位置が、たこやきを持っている手とたこやきを置く位置が、近くになってくれれば良いです。 なので、根に、次の式で表される力が働くとして、その力の方向に根が動くようにしました。

ただし,

です。

要は、たこやきを持っている手とたこやきを置く位置が、たこやきを持っていない手とたこやきが、近づくように根に力をかけているということです。 もう少し厳密に力(やモーメント)を計算すべきところですが、実装が複雑になるのと、計算量の観点から、このような形にしました。

ですが、案外うまく動き、スコアがだいたい30分の1くらいになりました。

提出その3(12221点)

この提出では、提出その1やその2で後回しにしていた、ロボットの設計を見直しました。 とはいっても自分で設計したわけではなく、ロボットを何個もランダムに生成して、その中で性能が良いものを抽出しました。そして、そのロボットをソースコードに埋め込んで提出しました。

詳しくは提出その4で説明しますが、提出その2くらいから、ターン数がだいぶ運によって左右されています。 なので、実行時間のある限り、ロボットの動き方を複数作り、その中でもっともターン数の短いものをprintするようにしました。

スコアは数倍下がり、提出時点では青パフォ(100位から200位)でした。

提出その4(10761点)

提出その3のビジュアライザの最後あたりを見ると、たこやきを掴んだり離したりするのにだいぶ時間がかかってしまっています。 また、テストケースによっては、根にかかる力がつりあってしまって根が動けず、永遠に終わらないようなものありました。

このように、最後あたりになってくると、力のかかり方が微妙になって性能が落ちてしまいます。 そこで、提出その4では、終盤の根・関節の動かし方を、確実にたこやきが掴める・置けるようなものに変更しました。 この動かし方のモード切替は、置かれていないたこやきの個数がある閾値m_{th}以下になったときに行われるようにしています。

ビジュアライザを見ると、ある時点からロボットの動きが明らかに変わっているのがわかると思います。

提出その5(最終提出, 8216点)

提出その5では、仕様を追加することはほぼありません*4でした。 そのかわり、パラメータを調節しました。 調整したパラメータは以下の通りです。

• 提出その4の、ロボットの動かし方を変えるしきい値m_{th}
• 何回も動き方を作るが、その時間配分(打ち切る時間t_{limit})

注意が必要なのは、最適なパラメータの値はNとVによって多少変わってしまうということです。 なので、最適なパラメータのNとVに関する依存性を調査して、パラメータをNとVの式で表すことを目指しました。

1つ目に関しては、もっともターン数が小さくなるm_{th}が、次のような式で表されることを見つけました。

驚くほどきれいな形になったので、発見したときはとても嬉しかったです。

2つ目に関して、これはどういうパラメータかというと、プログラム内ではロボットの動きを複数作ってその中で最も良いものを提出しているのですが、その時間配分に関するパラメータです。

提出その4の改善で多少ましになりましたが、ロボットが嵌ってしまって永遠に終わらない、ということが、まだ起こっていました。 そのとき、適切に打ち切って別の動き方を考えないと、スコアは大幅に下がってしまいます。 そのためのパラメータがt_{limit}です。 ある動き方を作っている時間がt_{limit}を超えると、強制的に打ち切って次の動き方を考えるようにしています。

t_{limit}に関しても、NやVに関する依存性を調べました。 式はあまりきれいな形にはなりませんでしたが、スコアは改善されました。

最終的な点数は8216点で、最終的な順位は154位でした。

実装の詳細

どのように実装したか軽く書こうと思います。 僕はプログラム設計に関して深い知識があるわけではないので、詳しい人からするとあまり良くない部分があるかもしれません。 ですが、どなたかの参考になれば幸いです。

基本

オブジェクト指向的なノリで、Pythonのclassを利用しました。 Pythonistaの上位陣のコードを眺めると、classを使わず全て関数だけで作っている人がいましたが、僕はclassを使った方が書きやすいと感じています。

今回は、

• 盤面:Gridクラス
• ロボット全体:Robotクラス
• ロボットを構成する頂点:Verticeクラス

というクラスを作りました。

クラスからオブジェクトを実際に作り、出力する答えの候補となる動作を作る関数をSolve関数にまとめました。 そして、if __name__=="__main__"節でSolve関数を何回も呼び出すことで答えの候補を複数作り、最もターン数の小さいものをprintしています。

クラスの役割分担

上の3つのクラスに、次のような役割を振りました。

Gridクラス

• 盤面の管理、あるマスにたこ焼きが置いてあるか、もしくはそのマスがたこ焼きを置く位置か

Robotクラス

• 根の位置・それを動かす関数
• 提出その1で実装した、腕の回転を全探索して、その結果を返す関数
• 提出その2で実装した、根が受ける力を計算する関数
• 提出その4で実装した、たこ焼きを確実に掴む・置くための最適な根の位置・回転のさせ方を全探索する関数
• 計算した最適な動作を実行する関数

Verticeクラス

• その頂点を、親の頂点を軸にして回転させる関数
• たこ焼きを掴んだり置いたりできるか調べる関数
• たこ焼きを掴んだり置いたりする関数

Gridと他のクラスはともかく、RobotクラスとVerticeクラスをどう役割分担させるか、結構悩んだ記憶があります。

Solve関数

Solve関数は、答えの候補となるものを作る関数にしました。

for文を回して1ターンごとに動きをRobotクラスの関数で計算して、それをまたRobotクラスの動きを担当する関数に渡すことでRobotを実際に動作させています。

そして、盤面上に何個たこ焼きが残っているかという情報を管理して、しきい値 m_{th}以下になったら、ロボットの動かし方を変更するようにしています。

また、TLEにならないように時間を管理して、Solve関数の呼び出しから t_{limit}が経つと強制終了するようにしました。

if __name__=="__main__節

提出その3やその4で説明したように、Solve関数を1回呼ぶだけだと、運によって結果が大きく変わってしまいます。 そのため、複数回答えの候補を作ってその中で最も良いものを提出しているのですが、それをまとめているのがこの節です。

問題の標準入力を受け取って、TLEにならないように時間管理しながらSolve関数を複数回呼び出して、最も良いものを標準出力しています。

反省

初参加ということで、たくさん反省がありますが、とりわけ感じたのが、

ということでした。

普通の競プロのコンテストでは、長いコードを書くことが少なく、そして一旦正解してしまえばそのコードを見返す必要はありません。 一方で、AHCでは、自分の書いたプログラムに手を加えなければいけません。 自分が書いたプログラムであっても、時間が経てば詳細は忘れてしまうものです。 そのため、自分が書いたプログラムを読み返して理解しなければなりません。

ですが、僕が今回書いたプログラムは汚くて読みづらく、理解するのに時間がかかりました。 これからは、未来の自分が読みやすいような、保守性の高いプログラムを書きたいと思います。

また、次のAHCでは、様々な数理最適化の手法や、ビームサーチや焼きなましといったAHCの典型手法も使ってみたいです。 機械学習(特に強化学習)的なこともできるという噂を耳にしたので、ゆくゆくはそういうこともやってみたいと思います。

最後に

初参加でしたが、とても楽しかったです。 AHCは月1で開催されているので、また参加したいと思います。 ここまで読んでいただき、ありがとうございました。

こんにちは、Yotugiです。ICPC2024国内予選に九州大学からチームquery conquerorで出場し、全体順位79位で予選通過しました。
完全に乗り遅れましたが、模擬国内と国内予選の参加記です。最後まで読んでくれると嬉しいです。(以下常体)

こんにちは!

突然ですが,弊部はこの度部名を変更することとなりました.新しい名称は

九州大学新入生の皆さん,合格おめでとうございます!
私たち九州大学 ICPCチャレンジ部はAtcoderを始めとした競技プログラミングコンテストに取り組む大学公認サークルです!!
プログラミング力,アルゴリズム力の向上を目的に週1~2回程度参加しており,他サークルとの兼部も十分に可能です!