カメヲラボ

主にプログラミングとお勉強全般について書いてます

競プロ日記011: 今年のまとめ

今年からマラソンマッチを本格的に始めました。また、マラソン力強化のためにAtCoderのアルゴにも挑戦してみました。来年以降もしばらく続けてみようと思うので、将来の自分とこれから競プロをやってみようかと思う方々の参考として、これまでのまとめを記録しておきます。

TopCoder Marathon Match(MM)

2022年のMMレーティング

2013年に初めてマラソンマッチに参加して、この時のレーティングが1720だったので、まずはそれを目指しましたがなかなか成績が安定せず、最高でも1625でした。しばらくはギリギリYellow Coderが続きそうです。とはいえ、初参加時の何となく解法と比べると自分が何をしようとしているか理解した上で解答できている感覚はとても大きくなっているので、単純に数値で判断するのも良くないかなと感じています。

現状では問題点が割とはっきりしています。それは、「自分より上位の人とアイデアはさほど変わらないのに、常にスコアが1割くらい低い」ということです。どうしてかというと、最適化云々以前に自分の実装がゆるいからです。たとえばグリッド上で最短経路を求めるようなケースで複数の案がある場合、状況に応じてその中からより良さそうなものを見つける、あるいは優先順位がつけにくい場合に確率的な偏りの少ない案を選ぶとか、その辺りの対処がきちんとできていない場合が多かったです。

これは単なる一例ですが、あらゆる実装面でこのような緻密さが足りないことが多く、その結果探索の精度が落ちるため持ち時間の10秒を十分に活かしきれていません。今後はその辺を丁寧にやる訓練が必要です。スコアが上がらない場合にほぼ100%陥ってしまったのは、「上位の人はきっと天才的なアイデアをもっているからだ。自分のような凡人には思いつけないんだ😢」という思考になって自分の今やっていることを信じられなくなるというミスでした。この辺は自分の実績とか性格の影響が大きいと思いますが、もっとトレーニングと実戦経験を重ねて克服するしかありませんね。

AtCoderアルゴ

MMと短期AHC(AtCoderヒューリスティック)の力を鍛える一環として、短時間でのコーディング力を高めるためにアルゴの方にも何回か参加するようになりました。とりあえず今の実力だと、このまま続けると緑くらいまではいけそうかなーというとことで止まっています。マラソンに役立っているかというとあまり関係なさそうというのが現時点の感想で、どちらかというとこれはこれでちゃんと過去問とか対策をして真剣に取り組んだ方が絶対面白いような気がしています。もう少し時間にゆとりができたら、将来的にこちらも本格的にやってみたいかなという気分です。

現状では3~4問解けるくらいで順位が大体2500~3000辺りですが、同じ解答数でも解くスピードが速いと順位的には1000くらい差が出るみたいです。最初の4問を高速に解答できたと仮定して5問目を解いた場合にACできたりもしているので、基本的にはスピードアップのトレーニングをすべきですね。周囲を見渡すと1000問以上解いている方ばかりなので、来年はできるだけたくさん解いて、500問くらい解いたらABCに数回チャレンジしようと思います。

それから使用言語に結構悩んでいて、Pythonで書いてみたりC++で書いてみたりしていたのですが、当初のMMの力を鍛えるという当初の目的からぶれないようにC++一択でやろうと決心しました。まあMMのことを考えなくても、PythonでTLEしたときに「もしかしたらC++なら通るかも…」みたいな気持ちになりたくないという気分ということもありますが…。

来年に向けて

一番はやはりMMで過去の自分を超えることですね。それから、AHCの方もMMと同じくらい頑張りたいと思います。ただ、スケジュール的にAHCとMMが重なったり、AHCが短期コン(4時間)とかだとなかなか参加できなかったりするので、やっぱりMMよりは優先度が下がると思いますが。まあそれでも青には到達しておきたいと思います。

つい先日Psyhoさんによるヒューリスティック・ボットコンテストのための無料Tipsをまとめたところですが、こういうのを見ているとやはり自分自身でアウトプットを重ねてまとめるという作業は必須化のような気がします。まあ今の時点でもそれなりに自分用のドキュメントを作ってはいますが、どんどん公開していったほうが良いかもですね。

ではまた来年!

Psyhoさんによるヒューリスティック・ボットコンテストのための無料Tips

ある日、マラソン王者のPsyhoさんがつぶやきました。

要約すると、

これから24時間、1いいね毎にヒューリスティック/ボット プログラミングコンテストのヒントを投下します。

という話です。このまとめ記事を更新する時点で1000を超えるいいねがついていて、皆Psyhoさんのありがたいお言葉を楽しみにしています。というわけで、私が1つ残らず捕捉して順次日本語にしていきます。基本的にはDeepLとChatGPTで翻訳して、そこからさらにざっくりと私が適当にまとめました(意訳がちょっとあるのと、見出しや補足のために多少の追記があります)。まずは精度よりも速度重視でやっていきますので、翻訳に問題がある場合はご指摘いただけるとありがたいです。 英語を読むのが辛くなければ実際のツイートを見るのがベストですが、どうしても英語がツライという方はどうぞご利用ください。

一般的な話題(その1)

#0: 無料のアドバイス

誰もが個性的で、いろんな背景を持っています。一人一人が異なるテーマで苦労しています。 すべてのアドバイスがあなたに当てはまるわけではありませんが、できるだけ一般的なものにするよう心掛け、状況に特化したものがある場合はその旨を述べるようにします。

#1: 1週間あれば、コンテスト中にあらゆる研究ができる

たとえ経験が浅くても、ひとつのコンテストに一所懸命取り組めば勝つチャンスはあります。これは何年も練習が必要な短期のプログラミングコンテストとは対照的です。

#2: 高度な数学は必要ない

シミュレーションのコードを書くという選択肢は常にあります。私が参加した約200のコンテストで、数学の知識があったために良い成績を収めた例は1つもありません。例外があるとすれば、ベイズの定理くらいですね。ちなみに私は微積分を知りません😅。

#3: ヒューリスティック(以下H)コンテストでは、ビームサーチと焼きなまし

グラフ理論動的計画法線形計画法、フロー問題などをきちんと経験しておくと便利な場合もあります。

#4: タッチタイピングは超重要

もしタッチタイピング(いわゆるブラインドタッチ)ができないなら、最優先すべきです。だいたい10時間から30時間くらいかかると思います。 タッチタイピングをすることで、コーディング中に他のことを考えることができるようになります。バグの数を減らし、プロトタイピングをスムーズにする、などなど。

