競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)

今回も前回に引き続きD問題が700点という、ABCには厳しい回でした… 結果は3完79分で30位…一気に黄色になりました！びっくりですね。highestパフォ400くらい更新しました。 黄色になりました記事は別途書きます。この記事ではC～E問題を振り返っていきます。 C - Triangular Relationship C - Triangular Relationship 解法 について、 が全て の倍数でなければいけません。数値が3つあると考えにくいので、まずは1つにできないか考えましょう。 から だけの式を作ることを考えます。 を計算すると結果は になって、 だけの式になります。 この値は の倍数3つを足し引きしているものなので、やっぱり の倍数です。つまり、 が の倍数であるということが言えます。ここから、 が偶数の場合、 は で割った余りが または でないといけない が奇数の場

はじめに --- DP は役に立つ はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 巷ではよく「DP なんて実務では使わない」といった言説が定期的に流れますが、そんなことはないです。僕自身この 2 年間で DP が使える実務案件に 3 件くらい関わりました！ それはともかくとして、DP を学び立ての方がよく抱く悩みとして「バリエーションが多すぎて混乱するし、統一的なフレームワークがほしい」というのがあります。確かに DP のバリエーションは非常に多岐にわたるのですが、そのほとんどが以下の 3 つのフレームワークで説明できると思います: ナップサック DP 区間 DP bit DP 今回はこのうちのナップサック DP について、とにかく

自己紹介 現在豊田高専の5年情報工学科に所属してます。 来年から豊橋にある某技科大に進学します。 高専3年のタイミングで運動部を辞めてコン部に入り、パソコン甲子園で競プロに目覚めました。 AtCoder水(応募時はHighest水の緑コーダーでした) 激冷えしてるやんけ... 大学に進学するにあたってバイト探さねぇとな～～～～～と思ってました。 あと卒業研究で深層学習を使って自然言語処理っぽいことをしたりしてました。 卒論書けた！(17時〆とは) 卒業させてくれ頼む頼む頼む頼む頼む頼む頼む頼む頼む頼む頼む頼む頼む頼む頼む頼む頼む頼む頼む頼む頼む pic.twitter.com/qBV4aXxUrt— 𝐓‌𝐓 (@TT_beginner) 2020年2月21日 https://twitter.com/TT_beginner/status/1234438002190868482 応募の経緯

この記事の目的AtCoder緑で停滞する著者が停滞期を脱却するために、過去に水色になった方のブログを見てこれからの精進手法を見つめ直すこと はじめにAtCoderで競技プログラミングのコンテストに参加している@tokizoです。 一昨年の4月にAtCoder緑になったきり、未だに水色になれていません。 なぜ停滞するのか、偉人が残した「水色になったブログ」と自分を比較して考えてみます。 今回は第1回目です。（続くの！？） 比較するに当たり、下記の項目を重点的に見ていきます。 ・水色になるまで勉強したアルゴリズム ・精進の仕方 ・スランプの脱出手法（スランプがあれば）まず、自分のことを振り返ります。 今まで勉強したアルゴリズムについて まず、自分のスキルセットを洗い出します。 過去にcp-categorize betaという、様々な競技プログラミングコンテストサイトで解いた問題をカテゴリー別に

セグ木がソラで書けなかったらセグ木に何か生やす問題とか解けない— つたじろう@帰省 (@_TTJR_) March 29, 2017 セグ木にいろいろ生やす問題がてんで解けない私なので、セグ木に慣れようと思い立ちました。そのためにはまずセグ木をもっと知らねばならないと思ったので、ソラで書けないか色々やっていました。 やってくうちにコツを掴んでソラで書けるようになってきたので、忘れないためにも記事を書くことにしました。ということで、何も見ずにセグ木を書くために押さえておきたいポイントを紹介していきます。 注意 この記事は、「セグ木がどんな形をしているかはわかるけど、実装はできない・・・」という方向けで、遅延評価が不要な、区間最小の基本的なセグメント木のみ扱っています。 そもそもセグ木って何という人は他記事を参考にしてください。 おすすめは iwiwi さんのスライド → プログラミングコンテ

Shared with Dropbox

