Hisui-競プロ支援ツール-競技プログラミング専用ツールHisuiを使って、競プロもっと楽しもう 競プロ向けにカスタマイズされたエディター、順位や時間などの必要な情報をすぐに手に入れられるダッシュボード、 競プロに役立つさまざまな機能が備わっています Windows・Mac対応
ダイクストラ法のよくあるミスと落し方 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
ダイクストラ法、正しく書けてますか？ ダイクストラは少しのミスですぐ計算量が壊れたりするのですが、テストケースによっては意外に落ちにくく間違いに気づかないこともあります。 この記事では、よくあるミスとその撃墜ケースを紹介していきます。 この記事はどちらかと言うと問題準備をする方に読んでほしい記事です。 writerをする際は、ここで紹介する撃墜ケースをテストケースに入れるようにすると良いと思います。 SではなくTを始点にするという小手先技が考えられるので、逆向きバージョンも入れておくと尚良いでしょう。 ジェネレーターも置いておきます。 コード中の定数を書き換えたり入力で取れるようにしたり、出力形式を変えたりして使ってください。 念の為生成されたテストケースにもちゃんとvalidatorをかけて下さい。 目次 既に見た頂点のcontinue忘れ： 最大ヒープを使う： 負辺のあるグラフで使う：
レーベンシュタイン距離を完全に理解した！(C++編)
※この記事はQiitaからの移行記事です こんにちは、競プロ絶賛勉強中のyapattaです。 AOJ(AIZU ONLINE JUDGE)のレーベンシュタイン距離の問題を解くことができなかったから、理解するために記事を書いた。プログラミングをやってない人でも理解できる記事を書きたい。 この記事を見て、レーベンシュタイン距離について理解して頂ければ幸いである。 最後に実装されたコードが書かれているので、コードだけみたい人は是非最後だけ見て欲しい。 1)レーベンシュタイン距離(編集距離)とは？ レーベンシュタイン距離とは、とりあえず２つの文字列がどのぐらい違っている文字列か表す指標であると理解してもらえるといい。 文字列Aの中の1文字を、置換、挿入、削除を繰り返しすことで、一方の文字列Aをもう一方の文字列Bに変形する。この繰り返しの最小回数をレーベンシュタイン距離という。詳しくは以下↓ レーベ
しゃくとり法のDequeを使ったバグりにくい実装 - Qiita
この記事の目的 しゃくとり法のバグりにくい実装の紹介です！ しゃくとり法(尺取り法)って？ しゃくとり法の説明自体は、とってもいいまとめがあるのでこちらをご覧ください。 しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ でも、しゃくとり法ってバグりません？ しゃくとり法っていざ書いてみるとかなりの確率でバグります。 区間の端を表す添え字 $l$ と $r$ の動かし方が結構混乱します。 この記事ではdeque(両端キュー)を使った実装を紹介します。 なんとこの実装では添え字を使う必要がありません！ deque(両端キュー)によるしゃくとり法の実装 次の問題を例にとって説明します。 ABC 032 C - 列 長さ $n$ の整数列 $A = \{a_1, a_2,..., a_n\}$の連続部分列で、その要素の積が $K$ 以下となるものの長さの最大値を求める問題です。 次の
【Python版】AtCoderのコンテスト中に「問題が解けない！」となった時に読む記事 - Qiita
この記事は、競プロ Advent Calendar 2021 3 日目の記事です。 飛ばしていい雑談 現在水色コーダーのH20と申します。 2020年の5月よりAtcoderのコンテストに参加してから、競技プログラミングという沼にハマり続け、参加回数はすでに80回を超えました。 沼にハマり続けるのは何も競技プログラミングだけに限りません。WA(不正解)とTLE (実行時間超過)の沼にもハマり続けました。 何度「解法は合ってた、解けてたはずなのに！」という後悔と、「ぎりぎりバグを見つけて通せた！」という喜びがあったでしょうか1。 実装ミスは特にこの半年の上がっては下がりを繰り返す気にくわないほど横ばいなレート推移となる一因です2。 とにかく今悩んでいる問題の AC (正解)を目指す。 解法は合ってるはずなのに何故か提出するとWAになってしまう状況や、ペナの数はもう気にしないとにかくこの一問を
二分木が平衡か判定する方法
引き続き『世界で闘うプログラミング力を鍛える150問』の問題を解いていこう。プログラミング言語は Python を使う。 お題を引用しよう。 二分木が平衡かどうかを調べる関数を実装してください。平衡木とは、どのノードの2つの部分木も、その高さの差が1以下であるような木であると定義します。 順を追って考えていこう。 二分木のデータ構造 Wikipedia にある二分木の定義はこうだ。 計算機科学でいう二分木は、データ構造の1つである。根付き木構造の中で、あるノードが持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。 この構造を素直にプログラムに直したのが次のコードだ。 This file contains bidirectional Unicode text that may be interpreted or compiled differently
うさぎでもわかる2分探索木 後編 2分探索木における4つの走査方法
こんにちは、ももやまです。 今回は2分探索木の4つの走査方法、具体的には 行きがけ順による走査通りがけ順による走査帰りがけ順による走査幅優先探索による走査 の4つの違いについてわかりやすく説明していきたいと思います！ 「2分探索木ってどんなやつだっけ」、「2分探索木忘れちゃったよ」という人は下にある記事でわかりやすく2分探索木について説明しているのでぜひご覧ください！ www.momoyama-usagi.com １．2分探索木の全探索 木構造にある各ノードを1度だけ訪問することを探索（走査）と呼びます。 全探索の仕方をおおまかに分けると、 深さ優先探索(DFS)幅優先探索(BFS) の2つとなります。 さらに、深さ優先探索はさらに 行きがけ順（先行順 / 前順 / preorder）通りがけ順（中間順 / 間順 / inorder）帰りがけ順（後行順 / 後順 / postorder）
競プロ典型 90 問 005 - Restricted Digits（★7） - けんちょんの競プロ精進記録
きたまさ法によく似たタイプの DP ダブリング高速化！ ただかなり難しい問題だと思うので、004 まで順調に解いていた方が、この問題で挫折しないように注意！！！ 無理に解こうとせずに飛ばすのも一案だと思います...... 問題へのリンク editorial 問題概要 種類の数字 のみを使うことで作れる 桁の正の整数のうち、 の倍数は何個あるか、 で割ったあまりを答えてください。 制約 まずは DP 今回の問題のように、「〜という数字を使って整数を作り、それが の倍数になるようにする」というタイプの問題では、DP が有効な印象があります。 drken1215.hatenablog.com そのような DP では、整数というものを、 倍する を足す という つの手続きを繰り返すことで作り上げるものと考えます。たとえば "" という整数は 整数 からスタートして 倍して を足すと、 になる
こわくないbit全探索1 入門編: bit全探索ってなに？【競プロ解説】 - Qiita
競技プログラミング（AtCoder）初心者が、最初に突き当たる壁になることが多いアルゴリズムのひとつに『bit全探索』があります。 この記事では、その『bit全探索』についてできる限り丁寧に解説をしていきます。 記事リンク 1. 入門編 bit全探索ってなに？ : bit全探索はどんなことをするアルゴリズムなのか解説します。 2. 基本編1 簡単な例題でbit全探索をやってみよう！ : 簡単な例題（部分和問題）で実際にbit全探索を実装してみます。 3. 基本編2 2進法を使って実装してみよう！ : 2進法を使ったbit全探索の実装をしてみます。 4. 実践編 AtCoderの問題を解いてみよう！ : AtCoderのbit全探索を使う問題のヒントとコード（Python・C++）を載せています。 5. 応用編 3つ以上の選択肢は再帰関数で書こう！ : 再帰関数を使ってbit全探索に似た問題
桁DPの痒いところに手が届く解説 - Qiita
はじめに 本記事は、アルゴリズムの一つである桁DPについて、入門者が疑問に感じる（というか筆者が実際疑問に感じた）ポイントに重点を置いて解説するものです。 筆者自身そこまで桁DPに詳しいわけではなく、むしろ最近覚えたぐらいなので、何かまずい部分があれば優しくご指摘いただけると嬉しいです。 この記事で特に重点を置くポイントは、次の通りです。 何故これでうまくいくのか 桁DPで数えているものは何か 初期条件はなぜこうなるのか 桁DPそのものの入門的解説としては、他にもけんちょんさん達の優れた記事がありますので、そちらも合わせてご覧ください。 http://torus711.hatenablog.com/entry/20150423/1429794075 http://drken1215.hatenablog.com/entry/2019/02/04/013700 https://pekempe
Typical DP Contest - AtCoder
お知らせ モーダルが現れました。(9/01 1:00) 順位表が一部正しく表示されていません。原因を調査中です。(9/01 0:12) 9 月になりました。あけましておめでとうございます。コンテストは残り一時間です。現在とかれていない問題は Q のみです。(9/01 00:00) リジャッジを行いました。(8/31 23:24) P 問題のリジャッジを行います。(8/31 23:17) 半分経過しました。現在とかれていない問題は P, Q, R の三問です。(8/31 22:30) リジャッジを行いました。(8/31 21:04) H 問題に不正な入力がありました。申し訳ございません。リジャッジを行います。(8/31 21:00) 質問に回答しています。質問も定期的にご確認ください。(8/31 20:44) D 言語は使用できないようです。(8/31 20:32) ペナルティタイムは 5
桁DP(Digit DP) を考え方から問題例まで徹底解説！ | アルゴリズムロジック
桁DPとは 桁ごとに分けて考える動的計画法です。 「1からNまでの整数について、条件を満たす数はいくつあるか？」「1からNまでの整数について、条件を満たす最大値は何か？」 というような問題で主に使えます。 Nについての制約が非常に大きくなるのが特徴で、O(logN)やO(1)でないと計算時間が間に合わない問題で使用されます。 桁DPの前に知っておくと良いこと 桁DPでは、「N以下の数を全て走査する」ことになりますが、以下のような場合分けを考慮しておくと分かりやすくなります。 例えば、N=63435 のような数であれば、 00000 ~ 59999 (\(6\cdot 10^4\) 通り)60000 ~ 62999 (\(3\cdot 10^3\) 通り)63000 ~ 63399 (\(4\cdot 10^2\) 通り)63400 ~ 63429 (\(3\cdot 10^1\) 通り)6
二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita
0. はじめに 二分探索法は単純ながらも効果が大きく印象に残りやすいもので、アルゴリズム学習のスタート地点に彩られた花という感じです。二分探索というと「ソート済み配列の中から目的のものを高速に探索する」アルゴリズムを思い浮かべる方が多いと思います。巨大なサイズのデータを扱う場面の多い現代ではそれだけでも十分実用的ですが、二分探索法はもっとずっと広い適用範囲を持っています。 本記事では、二分探索法のエッセンスを抽象化して、適用範囲の広い「二分探索法の一般形」を紹介します。同時に無数にある二分探索の実装方法の中でも「めぐる式二分探索」がバグりにくいと感じているので、紹介したいと思います。 注意 1: 二分探索の計算時間について 二分探索の計算時間について簡単に触れておきたいと思います。例えば「$n$ 個の要素からなるソート済み配列から目的の値を探索する」というよく知られた設定であれば、 単純な
BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 - Qiita
0. はじめに メジャーなグラフ探索手法には深さ優先探索 (depth-first search, DFS) と幅優先探索 (breadth-first search, BFS) とがあります1。このうち DFS については DFS (深さ優先探索) 超入門！ 〜 グラフ理論の世界へ 〜 【前編】 DFS (深さ優先探索) 超入門！ 〜 グラフ理論の世界へ 〜 【後編】 にて詳しく特集しました。これらの記事中で幅優先探索 (BFS) についても簡単に触れているのですが、今回改めて特集します。特に、後編で紹介した グラフの二点間の到達可能性 グラフの連結成分の個数 二部グラフ判定 トポロジカルソート サイクル検出 といった問題たちが BFS によっても解くことができることを示します。一つの問題を DFS・BFS と様々な探索手法で解くことで、グラフの様々な性質をより深く親しむことを狙います。
わんこら日記 わんこら式数学の勉強法(受験生、小学生から中学生、高校生、大学生、社会人まで通用)
今からわんこらの数学の勉強法を聞いてもらいます。うへ～。 １、定義、定理、解き方を覚える ２、無理やりページを進める ３、解き方をノートに写す ４、高速で繰り返す ５、適当にやれば次へ！ ６、出来ることをやる ○、覚醒モードに入る わんこら式数学の勉強法の実践動画(最新版) →わんこらメルマガ サンプル号も読んでください noteでの購読は→こちら １、定義、定理、解き方を覚える 数学は定義や定理、解き方まで何でも覚えまくってください。 あれはまだ短パンでママと手を繋いでお出かけしてたまだ純粋な頃やった。 僕は九九を覚えずにまともに計算してました。 それでドリルの真ん中辺りで ぶほー！ って血吐いて倒れてました。 それから学校で九九を強制的に覚えさせられたら簡単に出来るようになりました。 これはもう明らかに暗記が必要ですね。 ○難しい証明も定義や定理がスラスラ出るくらいじゃないと中々理解で
現役高校生が、AtCoderでレッドコーダーになるまでにやってきたこと。プログラミング上達の秘訣を全て教えます - Findy Engineer Lab
こんにちは、はじめまして。筑波大学附属駒場高等学校 3 年生（今年 4 月から東京大学に入学予定）の米田優峻（@e869120）と申します。私は競技プログラミング（競プロ）が趣味で、AtCoder・情報オリンピック・パソコン甲子園などの大会に出場しています。2021 年 3 月時点で、AtCoder では赤色（レッドコーダー）です。また、国際情報オリンピックの 2018 年／2019 年／2020 年大会で金メダルを獲得しています。*1 とはいえ、決して簡単にこの記録を手に入れられたわけではありません。何度も挫折と失敗を経験しながら自分のスキルを磨いた結果、競プロを始めてから 3 年後にはレッドコーダーになることができたのです。 今回は「わたしの選択」というテーマで寄稿の機会を頂いたので、私が中学 1 年生の秋に競技プログラミングを始めてからレッドコーダーになるまで、そして国際情報オリンピ
アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 - Qiita
こんにちは、大学 1 年生になったばかりの E869120 です。 私は競技プログラミングが趣味で、AtCoder や日本情報オリンピックなどに出場しています。ちなみに、2021 年 4 月 7 日現在、AtCoder では赤（レッドコーダー）です。 本記事では、アルゴリズムの学習や競技プログラミングで使える数学的な部分を総整理し、それらについて解説したいと思います。前編・中編では数学的知識、後編（2021/4/26 公開予定）では数学的考察の側面から書いていきます。 【シリーズ】 アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 ← 本記事 アルゴリズム・AtCoder のための数学【中編：数学的知識編②】 アルゴリズム・AtCoder のための数学【後編：数学的考察編】 1. はじめに 21 世紀も中盤に入り、情報化社会（いわゆる「IT 化」）が急激に進行していく中、
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
E869120@本発売 on Twitter: "5 日目の解説です。今日は日曜日なので新規出題はありません。なお、各小課題のサンプルコード（合計 3 個）を GitHub に挙げましたので、是非ご活用ください。明日は平日なので、投稿は通常通り 7:40 です。 #競プロ典型90問 https://t.co/mM9Ppi9kmy"
GitHub - E869120/kyopro_educational_90: 2021/3/30 ～ 2021/7/12 に行われる企画「競プロ典型 90 問」の問題・解説・ソースコードなどの資料をアップロードしています。
book_algorithm_solution/solutions at master · drken1215/book_algorithm_solution