#5: H(ヒューリスティック)コンテストとB(ボット)コンテスト、どちらが良い?

標準的なテクニックの違い以外に、主な違いは、Hコンテストでは迅速かつ正確なフィードバックが得られるのに対し、Bコンテストでは一般的により楽しいということです。 Hコンテストでは、より速いペースで学習することができます。

#6: コンテストを開催するのに最適なサイト

H: Topcoder (マラソン), AtCoder (AHC) B: CodinGame (今、コンテストが開催されています!) どのサイトも、良い問題、公平な評価システム、コンテスト後に解法について話し合うコミュニティが特徴です。 UIが荒いサイトもあるかもしれません;)

#7: [H]問題についてググるのは大体時間の無駄

良い問題デザイン(上記のサイト)とは、問題作成者が問題がユニークであることを確認したことを意味します。 ※まれに例外もあります。特定の部分問題でよく知られているものを研究するのはアリかもしれません。

#8: プロトタイピングのスピード

ほとんどの人にとって、最も制約の多いスキルはプロトタイピングのスピードです。 ある程度の経験を積めば、実装したいアイデアが常に何十個も出てくるようになります。それをいかに早く反復できるかということが、限界の要因です。速ければ速いほど、問題点を早く知ることができます。

#9: 1つのコンテストに集中する

早く上達するためには、中途半端に多くのコンテストに参加するのではなく、一つのコンテストに集中することが一番です。 基本的な解法ばかりやっていても、あまり身につきません。正しい学習期間は、壁にぶつかってどうしたらいいかわからなくなったときから始まります。自分を追い込まないと結果は出ません。

焼きなまし法(SA)について

#10: SAに代わる局所探索はすべて(ほとんど常に)ダメ

遺伝的アルゴリズム、タブーサーチ、蟻コロニー、などなど。これらは忘れてください。これらは効果が薄いだけでなく実装に時間がかかります。

#11: なぜSAなのか?

  • 山登り法(HC)から始めて、2行追加でSAに変換することができる
  • 高速な動的評価が可能
  • 適切に調整すれば、他の手法よりも高いポテンシャルを発揮する(高速なので)
  • 非常に高速なイテレーションが可能

#12: 標準的なSA

温度スケジュール: t = t_start * (t_final / t_start) ^ time_passed、time_passed は 0..1 の範囲

受理(最小値が良い場合): RNG() < exp((cur_result - new_result) / t)、RNG() は 0..1 を均一に返す

出発点としては、ほとんどの場合でこれが最も良いです。

#13: SAにおける温度管理は受理率がゆっくりと減少するようなものが良い

同じ受入率の値にずっと留まっていると、効果がありません。

#14: 局所最適解に陥りやすいときの対処法

  • 非常に高い温度/加速度
  • 複雑な遷移状態(※訳注:遷移状態を複雑にして解の変更を緻密にすることで、局所最適化から抜け出しやすくなる?)
  • (まれに)キック(※訳注:解を強制的に変更する)
  • (まれに)ソフトリスタート(解法は変えずに温度管理をやりなおす)
  • (まれに)複数回実行

#15: 制約のために多くの状態が無効になる場合に行うこと

a) 初期重み0、最終重み∞の衝突回数に基づくスコアリング要素を追加する。 b) (可能であれば)部分的な解に対して高い温度で短いSAを何度も実行する。

#16: 評価が非常に高速の場合に行うこと

これはあなたの想像以上にずっとよく起こります。

#17: SAの全体的な優先順位

  • 異なる遷移関数のプロトタイプを作る
  • 評価関数を非常に高速にする(つまり動的にする)
  • 適切な温度管理を見つける(通常3-4回実行するだけで十分)
  • たくさんテストする
  • 上記が終わってから、他のことに移る

#18: 常に最良結果を更新し、最終結果ではなく最良結果を返すようにする。

このミスを何度見たかわかりません。常に最良結果を更新することで、最終的な温度をより高くすることができます。

#19: SAがイマイチな場合

  • 局所最適に陥りやすい: #14にヒントがあります。
  • 単純な遷移と複雑な遷移が混在している: 各遷移に対して別々の受容関数を用意する。
  • 遷移中に評価が非常に不安定になる場合: 運が悪かったとしか言いようがない さて、SAについてはもう十分でしょう。

コンテストは基本的に単純なフィードバックループです。 a) 何かをする b) 結果を得る c) 情報を抽出する

このうちのどれかを改善することで、より良くなることができます。しかし、最も軽視されているのは(b)の部分です。

テストについて

#20: テストはコンテストで最も軽視されている点である

テストは、フィードバックを得るための手段です。もしテストが遅ければ、進歩は非常に遅くなります。テストが不正確だと、正しい次のステップを見つけるのが非常に難しくなります。 Bでのテストは非常に難しく、ほとんど実行不可能なことが多いので、これは主にHに焦点を当てます。

#21: [H]ローカルのテスターを使う

もしあなたが評価のために仮のテストを使うだけなら、あなたは自分自身にとってすべてを非常に困難にしています。時間を節約するのではなく、無駄にしているのです。 (※訳注:ローカルでテストせずに提出してスコア確認するのは時間の無駄ですよ)

#22: [H]良いローカルテスターを使う

絶対に必要なのは、次の2つの機能です。 - マルチスレッド(複数のテストを別々のスレッドで実行する機能) - 相対スコアリング(これはtopcoderの標準機能です) もし自分で持っていないなら、私のものを使ってください: https://github.com/FakePsyho/mmtester

#23: テストの速度は制約になりやすい

あなたの解法がコンパクトで簡単に拡張できる場合、数秒で機能を追加/削除することができます。つまり、コンテストのある時点で、解法の異なるバージョンをテストすることが主なボトルネックになりそうなのだということです。

#24: 素早いテストのために外部VMを使用する

強力なマシンを持っていない場合は、AWS/GCP/Azureを使用して素早くテストすることができます。Linuxの知識があれば、1-2時間で習得できます。スポットを使えば、5ドルであなたのノートパソコンと同等のものを1週間稼働させることができます。

#25: テストをできるだけ頻繁に実行する

コンテストでは、自分でテストができるようにテスターが用意されています。 テストを行えば、あなたがどこかでミスをしたのかがよくわかりますし、改良点についてのフィードバックも得られます。

一般的な話題(その2)

#26: バージョン管理は悪

あなたはgitの使い方にとても慣れていて、それでスピードが落ちることはないと感じているかもしれません。そしてそれは真実かもしれません。とはいえ、もしそれが自分にとって便利だと感じているのなら、あなたはプロトタイピングが下手なのです。プロトタイピングのスキルを見直しましょう。