少し比較するコンテストが悪いような感じはしますが，同じ600点でもパフォーマンスに大きな差があることがわかります． 本記事ではいかにして問題を早く解くのか，テクニック （アルゴリズム） を10個ほど紹介したいと思います． スニペット(ライブラリ)作成テクニック 多くのテキストエディタ(VScode, Atom, Emacsなど)には「スニペット」という機能があります． この機能を使うと，あらかじめ書いておいたコードを，画面に瞬時に表示させることができます． 例えばVSCodeの場合はこちらのサイトを参考にすると登録することができます． 他のエディタを使用されている方は「(ここにエディタ名)　スニペット」とかで検索🔍すると簡単にヒットします！ 以降，スニペットに登録しておくと便利なアルゴリズムを紹介します． (注意: 紹介しているAtCoderの問題はちょっと難しいかもしれません．これは検

2. 内容 • Union-Find 木 • バケット法と平方分割 • セグメント木 • 共通点：自分で実装するデータ構造 • セグメント木が中心 – IOI でのセグメント木の出題が非常に多い

この記事はCompetitive Programming Advent Calendar 2016（その2）の12月15日の記事です。 www.adventar.org はじめに 基本事項 1点に対する変更クエリ・区間に対する質問クエリ Range Sum Query Range Minimum Query 区間に対する変更クエリ・1点に対する質問クエリ Range Add Query Range Update Query 区間に対する変更クエリ・区間に対する質問クエリ RSQ and RAQ RMQ and RUQ 応用例 Flipping Parentheses セグメントツリーにチャレンジしたくなったら 謝辞 はじめに 私はRMQのような典型的なセグメント木までは比較的容易に実装できるのですが，それよりも難しいクエリに対応したセグメント木を書くのは難しく感じています。とはいえ「区間に

この記事は、Competitive Programming Advent Calendar 2016 - Adventarの15日目の記事です。 この記事について 去年(2015年)の12月ごろ、「セグメント木が任意のモノイドに対して使えるという(当たり前のことが)明示的に書かれた日本語の記事がないなぁ」と思い、「(当時)来年のAdvent Calendarあたりに書こうか」と思ったので書きました。その後調べてみましたが、どうやらこの1年(2015年12月-2016年12月)で割と書かれたようでした。(この記事の意味とは…) 前述のように多数の記事がこの1年間で出たので、この記事は主にそれらへのリンクを貼り、場合によってコードを紹介することにします。 データ構造と代数構造 セグメント木 <=> モノイド 集合M、Mの要素eとその上の二項演算*があり、*が e * x = x * e = x

概要 Union-Find の概要 注意 素集合データ構造と Union-Find 素集合データ構造 Union-Find アルゴリズム アルゴリズムの概要 言葉の整理 Union-Find 木の実装 データ構造の実装 Union-Find 木の実装の大枠 実装 実装のポイント：マージテク，経路圧縮 Union-Find アルゴリズムに関する資料 Union-Find 木のソースコード Union-Find 木で問題を解く 典型的な考え方：辺を切り離す処理より繋ぐ処理の方が簡単 問題一覧 各問題 ATC001: B - Union Find ABC049: D - 連結 / Connectivity ABC075: C - Bridge ABC120: D - Decayed Bridges 類題 終わりに 競プロで「典型」とされるアルゴリズム Union-Find についてまとめました．

競プロで使える謎高速化テクニックを集めた記事ほしいな— Joe@社会 (@xuzijian629) March 31, 2019 ということで自分で書きます。ここでいう高速化とは真に計算量を落とすようなかっこいいものではなく、定数倍高速化のことを指します。 まあこういうのは無限にあると思うんですが、自分が過去に使用したものをいくつか紹介します。 良さそうなのがあれば追記していきたいのでコメントなりで教えてください。 言語はC++です。普段から高速化意識してコード書いてる人には当たり前のことしか書いていないかもしれません。 いつでもできるような高速化 コンパイルオプション コンパイルオプションをこちらが指定できる環境ならばだいぶ強いです。具体的にはAtCoderやCodeforcesが可能で、TopCoderなどクラスで提出するような環境ではダメな気がします。ソースはありません。 プログラム