こんにちは。競技プログラミングのコンテストに参加しているyunixです。 estie プログラミングコンテスト2022(https://atcoder.jp/contests/ahc014)に参加しました。2週間は長くて超大変でしたね。 コンテスト中に考えたこととかやったことを書いていこうと思います。
お疲れ様です。AHC013(RECRUITE 日本橋ハーフマラソン2022夏)に参加して平均7435点くらいの8位でした。 コンテスト中にやったことを書いていきたいと思います。
続きを読む※この記事は包括的な解説というよりは、同じようなことをやろうとした人へのインプットになればいいかなと思っています。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
続きを読むこんにちは。競技プログラミングのコンテストに参加しているyunix (https://atcoder.jp/users/yunix )です。 最近行われたAtCoderのAHC011に参加して33位でした。 マラソン初心者なりに色々やってみて学びが多かったので、それについて備忘録として記事を書きました。
また、長期のマラソンマッチに時間をかけて参加するのは初めてだったのですが(と思ったけれどHTTFは割とちゃんとやってたな...)、コンテスト中に色々な方法を試して挙動がどう変わるかを調べたり、処理速度を改善したり試行錯誤することが本当に面白かったです。 試行錯誤してプログラムを書くことが面白かったということを伝えたい、AHCのようなマラソンマッチのコンテストに興味をもつ人が増えてほしいという気持ちで記事を書きました。
N色のリンゴがあり、各色のリンゴはそれぞれa_i個ある。
先手と後手が以下の行動を交互に行うようなゲームを考える。
このとき、最後のリンゴを食べたほうが勝ちになるとする。
先手と後手が双方最善を尽くした時、どちらが勝つか?
この手のゲームの問題は、"先手必勝の局面"の特徴は何か、ということを考えるとうまく行くことがあります。
もっと簡単な例でいうと、子供のころにやった遊びで、
というものがあると思います。
このゲームは
というわけで、正しくやれば先手が必ず勝ちます。
最初のターンで2までをカウントして、次に相手が3~5のどの数値までを数えたとしても、次に6を言って手番を譲り... ということを繰り返せば最終的に30を言うことができます。
この手のゲーム(いわゆる石取りゲーム)では、"相手が何を言っても最終的には勝てる"というような状態(必勝状態*1 )を決して手放さないような手順を考えることが大事になることが多いです。
この30を言うゲームでの必勝状態は"自分の手番で2+4nの数値までを言った"という状態です(n>=0)。
相手がその次にどのような手を指したとしても、自分のターンでまたこの状態に持ってくる、ということを繰り返すと最終的に勝つことになります。
NimやNimKなどで出てくるGrundy数の解析によって問題を解くのもこの考え方の延長で、"最善を尽くせば後手が必ず勝てるような局面"はGrundy数が0になっていて、局面のGrundy数を数えることで先手と後手のどちらが勝つかがわかります*2。
というわけで、このゲームでもそのような"先手か後手のどちらかが必ず勝てる状態"がないかを探してみましょう。
まず簡単のため、一色しかリンゴがない場合を考えましょう。
リンゴの数が
というわけで、リンゴの数が奇数: 先手勝ち、偶数:後手勝ち、という結果になります。
このことから、どうも各色のリンゴの数の偶奇が大事そうな雰囲気がしてきます*3。
最後のリンゴを食べたほうが勝ちなので、リンゴの数が偶数個の時に手番を譲られたほうが不利のような気がしてきます。
そこで、このゲームをプレイするときの戦略として、
という方針でやったら勝てそうです(今は全部偶数の場合は考えないことにします)。
この方針で実際にゲームに勝つことができて、
というわけで、このゲームにおいて、手番が回ってきたときに"すべての色のリンゴの数が偶数"の時は必ず負ける、逆に"どれか一つでもリンゴの数が奇数の色があるとき"には必勝になります。
最初の局面のリンゴの数、すなわち各a_iの偶奇を判定すればよく、コード自体は以下のようにとてもシンプルになります。
Submission #25883195 - CADDi 2018
def main(): N = int(input()) a = [int(input()) for _ in range(N)] odd_count = sum([(val%2) for val in a]) # aの中の奇数の数の個数を数える if odd_count==0: # 奇数の数が0の時、すなわちすべて偶数の時には先手負け print("second") else: print("first") if __name__ == "__main__": main()
*1:すいません、これは勝手に名前を付けただけです。この記事の外では使われていないので気を付けてください。
*2:ここではGrundy数については解説しません。たくさんの人が良い記事を書いてくれているので、そちらを探してみてください。AtCoderではABCの水色~青くらいの問題でGrundy数の解析が前提になる問題が出ることがあると思います。Grundy数を知っておくと、与えられた問題をどうやってGrundy数を数えるか、という問題に言い換えることができ、解答への糸口を得られることが多いです
*3:ここから先はあんまり論理的な展開ではないので語尾を濁しています。上のように簡単な例を使って考えると結果的に正しい方針を思いつけることが多いと思います。方針を思いつくまではエスパーでも、それが正しいことが説明できればOKだと思います。