#27: バージョン管理は悪だがテストを実行するときは別

テストを実行するときは現在のソースファイルを保存しておくと便利です。これは、予期せぬ結果が出たときのサニティチェック(※訳注: ある状態や結果が正しいかどうかを確認する)として機能することが多いです。テスト時にソースファイルを保存する短い.sh/.batスクリプトを作るだけでよいでしょう。

#28: コードを最適化する価値があるかどうか迷ったら、制限時間を延ばして実行してみる

これは非常によく使われるシンプルなテクニックです。潜在的な利益が非常に低い場合は、コードを最適化しないようにしましょう。

#29: 言語の選択 - C++は孤高の王者

マクロはC++の問題の多くを解決することができますが、あなたが何をしているかを知っていれば、C++から他の言語よりもはるかに多くのものを絞り出すことができます。 *私はRustの経験がない+非常に複雑なトピックなので、あまり真に受けないでくださいね。

#30: 何よりもバグを取り除くことを優先すべき

バグがある場合、その解法はあなたが思うようには機能しません。これは、テストを実行するたびに、間違った結果を得ることを意味します。問題に対する直感が正しく育たなくなるのです。 とても重要なことです。

#31: 直感に反する結果が突然出たら、その度に調査をする

バグがあるのか(上記参照)、直感が狂っているのか、どちらかです。後者の場合は、これを学習経験として扱い、なぜ間違っていたのかを突き止める必要があります。

#32: 解答コードは小さくまとめる

コードが多くなると - バグが増える - コードの内容を全部覚えるのは、精神的にもっと大変です。 - (通常)依存関係が多くなる -> リファクタリングのコストがかかる 上位の多くは、400-1000行程度のコードです。

#33: コンテスト参加後は必ずフォーラムを読むこと

これまで述べてきたすべてのプラットフォームにおいて、(ほぼ)すべてのトップクラスの競争相手が、コンテストが終了した後に自分の解法を説明しています。コンテストに参加した後、他の人が何をしたかを読まないのは、信じられないほど無駄な機会です。 では、なぜそのようなコンテストで常に優秀な人がいる一方で、常に苦戦している人がいるのか、その理由を説明しましょう。

#34: 良い解法には時間がかかる

まず当たり前のことですが、良い解法を開発するには時間がかかります。 魔法のようなテクニックや回避策はありません。でも、時間が経てば速くなりますよ。

#35: 実行 > アイデア

なぜ、多くの異なるアプローチが上位にあるにもかかわらず、どれも同じようなスコアなのか、不思議に思うかもしれません。このような場合、「完璧なアイデア」を持つことよりも、「うまく実行すること」が重要です。

#36: 問題文やテスターのコードを隅々まで読む

問題文の細かい部分を思い出せるようになるまで、問題文を読み直しましょう。テスターのコードも同様に読みましょう。 最初に読んだときには見逃していたような小さな詳細がよくあります。特に、非自明な論理を含む場合は、提供されたコードも読んでください。

#37: 何が自分のモチベーションになるかを見つける

多くの競技者にとっての最大の原動力は、自己研鑽の喜びです。HでもBでも、未来の自分が過去の自分より良くなろうとする孤独なゲームであることがほとんどです。他の競争相手をベンチマークとして扱い、自分の目標とはしないことです。

#38: 大して良くならない解法に時間を浪費しない

現在の解法が良い結果を出せないことがわかっているなら、それを最大限良くしようとしても意味がありません。 リーダーボードの頂点に立つ最も簡単な方法は、高い目標を掲げて失敗することです。

#39: ツールで生産性が爆上がり

Hの場合は主にローカルテスター。Bの場合はローカルリーグ方式です(信頼性は低いですが)。私の試算では、ローカルテスター(リンク先)を改良した後、コンテストに費やす時間が30~40%程度減りました。

#40: 優れた競争者はアイデアが尽きない

テストを実行したり、ビジュアライザー(H)/ゲーム(B)を見たりすることで、より多くのインスピレーションを得ることができます。解法に取り組むことで、アイデアを得ることができるのです。最初のうちは、どんなに優秀な人でも、何がベストな解法なのか、まったくわからないものです。

競プロ(アルゴ)的なお話

また切り替わる。CodeForcesからたくさんの人が参加してくれたので(マイクありがとう😁)、古典的な競技プログラミング(CP)とH/Bコンテストの違いについて話してみようか。 ちなみに、今はもうクラシックCPはやっていませんが、topcoderで4位になった時期もありました。

#41: CPとH/Bコンテストは全く違うスキルが必要

CPは短距離走で、非常識な集中力と豊富な知識が必要です。 H/Bはマラソンで、長期的な計画と創造的思考・問題解決が主体です。

#42: CPの場合「相手」は問題設定者であり、H/Bでは(主にH)、相手は過去の自分である

H/Bでは問題解決に終わりはなく、解決は継続的なプロセスです。コーディングセッションの間に自分の生活を合わせなければならない。問題の切り替えが非常に難しいのです。

#43: CPでは最悪のケース、H/Bでは平均的なケースを気にする

これにより、完全に新しいクラスの技術が開かれます: - ランダム化アルゴリズム - 特殊なケースを素早く処理するための様々なバージョン - プルーニング(早期終了) (※訳注: プルーニングは計算時間やリソースを削減するために処理を途中でやめることで、探索アルゴリズムだと枝刈りのようなものだと思ってください)

#44: CPの経験があると、H/Bコンテストの基礎が固まる

CPのアルゴリズム知識はある程度しか役に立ちませんが、非常に比較的短時間で繰り返しコードを書くため、プログラミング言語の練習やバグのないコードの書き方を身に付けるにはとても効果的です。

#45: CPは就職に有利、H/Bは仕事ができるようになる😁

多くの企業が採用活動でプログラミングパズルを使用しますが、CPはそれ以上に大して役に立ちません。H/Bコンテストは、AI企業に入社するとよく遭遇する小規模な研究に似ています。

初心者向けアドバイス

では、初心者の方へのアドバイスです。

#46: プログラミングの初心者にはH/Bコンテストを勧めない

もしあなたがプログラミングの初心者なら、H/Bコンテストはお勧めしません。 まずCPに挑戦し、言語のシンタックスを学び、BFS/DFSや1次元DPなどの簡単なアルゴリズムを学びましょう。基本的なことを素早く理解するためには、より速いフィードバックサイクルが必要です。

#47: コンテストを見つけ、そのための時間を確保し、ベストを尽くそう

