競プロでWAが出たときのランダム入力データ生成入門 - ARMERIA
概要 競技プログラミングで提出コードがWAになったとき、実際に不正解となるような入力データを入手できると役に立つ場合があります。ただ多くのコンテストサイトでは、コンテスト中には入力データを見ることはできません。 そのような時に、小さめの入力データを乱数で大量生成して、提出コードと愚直解法の結果を突き合わせ、答えが一致しないものを探すという方法があります。もちろんそのようなデータを確実に得られる保証はありませんが、もし見つかればデバッグの大きな助けになります。 今回の記事はその手順を紹介します。また、生成コードの例としてC++とPythonを扱います。 手順1：愚直解法コード作成 まずは問題に対する愚直解法のコードを書きます。小さな入力データで回すので、 だろうと だろうと気にせず書きましょう。これがバグっていると破綻するので計算量よりも正しさ優先です。 C++等の場合はコンパイル時に提出コ
競技プログラマのための抽象セグメント木実装のすすめ - beet's soil
午前起床！（素振り） はじめに 先にこっちを見て beet-aizu.hatenablog.com うし木（一点更新区間取得）について書きます おまけ なんだこれはたまげたなあ（わかる人にはわかる記事、わからない人にはわからない） beet-aizu.hatenablog.com 前提知識(C++) 厳密性や歴史的背景をガン無視しています。あんまりあてにしないでください。 雰囲気を掴むためと割り切って読んでもらえるといいと思います。 C++のバージョンは14を前提にしていますがそのうち17に上がりそう？ struct is 何 競技プログラマならpairやtupleくらいは使ったことがあると思いますが、自分でそういうのを作るための機能です。 たとえば struct Node{ int fi,se; }; Node v; v.fi=0;v.se=1; みたいな感じで使えます。 つまり、大きな
動的計画法によるDVDのディスク分割の改善
こんにちは。「家族アルバム みてね」の開発チームに所属している黒川と申します。今回は、その「みてね」の機能の1つで、写真や動画をDVDにして注文できる機能を動的計画法を使って改善した話をします。 「みてね」では家族の写真や動画をアップロードし、アプリ上で月ごとに振り返ることが可能になっています。一方、たとえば自宅のテレビやパソコンでまとめて振り返りたいという要望もあり、「みてね」では最長過去1年間の写真や動画をDVDにまとめて注文することができます。 このときに問題となるのがDVDのディスク分割です。1年分の写真や動画はともすると1枚のディスクに収まりきらず、複数のディスクに分割する必要があります。いままでは、動画を月ごとに分けて各ディスクに入れていく、というシンプルなアルゴリズムで分割を行っていました。しかし、ユーザーさんからは「1枚のディスクにすこしの動画しかないがどうなっているのか」
典型データ構造まとめ - beet's soil
なんか前回伸びたので 参考 hamayanhamayan.hatenablog.jp ei1333's page 宣伝 beet-aizu.hatenablog.com 以下とりあえず辞書順（そのうち典型度順にしたい） Binary Indexed Tree 一点加算、先頭からの区間和、k番目に大きい値が で可能 library/binaryindexedtree.cpp at master · beet-aizu/library · GitHub 容易に多次元に拡張が可能（実用上は2次元くらい？ library/binaryindexedtree2D.cpp at master · beet-aizu/library · GitHub Binary Trie 二進数を管理するTrie木 全体にXOR、k番目に大きい値、lower_bound等が で可能 library/binarytri
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
