競技プログラミングは役に立つ、 というかアルゴリズムとデータ構造は身の回りで役に立ってるよ案件なんですが、 バージョン管理システム Git のコア部分の仕組みは永続データ構造です。 ブラックボックスとして使うより簡単な仕組みを知ってる方が 親しみや…

前書き 全点対最短経路問題 (APSP : All Pair Shortest Path) を解くアルゴリズムを 4 つ紹介します。 $V$ 頂点 $E$ 辺の非負重み有向グラフ $G$ を考えます。 負の重みがあるときは一回 Bellman-Ford か何かを使ってポテンシャルを計算すれば非負に直せると…

CodinGame / コドゲ というゲームAIを作って戦わせるコンペを定期的に開いているウェブサイトがあります。 この記事の執筆時点では Spring Challenge 2021 が開催中です。 コドゲはかなりリッチなサイトで、ブラウザ上のエディタで実装してテスト対戦実行・…

完全に理解しても今ではもう捻くれた応用問題しか出ないので 今後解けるとは言っていないです。 数弱なのでガバってると思うけど雰囲気で察してください。 参考資料 書き終えてから見つけたけど、この記事の内容大体ここに書いてあった気がする。 再発明万歳…

対戦型ゲームAIのオンラインコンペティションサイト CodinGame で開催された CodinGame Fall Challenge 2020 に最後2日間ぐらい参加しました。 省エネで Gold まで上がれたらいいなーと参加してたけど力及ばず Silver League 止まりで終了でした。 (最高で S…

前書き ゆるふわ競技プログラマです。 koyumeishi というアカウントで色々参加させてもらっています。 この記事の執筆時点 (2018/12/28 05:00 AM JST) ではまだ結果が出ていませんが、 先日 topcoder で開催された MM105 でマラソンマッチ(MM)のレッドコーダ…

日本橋ハーフマラソン本戦B 日本橋大渋滞 解説 先日 RCO が主催したプログラミングコンテスト 日本橋ハーフマラソン のオープンコンテストに参加しました。 オープン参加で賞金もレートもかかっていなかったのでA問題は放棄して、 ビジュアライザが用意され…

競技プログラミングのいわゆるアルゴリズム部門のコンテストは数時間の間に数問を解く形式のものが多いです。 例えば topcoder SRM は1時間15分で3問、 codeforces は2時間で5問出題されます。 しかし最近は数日から数週間に及ぶ長期間コンテストが増えてき…

template は再帰的に展開されるので工夫次第で色々できます。 出来るってだけで実用的かどうかは知りません。 自分が使っていたり、思いついたりした std::vector 操作テクを紹介します。 C++11です。 GCCです。 目次 vector の 入力を簡単に vector の 出力…

なんだかよくわからないタイトルでごめんなさい。こういうのなんて言ったらいいんだろうか。 先日の Facebook Hacker Cup 2016 Round2 C でそんなテクが要求されて解けなかったので自分用メモ書き。 教えて下さった@kyuridenamidaさんに感謝。 @koyumeishi_ …