おそらく失敗するでしょうが、それでいいのです。失敗することは学ぶことであり、勝つことは何も教えてくれません。自分がうまくいかなかったと思う理由をすべて書き留めておいてください。自分が苦労しているところを見つけるのです。

#48: 出場しなくても、問題を読むのはアリ

以前見たことのあるような新しいコンテストを見かけたらフォーラムを全部読んで、何か応用できそうなことがないか見てみましょう。 少ない経験で良い成績を残すには、圧倒的に簡単な方法です。

#49: コンテスト開始当初は(コンセプト的に)シンプルな解法の実験に集中すること

あなたの目標は、問題に対する直感を養うことであって、手っ取り早く得点を稼ぐことではありません。アドレナリンが出るのは良いことですが、長期的には何の役にも立ちません。

#50: 可能性のあるアプローチを評価する良い方法は、良い答えで終わるために、どのようなステップを実行しなければならないかを考えてみること

もし、それが不可能であったり、非常にあり得ないと思うのであれば、おそらくそれは良いアプローチではないでしょう。

#51: 小さな漸進的な変更に集中する

解法を書き換えることは避けましょう。 小さな変更=速いフィードバックサイクル、少ないバグ、より良いモチベーション。ちなみに、私は自分の解法を書き換えたことはありませんし、テストせずに10~15分以上経過することはほとんどありません。

#52: コードの最適化は、悪い解法を素晴らしい解法に変えることができる

ほとんどの反復的アプローチ(SAなど)では、そのアプローチが良い結果を生むまでに、ある程度の重要な反復回数/ステップを必要とします。コードの最適化によって、全く新しい可能性が開けることもあるのです。

#53: もしテストやゲームの結果に一貫性がないと感じたら、それはテストやゲームの数を増やせということ

解法が改善される一方で、テストの精度を高めるために、より多くのテストが必要になります。1回の実行で 2-5K テストを使用することは珍しくありません。

#54: Pythonをコンテストに使わない

Pythonはある用途には最適ですが、通常の操作ではおよそ100倍も遅くなります。妥当な速度を得るためには、コーディングやアルゴリズムで非常に創造的になる必要があり、それはあなたのコードがずっと複雑になることを意味します。そこまでする必要はありません。

#55:自分を信じること。

自分はうまくいかない、手が届かない、と盲目的に思い込んでしまうと、モチベーションを維持するのはとても難しいです。私は、考え方を変えただけで、突然良いパフォーマンスを発揮する人にたくさん会いました。

最適化のお話

さて、次はコードの最適化に関する一般的なテクニックを紹介します。

#56: コードの最適化に理論的考察の必要なし

ターゲットマシーン上でコードを実行し、それを測定しましょう。 コンパイラのバージョン、OS、プロセッサの違いは大きな影響を与えます。

#57: N次元の座標は1次元に統合する

これは非常によくあるテクニックです。2次元のグリッドがあり、その上でBFSを実行するとします。(行, 列)を使う代わりに、それらを1つの値にマージします。メモリフットプリント(※訳注:メモリ使用量と考えてください)、演算数、コード自体を減らすことができ、通常は10-30%高速化されます。

#58: メモリ割り当ては非常に遅い

メモリプールの経験(※訳注:自分でメモリの割り当てをやり繰りする経験と思ってください)がない限り、一般に、すべての配列を一度だけ割り当てるようにしたいものです。時間計算量と空間計算量がO(N)の関数では、呼び出すたびにメモリを再割り当てすると、最大で10-50倍の速度になることがあります。

#59: 本当に必要なデータ構造は配列だけ

本当に必要なデータ構造は配列だけです。すべてのデータを単純な配列に置き換えることができないのは非常に稀です。 とはいえ、データ構造の最適化は複雑さを増す可能性があるので、時期尚早と考えることもできます。

#60: 剰余演算子は驚くほど遅い

正直なところ、理由はわかりません。でも、そういうものなんです。 次のように書き替える、かなり高速になることが多いです。

x = (x + y) % m

x = x + y
x -= x >= m ? m : 0
(y < m, y > 0, m > 0 と仮定して)

の方が速い場合が多いです。 (※訳注: typo修正済み)

#61: できることはすべて事前に計算し、それらの値を配列に格納しておく

常に良いというわけではありませんが、いくつかの演算は思ったより遅いかもしれません。例えば、"x ^ y"を事前に計算することは、その場で計算するよりもかなり速い場合があります。 (※訳注: これはxのy場を意味しています)

#62: 大きな配列を扱う場合、可能であればできるだけ小さな変数型を使用する

メモリコピー/クリアはバイト数だけを考慮します。これにより全体的なキャッシュ効率も改善します。単一の変数に対しては行わないでください。

#63: Fast-Clearing Arrayを使う。

3つの異なる操作を必要とするboolean配列をイメージしてください:

set(pos, value)
check(pos)
clear() - 配列全体をクリアする

ナイーブな実装ではO(1)+O(1)+O(N)ですが、カウンター(clear -> counter++)を持つint配列を使用することで、O(1)+O(1)+O(1)にすることができます。 (※訳注: tomerunさんのブログが参考になります)

#64: Fast-Clearing Arrayを拡張する

  • クリアするたびにカウンタがxずつ増えるなら、0..x-1に値を格納できる。
  • 衝突が許容されるなら、多くの場合、これはセット/マップを置き換えることができます。

#65: グラフには番兵を置く

グラフ内に特別なガード/境界を追加することで、経路探索中の操作数を削減できます。 例えば2DグリッドでBFSを実行する場合、境界条件のチェック(グリッドの外へのステップ)を避けるために、すべての方向に1ずつグリッドを拡張するとよいでしょう。

#66: 一般的に最も重要な高速化は、アルゴリズムを差分にすること

例えば、TSP(Traveling Salesman Problem)にSAを適用して、都市をパス上の別の地点に移動させる場合、Δにしか関心がないので、evalはO(1)であるべきです。

(※訳注: Δは変化量、差分という言葉は時間計算量が定数時間であると読んでください。)

(※訳注2: 当初は「差分」と書かれている部分を「動的」としていましたが、動的ではなく差分と解釈した方が良いのではとtoast-usさんからご指摘いただきました。確かに、ある状態を計算する場合や盤面の評価関数を計算する場合、前の状態を利用して差分計算するのは高速化にかなり良い影響を与えるという文脈だと思うので、それが良さそうです。)

#67: 時間の計測はコストがかかる(ことがよくある)

一番早いのは rdtscを呼び出す方法ですが、サイトによっては別の方法で時間を計測しているところもあります。c++でよく使われるgettimeofday()はシステムコールで、 プラットフォームによっては非常にコストがかかります。1Kコールで1秒以上かかったこともありました。

