key指定でtuple配列のsortを高速化 - Qiita
はじめに 競プロ精進中に「計算量的には間に合いそうなのにTLEする...」と悩んでいたところ、前準備のsort部分がボトルネックになっていたと発覚。 ハマったポイントを共有します。 tupleの配列のsort key指定あり/なしの違いについて、簡潔に説明します。 key指定あり a = [(3,3), (2,2), (3,1), (4,2)] a.sort(key=lambda x: x[0]) print(a) # => [(2, 2), (3, 3), (3, 1), (4, 2)] 指定したkeyの大小によって、sortを行います。keyの要素が等しければ、その順序は保持されます。 sort() メソッドは安定していることが保証されています。ソートは、等しい要素の相対順序が変更されないことが保証されていれば、安定しています。（公式ドキュメント） sort(key=lambda x:
競技プログラミングに関係する数学の整理 ～文系出身や数学苦手erが、もっと競プロを楽しむために～ - テルの競プロメモ
まえがき この記事の目的 意図する対象読者 今回の整理の仕方（記事の見方） 注意 競プロに関係する数学（本題） 言葉（文系でも多分聞いたことはある）編 言葉（文系だと聞いたことないかも）編 言葉（離散数学）編 「式変形」編 「図形っぽいやつ」編 筆者のバックグラウンド 経歴、仕事など まえがき この記事では、競技プログラミングに関係する数学用語・概念と、それがどんな単元（分野）に属するものかを整理（一覧化）します。 競技プログラミングの問題に出てくる用語・概念をはじめ、競技プログラミングの解説記事などに出てくる用語・概念も、思いつく限り挙げています。 「この記事の数学的な部分、どのぐらい信用できるの？」とか、「数学苦手と言ってもどのくらい苦手なの？」といった疑問への参考としては、筆者のバックグラウンドを記事の最後で紹介したので、気になる方は先にそちらを読んでください。 この記事の目的 文系
競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック
競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)
競プロライブラリのためのソフトウェアライセンスについて - うさぎ小屋
対象読者: 自分の書いた競プロ用ライブラリ1を公開している人2 注意: 法律の専門家でない人間が書いています。内容については保証しません 言いたいこと: 「意味をよく分かってないままとりあえずで MIT License とか書くのやめろ。それなら何も書かない方がましだぞ」 Q. ソフトウェアライセンスとは何ですか？ A. 開発者からユーザに対する、「そのソフトウェアを使ってもよい」という許可のことです。 Q. ライセンスがないソフトウェアを使ってはいけないのですか？ A. はい。 「ソフトウェアは著作物であり」かつ「他人の著作物を勝手に使ってはいけない」ことから、「他人の書いたソフトウェアを勝手に使ってはいけない」のは明らかです。 ただし、ライセンスについての表示がないとしても、開発者がソフトウェアを他人に使ってもらう意図で公開している場合は、それを使ったとしても問題は起きにくいでしょう。
多重vectorを可変引数テンプレートで - beet's soil
vector<vector<vector<...... > > > > >みたいなのを再帰的に定義させてほしい— beet (@beet_aizu) 2018年4月8日 vector<vector<...>> みたいなのは普通に Variadic Templates で作れるけどそれだとダメなのかな— すいばか (@suibaka_ku) 2018年4月8日 https://t.co/tUwRlZkjIq— すいばか (@suibaka_ku) 2018年4月8日 すいばか さんに圧倒的感謝🙏🙏😭🙏🙏 以下C++ のコード すいばかさん版：型は最後の引数で決まる template<typename T> vector<T> make_v(size_t a,T b){return vector<T>(a,b);} template<typename... Ts> auto make
競プロ初心者だった頃の注意すべき点を列挙する 1 - ヘクトのメモ
背景 ここ最近になって競プロを始めて、毎週プログラミングコンテストに参加する人が増えていると感じます。*1 特に日本語で提供される初心者向けコンテスト AtCoder Beginner Contest (ABC) に参加する人が多いです。各ABCに対して解説pdfと配信動画が公式に用意されていますが、実装で苦戦している人が多いように思えます。 今回の一連の記事では、無意識にやっているようなレベルの実装上のテクニックをあぶりだす為に、自分が競プロを始めた頃の提出コード*2をもとに難所を列挙していきます。ここでの対象読者層は、1問でも解いた人からAtCoder上での緑色くらいまでを想定しています。 以下の記事よりもかなり細かいレベルで書いていきます。 初心者向けのABCの問題傾向とその対策 - ヘクトのメモ この記事の要約 競プロ初心者かつコンテストパフォーマンスを上げたい人への典型tips集
My strategy at AtCoder & CS Academy - Codeforces
There's been much controversy lately about the late submission strategy not penalized by scoring systems of AtCoder and CS Academy. Most of the relevant discussion happened earlier at http://codeforces.com/blog/entry/53431 and http://codeforces.com/blog/entry/53449. I have a lot of thoughts on the topic, so I've decided to share them in a separate blog post. I really like the strategic part of pro
競プロにおけるNim、Grundy数とNimK - かっさのなにか
この記事は、 「競プロ!!」 競技プログラミング Advent Calendar 2017 21日目 の記事です。 昨日は DEGwer さんの「数え上げテクニック集」でした。まだ全部読んでないけど凄かったです。 こっちでも同時に競プロのアドベントカレンダーが進められています。 Nim,grundy数がわかっていると、盤面を共有して二人で対戦し、勝敗が必ず決するタイプのゲーム問題がわりとサクッと解けます。 最近では 5日前、2017/12/16 の Atcoder Regular Contest 087 E で Grundy数の問題が出ました。 この記事の本題はNimの拡張されたゲーム、NimKの話です。 導入として、Nimとかgrundy数を知らないひとにもわかるようにスライドを作成しました。 絵を描くだけのつもりだったのにスライドになってしまいました。 適当すぎてわからん！と思うひとも
マラソンマッチの簡単な解法 - じじいのプログラミング
まえがき この記事は、Competitive Programming Advent Calendar 2017 - Adventar 18日目の記事です。 最近は、簡単にやるべきことでも、難しくやってしまうことが多く、それがマラソンマッチでの不振につながってるので、「簡単な解法」をネタに書きます。 昔、自分でこう言ってました。 敗因：誰でも思いつくようなケースをほとんど試さなかった。 特に、時間がかからずに実装できるものは、絶対試したほうがいいです。仮に全然結果がでなかったとしても、その後のヒントになる可能性もありますし、条件によっては使えるかもしれません。今回、自分の考えたのは実装時間がかかるため、それが外れ方針なのに気づくのに時間がかかってしまいました。 はい、その通りです。でも、その最初に作りたい簡単な解法が、年々思いつかなくなってきているので、復習しようと思います。マラソンマッチ初
競技プログラマのためのC++ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
この記事はCompetitive Programming Advent Calendar 2015の６日目の記事として書かれました。 この記事は、C++初心者が頑張って編み出した、C++初心者の競技プログラマ向けの実装テクニックを紹介するものです。 筆者自身がC++に詳しいわけではないため、仕組み等の解説は避け、「こう書けばいい感じに動くよ」みたいな部分だけを書いていきます。 「競プロでの応用例」という点に注目して読んでいただければと思います。 目次 ・range-based for（前菜） ・lambda式（メイン） ・コメントアウトの小技（おまけ） まずは、C++11の新機能を使ったテクニックから紹介します。 range-based for これはよく知られていると思います。以下のように書くとvectorとかmapとかを舐められるやつです。 for (型 変数名 : 舐める対象) 使用
競技プログラマの名前で呼ばれるアルゴリズムたち - HackMD
# 競技プログラマの名前で呼ばれるアルゴリズムたち [競技プログラミング Advent Calendar 2017](https://adventar.org/calendars/2221) Day
AtCoder Problems を支える技術 - 宇宙ツイッタラーXの憂鬱
adventar.org はじめに AtCoder Problems というサービスを作っています。最近作り直しています。 http://beta.kenkoooo.com/atcoder/ これは AtCoder の提出を全部クロールして、一覧で見れるようにしたものです。最近は機能が増えすぎていますが・・・ ソースコードも公開しています。このプログラムの中でどんなことをしているのかを書いていきたいと思います。競技プログラミングはそんなに関係ないです。 github.com スクレイパー Scala で書いています。ScalaScraper でクロールもスクレイピングもやってくれるので、それに任せています。 やっていることは以下のとおりです。 コンテスト一覧をクロールして DB に入れる。 DB のコンテストを順番に見ていき、そのコンテストの問題をクロールして DB に入れる。 コンテスト
競技プログラミング練習問題集 - はまやんはまやんはまやん
他 競技プログラミングにおける細かな話題まとめ - はまやんはまやんはまやん DEGwerさんの数え上げテクニック集問題まとめ - はまやんはまやんはまやん セグメントツリーにセグメントツリーを乗せる手法（2Dセグメントツリー） - はまやんはまやんはまやん HackerRank Game Theory の勧め - はまやんはまやんはまやん Educational DP Contestの勧め - はまやんはまやんはまやん 今年中に理解する！多項式、母関数、形式的べき級数の競プロでの実践的使い方 - はまやんはまやんはまやん パソコン甲子園 プログラミング部門 解説まとめ - はまやんはまやんはまやん 日本情報オリンピック 解説まとめ - はまやんはまやんはまやん アルゴリズム実技検定解説まとめ - はまやんはまやんはまやん フロー 競技プログラミングにおける最小費用流問題まとめ - はまや
競プロ用語 - 幸せに
twitter上の競プロerの文化や，erが使っている用語を紹介しようと思います。 ・色 競プロのコンテストに出場すると，成績に応じてレートが変動します。レートは色分けされています。 例えばatcoderでは 色 レート 自由色 3200以上 赤 2800以上 オレンジ 2400以上 黄色 2000以上 青 1600以上 水色 1200以上 緑 800以上 茶色 400以上 灰色 0以上 と色分けされています。サイトによって少しずつ違いますが，どのサイトでも赤が一番強いというのは共通しているようです。 「○○コーダー」というのはこの色を指します。例えばレートが2000以上2400未満の人を「黄コーダー」と呼びます。 twitterのアイコンを自分の色に合わせておくと，どのくらい強いのか見た人がすぐに分かるので便利です。 赤コーダーの人が自分のtwitterアイコンをあえて灰色にすると，ハラ
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
複素数演算による幾何ライブラリの実装 - ヘクトのメモ
この記事はMCC Advent Calendar 2016 15日目の記事です．ICPC向けの複素数演算による幾何ライブラリの実装について話します． MCC Advent Calendar 2016 - Adventar 遅れてすいません... 背景 ICPCでは幾何の問題が出てきます． ただし，ICPCでは電子的な事前準備の禁止と標準ライブラリしか使えない制約があります． このため，標準ライブラリ縛りで幾何に必要な関数を一から実装する必要があります． しかし，事前準備なしで幾何に必要な関数を実装するのは大変なことであり，多くのチームは紙媒体でライブラリを用意していると思います． 幾何に必要な関数を一から実装するとコード量も膨大になりがちです． そこで，複素数演算を活用することで実装量を減らすことができます． (ただし，2D限定です．あと，事実だけを淡々と書いていきます．) ベクトル 2次
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.graco.c.u-tokyo.ac.jp/icpc-challenge/wp-content/uploads/2014/12/2014.pdf
https://www.cses.fi/book.pdf
高度合成数一覧 - ペケンペイのブログ