HTTF2023(AHC016)参加記録

こんにちは。競技プログラミングのコンテストに参加しているyunixです。 最近行われたHACK TO THE FUTURE 2023予選(https://atcoder.jp/contests/ahc016)に参加して6位でした! 上位10人に入れたのでオンサイトの本戦に行けそうです*1。とても楽しみです。

コンテスト中にやったことや考えたことを書いていこうと思います。

*1:競プロを始めたのがコロナ禍以降の2020年だったので、初のオンサイトコンテスト出場です。めちゃくちゃ嬉しい。

続きを読む

焼きなましをするときの設計に関するメモ

言いたいこと

焼きなましをするときにはこんな感じにクラスを作ると個人的にいい感じでした:

焼きなましをするときのクラス設計

  • 主に以下の2つのクラスからなります:
    • Stateクラス: 問題の状態を保持するクラスです。状態に関するクエリと状態を変更するためのコマンドのメソッドを提供します。問題によっては状態の一部を切り出して別クラスにしてそれを保持することもリマス。
    • Neighborhoodクラス: 近傍操作を司る抽象クラスです。Stateクラスへのポインタを保持し、execメソッドで状態を変更・rollbackメソッドで状態の変更の取り消しを行います。具体的な近傍操作はNeighborhoodクラスを実装する形で作っていきます。

このようなクラス設計をすることで以下のようなメリットがあったと思っています:

  • 関心ごとの分離

    • Stateは状態に関するクエリと状態を変更するコマンドを提供し、Neighborhoodクラスはstateが提供するコマンドとクエリを使って近傍操作のロジックを実装する、というように役割を明確にできます。
      • Stateに近傍操作のロジックを持たせても良いのですが、気を抜いているとStateが際限なく膨れていき、どこに何があったかを理解するのに負荷が大きくなります。近傍操作を切り出すことでこれを防ぐことができます。
  • 近傍操作をする際に状態管理の実装の詳細を隠蔽できる(これも関心ごとの分離の一種かも)

    • 近傍操作のロジックはstateクラスのpublicメソッドを通じて状態を操作することになります。したがってStateがどのように状態を管理しているかを近傍操作をする際には気にする必要がなくなります。
    • ラソンをやっていると状態管理の高速化がポイントになることが多いですが、状態管理を低レベルでどのようにやっているのか(例えば配列を使っているのか、bitを使っているのかなど)を近傍操作のロジックとは独立して変更することができます
  • 近傍操作の選択やrollbackの記述をシンプルにできる

    • 近傍操作を実装したクラスは全てNeighborhoodを実装しているので、ポリモーフィズムの恩恵を受けることができ、コードがシンプルにできます
  • 場合によってはState部分には単体テストを入れてもいいかも

    • ラソンマッチでバグりやすいのは状態管理のロジックだと思います。こういうところにテストが入れられると楽になりそう。
    • 特にStateで外部に公開している部分(command, query)の外部から見た挙動は結構変わりにくいのではないかという気がします。内部的な実装が変わっても使い続けられるテストが書けるならテストを入れてしまっても良いような気がします。

批判・自分はこうやっているなどのコメントをお待ちしてます^^

続きを読む

鉄則本マラソン Mayor's Challenge 感想

E8さんが出版した『競技プログラミングの鉄則』の中に収録されているMayor's Challengeというマラソンの問題をやってみました。 あまり包括的な解説にはなっていなくて、twitterに書きたかったことを書き殴ったような感じです(twitterではネタバレになってしまうかと思って...)。

ネタバレだらけなので問題を解いていない人は注意してください。

book.mynavi.jp

記念撮影: seed=0(0.98M点)

  • 参考文献など
    • terryさんの解説とtwitter
    • tomerunさんのブログ
    • takumiさんの解説
    • 公式解説
  • 解法の概要
    • 初期解の生成
    • 近傍
    • 評価関数
    • optuna
  • 感想
  • 疑問
続きを読む

AHC014参加記録

こんにちは。競技プログラミングのコンテストに参加しているyunixです。 estie プログラミングコンテスト2022(https://atcoder.jp/contests/ahc014)に参加しました。2週間は長くて超大変でしたね。 コンテスト中に考えたこととかやったことを書いていこうと思います。

  • 解法概要
  • 問題概要
  • 最初に問題を見て思ったこと
  • 問題に対するアプローチ
    • 方針を決める際に考えたこと
    • 最終的な解法
  • 実装面での工夫
続きを読む

AHC012参加記録

こんにちは。競技プログラミングのコンテストに参加しているyunixです。 最近行われたAHC012に参加して33位でした。 コンテスト中にやったこと、考えたこと、やればよかったことなどを書いていきたいと思います。

この記事の内容

  • AHC012の概要
  • 解法
  • 学びを得たこと
続きを読む

AWS上にマラソンマッチ用のジャッジ環境を作った

  • 背景
  • システムの概要
  • CDKやその他のコード
  • テスト実行結果
    • コスト
    • Lambdaのメモリに関する実験など
      • LambdaのメモリとCPUに関する仕様
      • Lambdaに割り当てるメモリ量を変えながら実験
    • 不満ポイント

※この記事は包括的な解説というよりは、同じようなことをやろうとした人へのインプットになればいいかなと思っています。C++ソースコード用に書きましたが、少し手を入れれば他の言語でも使えると思います。 AWSを触ったことがない人向けには書いていないです。すいません...

<7/23追記> Lambdaのメモリと処理能力について理解があやふやだったので検証した記録を残しました。メモリは1.8GBくらいにするのが良さそうです。

<8/20追記> 実際にコンテストで使ってみたところ、この構成だと不満が多かったです。それに関するレポートを書きました。

<11/7追記> 実際にプログラムを走らせるLambda(図の2番目のLambda)でプログラムをビルドしていたんですが、毎回ビルドするのは無駄が多いことに気がつきました(最適化オプション付きだとそこそこ時間がかかる)。1番目のLambadでビルドしてバイナリをS3にアップロード&2番目のLambdaでS3からバイナリをダウンロードするとコスト面で少し安くなると思います。 また、最近はStepFunctionsいらないかなという気分になっています。StepFunctionsではLambdaの並列実行を担保していてコードはすっきりするのですが、コストが微妙にかかるのと、処理時間がかかってしまうので、ちょっと微妙かなと思い始めました。並列実行が全部終わることを担保するのはクライアント側の方でやればいいかなと思っています(もしくは全部終わったかを確認するLambdaを作るか)。

<11/13追記> tsutajさんに問題を見つけていただいたのですが、GLIBCのバージョンが古いことでエラーが起きているようです。 コンテナのOSのバージョンを上げるように変更をしました。 月報 (2022 年 10 月) - hogecoder

続きを読む