#68: プルーニング/早期終了/単純化された計算を使用する

これはあまり起こらないことですが、単純に計算をスキップする場合があります。これは主に評価関数で発生し、いくつかの遷移でスコアが完全に壊れてしまうので、すぐにわかります。 (※訳注: ちょっとわかりにくいですが、「評価関数において、ある遷移がスコアを完全に壊してしまうような場合、つまりスコアが良くなる見込みが全くないとわかった場合、その遷移を完全に打ち切る(枝刈りする)と良いですよ」という意味かと思います。)

#69: 非常に重いコードの最適化を行う場合は、ジャッジマシンをミラーリングする

gccの正確なバージョンを持っていることが一番重要です。 とはいえ、私は一般的に5%未満のスピードアップを目指す程度ならお勧めしません。パラメータの最適化の方がはるかに簡単です。

#70: SIMD/自動ベクトル化は超強力

私は最近これを使うことはありませんが、それでも強力なツールです。SSE/AVX命令セットを使うのは、ミニパズルを解いているような気分です。最高のコンパイラを上回るのは簡単で、重要な場所で2-20倍のスピードアップが可能です。

#71: [gcc]コンパイラのフラグ

"#pragma GCC optimize (...)"でコンパイラのフラグを(ほとんど)オーバーライドできるようになっています。 私は"Ofast,omit-frame-pointer,inline,unroll-all-loops"を使っています。理論上"omit-frame-pointer"は"-O1"に含まれますが、こちらの方が速かったです🤷。コンパイラのフラグでHC(山登り法)ができる😅。

(※訳注: 「inline、-O3、-ffast-math、-funroll-loops、... 他の便利なフラグはありますか?という質問に対してのツイートです」)

ボットコンテスト(コドゲ)について

ボットコンテストに特化した話をあまりしてきませんでしたので、ここからはそのお話をしましょう。 Bコンテストは形式も問題の内容もさまざまです。ここではCodinGame(コドゲ)に焦点を当てます。コドゲは頻繁にコンテストを開催する唯一のサイトです。

#72: ボットゲームの新しい概念

ボットゲームには新しい概念があります。それはメタゲームです。最良の戦略は、他のプレイヤーが採用する戦略によって大きく変わります。これは特に、不完全情報のあるゲームで問題が発生しやすいです。自分の解法をまともに評価することは忘れてください。

#73: 勝つか負けるのみ

各テストは本質的には、二者対戦ゲームであり、勝ちか負けかという2値の結果になります。どれだけ大きな優位/劣勢があっても、勝ちか負けかにしか過ぎません。自分の解法をまともに評価することは忘れてください。

#74: ローカルテスト

ローカルでうまくテストを実施できるようにするには、リーダーボード上のボットに代表される様々なアプローチを持つ必要があります。 解法をまともに評価することは忘れてください。 (※訳注: 自分のボットをテストするには、他のさまざまなボットと対戦するとよいといういみだと思います)

#75: フィードバックは重要

#20を覚えていますか?コンテストはフィードバックのループです。自分の解法を効果的に評価できない場合、直感力を高めることは困難です。 ボットコンテストでは、ノイズの多いフィードバックを受け、次のステップについて非常に大胆な推測をする必要があります。

#76: ボットコンテストは時間投資が大きい

ボットコンテストは、ヒューリスティックコンテストよりはるかに大きな時間投資を必要とします。 - フィードバック機構が非常に弱い - 常に進化するメタゲーム - すべてのリプレイにアクセスできるため、誰もがあなたのボットのプレイを知ることができる(そして、それに対抗することができる) - (しばしば)より複雑なルール

#77: 楽しいけれども初心者向けではない

ボットコンテストはインタラクティブなため、同じようなヒューリスティックコンテストよりもずっと楽しいものになる傾向があります。しかし、私は一般的にボットコンテストを初心者のための良い学習プラットフォームとして勧めません。フィードバックループが効果的でないため、自分の行動と結果を関連付けることが難しくなります。

#78: HスキルはBでも役立つ

Hで得たスキルや知恵のほとんどは、Bコンテストにも適用できます。 プロトタイピング。良いワークフロー。コードの最適化。多くのアルゴリズムとテクニックが適用できます(ビームサーチも使えます)。

#79: 2種類のテクニックのタイプ

多くのテクニックは2つのタイプに分類されます。1つは複雑な状態評価(別名ヒューリスティック)関数、もう1つは検索(ビームサーチ、ロールアウト、MCTS)です。 どちらが有効かは問題によって大きく異なりますが、成功するためには両方をマスターする必要があります。状態評価にニューラルネットが使えれば最強です。

#80: ノイズを無視する

評価は非常にノイズが多いので、それを完全に無視して、うまくいくと思われる解法に集中するのが良い場合があります。 検索ベースの解法は、メタゲームにあまり依存しない傾向があります。また、ローカルリーグのシステムを開発し、状態評価の調整を自動的に行うのもよいでしょう。

ボットコンテスト用のツール

これはヒントではありませんが、私は自動マッチメイキングを行う簡単なローカルリーグシステムに取り組んできました。mmtesterと似たようなものですが、ボットコンテストのためのツールです。 近い将来、PyPIパッケージとして公開できればと思っています。

#81: [コドゲ限定]持ち時間の使い方

通常、最初のターンの制限時間は1秒ですが、次のターンでは50ミリ秒になります。相手の行動が限られている場合は、最初のターンで2-3ターン先を「考える」ために使うのは非常に有効です。

#82:

現在のメタゲームを追いかけ、トッププレイヤーを真似ることで順位が良くなるかもしれませんが、長期的にはあまり多くの学びにはなりません。 もしあなたの目標が自分自身のレベルアップなら、そういったことを避けてみてください。

ここで一区切り

お話ししたいことは一通り触れたと思います。もちろんTwitterのスレッド上なので、共有すべき知識や知恵が大量にあることに比べればとても浅いものですが。 あとはQ&Aとまとめのために残しておこうと思う。 おやすみなさい💤。

この記事の作成者より

この先はQ&Aがいくらか続くと思いますが、何か目についたものがあれば追記しておきます。内容的な修正と見やすくする作業は続けます。

競プロ日記010: MM142に参加しました

TopCoderマラソンマッチ(MM142)に参加しました.最終結果は19位でした.

問題の概要

