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:
AtCoder Clans
Home Home Quick Start For Beginners Recommendation Web Apps and Sites Scripts Articles, Blogs, Books and Videos Libraries and Snippets Command Line Tools Milestones Related Contest Sites Archives Privacy Policy Contact Special Thanks Contributing License Change Log AtCoder Clans 【非公式】競技プログラミングサイトAtCoderがもっと楽しくなるリンク集です。有志による非公式サービス・ツール・ライブラリ・記事などをまとめています。 特長 網羅性が高い: 初心者から上級者向けの情報まで幅広く掲載しています。 最新: 最
競技プログラミングに関係する数学の整理 ～文系出身や数学苦手erが、もっと競プロを楽しむために～ - テルの競プロメモ
まえがき この記事の目的 意図する対象読者 今回の整理の仕方（記事の見方） 注意 競プロに関係する数学（本題） 言葉（文系でも多分聞いたことはある）編 言葉（文系だと聞いたことないかも）編 言葉（離散数学）編 「式変形」編 「図形っぽいやつ」編 筆者のバックグラウンド 経歴、仕事など まえがき この記事では、競技プログラミングに関係する数学用語・概念と、それがどんな単元（分野）に属するものかを整理（一覧化）します。 競技プログラミングの問題に出てくる用語・概念をはじめ、競技プログラミングの解説記事などに出てくる用語・概念も、思いつく限り挙げています。 「この記事の数学的な部分、どのぐらい信用できるの？」とか、「数学苦手と言ってもどのくらい苦手なの？」といった疑問への参考としては、筆者のバックグラウンドを記事の最後で紹介したので、気になる方は先にそちらを読んでください。 この記事の目的 文系
競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック
競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)
2020競プロスラング用語集 - kaage精進録
2020最新版競プロスラング用語集です。 「FFの競プロerが意味不明な単語を叫んでいてわからない！」 「界隈用語で溢れていて入っていけない！」という方、必見です。 ちょっと内輪ネタが入っているかもしれませんが、競プロ用語は全部内輪ネタみたいなものなので、よしとしましょう。 これであなたも競プロ界隈の仲間入りです。 色 AtCoder, Codeforces, TopCoderなどのコンテストでは、参加者に「レーティング」とそれに応じた「色」がつけられ、実力の指標になります。 サイトによって色は多少異なりますが、どのサイトでも赤が一番強く、「赤コーダー」になることは人々の夢です。 コンテスト プログラミングコンテストに参加することは、競プロerのライフワークです。 競プロ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
AtCoderでの競技プログラミングがもっと楽しくなるサイトまとめ - NoiminのNoise
この記事は情報系を勉強する女子大生 Advent Calender 2017の16日目の記事です． qiita.com 16日目担当のNoiminです． 情報系学科の学部4年で，自然言語処理の研究室に所属しています(自然言語処理は本アドベントカレンダーでもasai0304さんが取り上げてくださっていますね)． 去年から趣味として競技プログラミングをかじっています．実力はまだまだですが楽しくやっています． 今日はその競技プログラミングを話題にしたいと思います． 競技プログラミング/AtCoderとは 各サイト紹介 AtCoder Problems AtCoder Scores AtCoder Rating Estimator AtCoderRatingGraphComparison AtCoder Stats Rating History AtCoder Finder AtCoder Rat
競プロ解法紹介～レベル別マラソンの戦い方～ - Qiita
2018年02月18日（8時間）に開かれたマラソン形式の競技プログラミングコンテスト、Hack To The Future 予選問題について、マラソン初心者からマラソンイエローコーダー以下までのレベル別の戦い方紹介です。 問題概要「 山型足し算」※原文引用 N 行 N 列のマス目 A が与えられます。一番左上のマスの位置を (0,0) と定義します。 このとき、左上のマスから下に i (0≦i≦N−1) マス、右に j (0≦j≦N−1) マス進んだマスの位置は (j,i) で表されます。 また，各マスに整数が書かれており、位置 (j,i) のマスに書かれている整数を Ai,j で表します。 ここで、マス目に対して全てのマスに書かれている整数が 0 である状態を「初期マス目」と定義します。 また、マス目 P に対する「山型足し算」 (X,Y,H) を以下のように定義します。 まず，山の中心
Digit DP 入門 - torus711 のアレ
はじめに 動的計画法のパターンの一つで，「Digit DP」とか「桁 DP」と呼ばれているものがあります．問題によって異なってくる部分もありますが，問題によらず共通している部分がかなりあるので，その部分を中心に解説してみたいと思います． Digit DP とは？ 「ある整数 以下の非負整数であって，ある条件を満たすものの個数を求めよ」といったタイプの数え上げ問題を解くときにしばしば使われる手法です．Digit DP は，整数の各桁に入る値を 1 桁ずつ決めていくという全探索を DP 化したものです．「ある条件」の部分はとりあえず置いておいて，「 以下の非負整数を数える」というのを例にしてみようと思います．答えは当然 ですが，これを Digit DP で求めることで Digit DP の本質的なアイデアが見えてくると思います．また，求める整数は 10 進表記であるとします． Digit DP
競プロにおける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日目の記事です。 最近は、簡単にやるべきことでも、難しくやってしまうことが多く、それがマラソンマッチでの不振につながってるので、「簡単な解法」をネタに書きます。 昔、自分でこう言ってました。 敗因：誰でも思いつくようなケースをほとんど試さなかった。 特に、時間がかからずに実装できるものは、絶対試したほうがいいです。仮に全然結果がでなかったとしても、その後のヒントになる可能性もありますし、条件によっては使えるかもしれません。今回、自分の考えたのは実装時間がかかるため、それが外れ方針なのに気づくのに時間がかかってしまいました。 はい、その通りです。でも、その最初に作りたい簡単な解法が、年々思いつかなくなってきているので、復習しようと思います。マラソンマッチ初
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのブログ
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。 そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと) ※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。 随時追加更新します ・(10/10 04:31) ワーシャルフロイド法を使うのが適切そうな2題追加 ・(10/10 04:33) 深さ優先探索が寂しかったので1題追加 ・(10/10 04:??) 最小全域木が寂しかったので2題追加 ・(10/24) 深さ優先探索っぽいの追加(幅優先でもよい問題だが) 深さ優先探索 ・Ball[☆](効率的な別解もあり) ・Sum of Integers[☆] ・The Number of Island[☆] ・Block[★] ・Sergeant Rian[★★☆] ・Proper
競技プログラマのための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 に入れる。 コンテスト
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
atcoder初心者こそ環境構築しよう！(atcoder-cli,online-judge-toolsのインストール、使い方） - Qiita
http://www.graco.c.u-tokyo.ac.jp/icpc-challenge/wp-content/uploads/2014/12/2014.pdf