N×Nのグリッド上にいくつかプレゼントが配置されています.このグリッド上(一番外側)に,一定の確率でエルフが生えます.このエルフたちをN×Nターン操作して,プレゼントを盗み出すという問題です.障害物としては,所々に木が生えています(初期盤面から固定されていて,途中で現れたり消えたりすることはありません).また,エルフの動きを邪魔するため,AIがグリッド上に木箱を配置(0個以上,複数設置可)する場合があります.ただし木箱設置にはお金(金額はパラメータCとして固定)がかかり,お金は毎ターン1ずつAIに与えられます.AIはテストケース毎に5種類の中からランダムに選ばれ,これらのAIは過去の問題(MM131)で参加者が作成したプログラムだそうです!

プレゼントをエルフがグリッド外まで持ち出すことができれば,盗んだとみなされます(つまり持っているだけではダメです).すべてのプレゼントを盗むことに成功すると,N×Nターン経っていなくてもプログラムは終了します.プログラムが終了したとき,持ち出したプレゼント数×100と,終了までにAIが使用したお金の合計額を加えたものがスコアになります.たとえばプレゼントを3個盗み出し,その間AIが50のお金を使ったとすると,スコアは350になります

やったこと

最初の解答

おそらく多くの人がやったであろう,

  • プレゼントまでの最短経路を通ってプレゼンを取る
  • プレゼントからグリッド外への最短経路を通って脱出する
  • プレゼントまでの経路が見つからない場合は適当な箱に対して同じような処理を行う

といったものでした.当然プレゼントまで進む途中に箱を置かれてしまうので,プレゼントを取れずに箱ばっかり取る事になります.それでもCが大きくグリッドが大きいものであればそれなりにプレゼントを取ってくることができるので,これだけでも70点くらいは取れそうな感じです.経路の計算が間違ってて最短経路じゃない場合,AIが余計に箱を設置することになってスコアが少しだけ高くなったりすることもありましたが,そういうので得点が上がってもあまり嬉しくないです.

2番目以降の解答

2番目以降の提出では,プレゼントまでの経路中に箱が置いてある場合への対処を主に行いました.

プレゼントの前に箱がある
プレゼントの前に箱がある場合,これを持ち去ったとしてもまた箱を置かれてしまってプレゼントが取れなくなるため,手助けが必要になります.
1人助けが来る
1人が箱を取る
空いたところにもう1人が入る
1人が箱を取り去り,空いた部分にもう一人が素早く(同じターンに)入り込みます.
プレゼントGET
しかしこの方法だと,多くの場合はさらに箱を置かれて道がふさがってしまいます.
箱置いて塞がれる
ですので,プレゼントを取りに行ったエルフの隣に箱を持ったエルフを潜り込ませて,帰り道を確保しておきます.
箱を置かれないようにブロック
2人並んで帰る
70点以上を目指すには,基本的にこの動作に類するものが必要になります.

やりきれなかったこと

私の解答では,上手くいった場合に上記のような動作をしてくれますが,実際のところはいろいろと不具合があって,エルフが閉じ込められたりすることも結構ありました.対処としては,脱出したいエルフの逃走経路を確保するために別のエルフを派遣することです.これも上手くいったりいかなかったりなので,しっかり修正して提出したかったですが間に合いませんでした.あとは逃走経路に他のエルフが立ち入ってしまってデッドロック状態になる場合もあって,その辺の対処も不完全でした.この辺りがもう少しスッキリ書けていれば,もう1~2点上がるかなーと思っています.

それから,この問題では5種類のAIがランダムに選ばれるので,上位に入ろうとするならAIの特定と,それらに対して最適な行動ルールを設計すべきです.これには各AIの特性を見極めるとかソースコードをちゃんと読むなりしないと行けないので,とても大変そうです.考察力とか実装力が高まればその段階に進めると思いますが,今のところは難しいです.

ハイレベルな解法

simanさんのブログValGrowthさんのブログにわかりやすい解説がありますので是非ご参考に!

日記

以下,メモしていた日記を簡単にまとめておきました.あまり得るものはないです.

12/8(Thu)

午前2時開始と思い込んでいましたが,3時からでした.3時になると同時に登録して,いつも通りサンプルコードテスターのダウンロードを済ませました.その後「あーこれ系かー」と思いつつもよくわからず入眠.お昼にサンプルを動かそうとしてけれどもテスターが動かなくて困った.どうもファイルパスの問題っぽいのでフォーラムに質問したら修正版を用意してくれた.これで戦える!という感じだけど今日はこれで終わりっぽい.疲れた.

12/9(Fri)

方針を決める.とりあえずプレゼントを狙えば良い気がするので,プレゼントからグリッド外への最短ルートを調べることにする.しかしルートの途中に箱があると通れないので,箱を処理する部隊が必要.箱を持っていると他の箱を乗り越えられないため,ルートの歩数分だけ人数が必要になる.まあその辺はあとで考えるとして,各プレゼントを起点とした枠外へのルートを取得する部分から書き始めることにした.

12/10(Sat)

実装が結構大変な気がするので,まずはシンプルに箱とかプレゼントを拾ってくるコードを書くことにした.基本的なコードは書けたけど完成はせず.明日に持ち越し….

12/11(Sun)

いろいろと勘違いに気付く.

  • 箱やプレゼントがあるマスに移動すると自動的にそれを拾ってしまう(拾うかどうかを選択できると思ってた)
  • ターン毎の出力に改行を入れちゃダメ

修正したものをひとまず提出して70点くらい.まあそんなもんかな.seed1で1つもプレゼントが拾えてないので,まずはこれをどうにかする必要がある.プレゼントまであと1歩のところまで来ると目の前に箱が置かれるので,その時点でもう1人エルフを連れてくる必要がある.

12/12(Mon)

プレゼント毎にチームを作れば良いんじゃないかとか考えすぎて無駄なクラスを設計しまくった結果酷いコードが出来上がった.あまりに出来が悪すぎて最初の解答とさほど点が変わらずコード量だけが膨れ上がった.

12/13(Tue)

膨れ上がったコードにいろいろと機能を追加する.どんどん酷くなる.泣きそう😢

12/14(Wed)

書いたコードを全部捨てることを決断する.最低限やることをルールベースで書き直す.最終提出2時47分で前回に引き続いてまたギリギリ.大変疲れた.

感想

こうやって振り返るとかなり無駄な作業が多かったので,時間が無かったのではなく時間の使い方がとても悪かったということがわかりました.今回はテスターの不具合で早々に精神を削られたのでモチベーションの維持が結構大変でした.こういうゲームっぽいお題は結構好きな系統なんですが,その割には問題へのアプローチ方法が整理されておらず試行錯誤が多すぎるように感じたので,無駄な行動を減らすためにしっかり復習せねばと思いました.

競プロ日記009: ABC276

ABCのレーティング2022年11月6日現在

ABC参加8回目

ABC275は一度お休みして,AtCoder Beginner Contest 276に参加しました.ABCDの4問を解きました.E問題に目を通したのが残り10分ちょいでしたがマラソンマッチでよく書くタイプの問題だったので「いけるかも!」と思ったけど間に合いませんでした😢

解く順番をちょっと変えてみた

これまではA問題から解いていたんですが,データセットのダウンロードに時間がかかってしまったため待ち時間の間にB問題に目を通していました.そうすると頭の中がB問題になってしまったのでBACDという順番になりました.全体的な出来には対して影響しなかったけれども,無駄な待ち時間は数十秒くらい減ったので悪くないかも.C以降の問題も見た方が良いのかもしれない.

C問題: Previous Permutation

どうやらprev_permutationという関数があるらしいけど知らなかったので,真面目に考えました.数字列の後の部分が単調増加している区間を見つけて,そのひとつ前(単調増加が崩れている箇所)から並び変える感じですね.

9 8 6 5 10 3 1 2 4 7

という例なら,

3 1 2 4 7

という部分で,3と2を入れ替えて,

2 1 3 4 7

のようにして,2より後の部分を降順にソートします.

2 7 4 3 1

解説とかは見てないので想定解かどうかは知らない.

D問題: Divide by 2 or 3

結果的にそのまま実装すればよかっただけなのだけど,ここら辺までくると余計なことを考えて迷ってしまうことに気付きました.「本当にそれだけで良いの?何か高速に計算しないとダメ?」みたいな.大きいテストケースを想定したときの時間感覚が身についていなくてそういう思考になるのだろうなと思うので,やっぱり過去問等使って練習しないと早解きは難しそうですね.

3つ以上の数の最大公約数を求める方法がパッと思いつかなかったのでものすごくややこしい実装をしてしまいましたが,よく考えたら3つ以上でも順番に計算すれば良いだけでしたね.焦りは禁物.

E問題: Round Trip

これはマラソンマッチでめっちゃ書くタイプのグリッド問題なのでACしたかったところですが,時間切れ😢やっぱりスピードがネックだ…

競プロ日記008: MM141に参加しました!

MM141 seed 1

MM141

TopCoderマラソンマッチ(MM141)に参加しました.この日記を書いているのが10月28日で公式な結果はまだ出ていませんが,PROVISIONAL RANKは25位最終順位は23位でした.

今回からマラソン参加時に簡単な日記を書くようにしてみたので,今後の自分用と,これからマラソンマッチを始める人にとって少しでも参考になれば良いかなーと思って書き残しておきます.

10/20(Thu)

予定通り午前2時に起きてサンプルコードテスターのダウンロードを手早く済ませました.

不具合でページが消えたり一時的に閉鎖されることがあるかもしれないので,問題ページは念のためスクショ.

その後問題をちょっと読んで寝て,日中は普通に仕事をしました.適当に信号を切り替えるだけならすぐできますが,先々のこと(たぶんシミュレーションが必要)を考えて,最初の段階でできるだけ丁寧に書いておこうと,信号切り替え→実際に車を動かす→入力を取る→整合性チェックを厳しめにすることにしました.しかし仕事の後にコードを書いてみるものの眠すぎてめちゃくちゃなコードを書いてしまった結果,次の日の作業が無駄なデバッグ祭りになりました.眠いときはおとなしく寝た方がマシですね.とはいえ,最初にきちんとやっておくことはとても重要で,方向性は正しい(はず)です.

10/21(Fri)

前日に書いたコードを修正して動かしての繰り返し.バグは大体取れたはずなのにいくつかのケースでスコアが-1になってしまいました(assert入れまくってるので異常終了). ビジュアライザで見てみたら,

MM141初期のテスター
ナニコレ😰…とかなり焦ったのだけど,これ(道がつながっている)は明らかにテストケースがおかしいんじゃないかと思ってフォーラムを確認してみたら修正版のテスターが公開されていました.初日に張り切ってテスターをダウンロードしたのは良いけど,初期のバージョンは修正が入るかもしれないので注意しないとですね….その後テスターを差し替えて1000ケースほど試したらすべて正のスコアが得られたので,満足して就寝.この日はおしまい.

10/22(Sat)

最低限の実装を一通り終えて提出するとスコアは78点くらいで12位,悪くなさそうです.いくらか点は上がるビジョンがあるので安心してこの日の業務を行うことができました.この時点では,グリッド上にあるすべての車について,とにかく前に進むだけです.信号に引っかかって動けなくなれば信号を切り替えるというだけ.それでもそこそこのスコアが出るので,これってめっちゃいい感じじゃね?と思ったもののそこからスコアを挙げる方法がよくわからず.とりあえず前に進める車に優先順位を与えることから取り掛かろうと日曜日の方針を決めて寝ることにしました.

10/23(Sun)

比較的時間はあるので,家族とのんびり過ごしながら何か思いついたら実装して確認というのを何度も繰り返していました.しかしいろいろやっても推定1~2点くらいしか上がらなさそうなので,100ケースくらいをビジュアライザでチェックしたところ,

グリッドロック
見事に詰まっていますね!まあ何の対策もしていないのでそりゃそうか,ということで進んださらに1マス前に他の車がいる(あるいは来る)場合は一旦停止することにしました.
ちょっと待つ
これで幾分マシになりましたが根本的な問題は解決せず.かといって賢いアイデアもないので,1マス先だけじゃなく2マス先も見るようにしてみました.
余裕を持たせて待つ
これでもう少しスコアが上がったので一旦提出すると87点くらい.まあよしということでこの日は終わり.

10/24(Mon)

朝から予定が詰まっていてほとんどノータッチでしたが,いくつかのseedで極端に点が低いことがわかったので残りの時間はグリッドロック対策を行うことに絞り込みました.

10/25(Tue)

調査の結果,やはり早い段階でグリッドロックしていることが確認できました.まずはグリッドロックを検出できるようにしなければいけないということで,それだけ頑張りました.

夜中まで頑張って,「次のターンでグリッドロックが発生するよ!」というのを見つける処理を実装できました.この状態になったら上手く調整して渋滞を回避しないといけないのだけど,残り時間を考えるとバグらせずに組み上げる自信がなかったので,渋滞に関与している車をランダムに停車させて渋滞を回避できるかを何回か(10回)試してみる処理にしました.完全に渋滞を防げるわけではないけどだいぶマシになりました.これで最終日に時間がなくても提出できる状態までもっていけそう!

10/26(Wed)

最終日.普段は高速化とかパラメータの調整くらいしかできそうなことがないけど,今回は割と実装げーな感じでやることが無限にある感じでいつもと違う充実感がありました.残り時間と相談しつつ,できそうなことだけ進める.この日やったのは,まだ動く余地があるのに止まってしまうことをできるだけなくすように,取り除けそうな条件式を取ってはバグって取ってはバグって,じんわりスコアアップしていきました.渋滞が発生したら一時的に車を出現をブロックする処理を加えてみたら,渋滞が起こりやすいケースではある程度機能するもののそうでない場合はスコアが下がってしまってトータルではそんな感じだったので,無理やりコントロールするのは断念しました.

23時くらいに完成して提出し,お疲れ様でしたーと終わるつもりだったのですが,不要なコードを削除していたら削除前とスコアが変わってしまったので,絶対バグあるやんこれ😱」ということで泣きながらデバッグしました.で,提出できたのが1時57分と超ギリギリ.まあ何とか間に合いました.スコアが1.5点くらい増えたので,もしかしたら2~3ケースWAを出していたのかも.

というわけで,やりたいことがすべて実現できたわけではないけれども何とか形にできました.

やりたかったこと

もう少し時間があったら,1つ先のターンだけでなく複数ターン先をシミュレートしてみてよりスコアの上がりそうな選択をする処理を加えたかったです.2~3ターン先読みするだけでも結構変わる気がするので,そこが心残りではありますが,まだまだ実力不足ということで次に向けて頑張ろうと思います.

競プロ日記007: ABC274も終わったしマラソンマッチをやるのだ!

ABCのレーティング2022年10月23日現在

ABC参加7回目

キーエンスプログラミングコンテスト2022(ABC274)に参加しました.ABCDの4問を解きました.D問題を提出したのが終了2分前くらいだったので後は何もできず….ACした時間を見返してみると

[A]21:09:05
[B]21:13:20
[C]22:01:36
[D]22:38:04

Aでもたつきすぎなのと,Cで時間かかりすぎでした.Aは四捨五入か面倒やな…と思っていろいろと調べたりもがもがしてましたが,結局のところPython3なら

print(f'{B/A:.3f}')

で通るんですね…😅しかし.3fのところを.3gと書いていて0埋めする方法を3分くらい調べてました.これホンマに2問くらいしか解けないんじゃないかと思ってきましたが,Bは特に迷う要素もなくすんなり通ったのでちょっと持ちこたえました.

しかしCで大幅なロス.問題の意味が全然わからなくて,とりあえずサンプルで入出力が一致するコードを提出してWAを得るということを複数繰り返すことでなんとか通りました.明らかに集中力がなくなってきて,通った時点で諦めようかと思ったのですが,一応D問題も目を通しておこうと開いてみるとできそうだったのでやってみて,終了間際になんとかAC.

振り返ってみると,「わかるぞ!」と思っても37分くらいかかっていてとても遅いので,C・Dの過去問で練習しないと成績は安定しなさそうです.ちょっとずつやっていこかな.

MM141

マラソンマッチ(MM141)が始まってます! これに関してはまだ途中なので書けることがないですが,今回から日記をつけるようにしたので次回の日記にまとめを書こうかなと思っています.現在37人中20位で,これからもうちょっと頑張ろうと思います.まだ参加していない人はぜひご参加を!!!

競プロ日記006: 今日も割とやらかす

ABCのレーティング2022年10月16日現在

ABC参加6回目

パナソニックグループプログラミングコンテスト2022(ABC273)に参加しました.ABCの3問を解いて,Dを愚直な方法で書いたあとTLEにならずにREになった1ので,なんでやろーと思っている間に時間切れでした.前回までの結果から,テストデータの用意とかスムーズな提出を行うためにいろいろと準備はしていたのですが,新しい環境にした結果余計にもたついてさらに提出が遅れるという事態になりました….まあ何回か参加していれば徐々に慣れるはずなので,あまり気にせずやっていきたいと思います.

前回からの変更点

この記事を参考にしてatcoder-clionline-judge-toolsを導入し,コマンドラインでいろいろとやりくりできる環境にしました.

「これでバッチリじゃろ~」と思ってたのですが,いざ始まってみると

  • 事前のログインを忘れて焦る

  • acc new abc273した後,何故かぼーっと待ってしまう

  • 提出したつもりでできていなかった

というアホみたいなミスをしてしまって,結局最初の5分くらいはワタワタして余計に遅くなってしまいました….

事前のログインを忘れて焦る

過去問で練習したときにログインしていたので大丈夫かなーと思っていたのですが,再度ログインが必要な状態になっていて,「なんかダウンロード遅いな」と思ってたらidとパスワード入れなはれ的なメッセージが出ていてまず慌てました.1アホ

テストデータの取得時にぼーっとしてしまう

テストデータを自動でダウンロードしている間に問題を読んでスピーディに解答する予定だったはずが,進行状況をただぼーっと見つめるだけになっていました.おそらく1アホのときにかなり動揺したこともあるかな?2アホ

提出したつもりでできていなかった
acc submit src

で簡単に提出できるので超楽チンになりましたが,実際にやってみると(たとえばD問題だと)

[WARNING] the problem "https://atcoder.jp/contests/abc273/tasks/abc273_d" is specified to submit, but no samples were downloaded in this directory. this may be mis-operation
Are you sure? Please type "abcd"

みたいな警告が出て,さらに指定された文字列を入力する必要があります.これは事前に確認していたものの,いざコンテストが始まるとそれを忘れてしまっていて,しばらくぼーっとするというのを何度となくやってしまいました.あまりにも注意散漫です.3アホ

まあそんなこともあって,いつもと大して変わらなかったような.やっぱり単純に過去問をやって慣れていくしかないですね.

二分探索

毎回のように二分探索が必要な問題が出ている気がして,毎回同じようにbsearch→いや違う→binary_search→これじゃあ要素が特定できないやん→upper_boundとlower_boundどう違うんだっけ??と調べて2,毎回結構な時間をロスしているので,ちゃんと覚えておくとかコードスニペットに登録しておくとかせねばならんと思いました.

次回に向けて

過去問を少しずつやりたいと思いつつ,今週はMM141が始まるし仕事がどんどん溜まってきているので,当面はAとかBくらいの短時間でできそうなものに限定して練習をしようかなと思っています.


  1. グリッド用のメモリを確保しようとして失敗してたっぽい.障害物の情報だけをリストにしたら大丈夫でした.

  2. そして毎回https://qiita.com/ganyariya/items/33f1326154b85db465c3を見る^^;