AtCoder ABC 165 D - Floor Function (茶色, 400 点) - けんちょんの競プロ精進記録
気づけば一発系。ただし、数式の見た目がエグく見えてしまうかもしれない... 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数 に対する - の値の最大値を求めよ。 制約 考えたこと 全探索すれば だけど、それでは間に合わない。さて、式の見た目がエグくてエグくてやばい。ちょっと思うことは もし「小数点以下切り捨て」とかなくて実数演算だったら、 で常に 0 になるなぁ... というくらいだろうか。よって、なんとなく、この値が大きくなるためには、後半の のところが、でかい小数点を抱え落ちすると良さそうという気持ちになる。たとえば という具合だ。 手を動かす しかし、依然としてよくわからないので、こういうのはいくつかの具体例的に手を動かして、試してみると良さそう。 試しにサンプル 1 に従って、、 について考えてみる。そして に対して値がどのように変わるのかを眺めるのだ。 差
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita
※ ダイクストラ法・ワーシャルフロイド法は最短経路問題を解くアルゴリズムです。 ※ クラスカル法は最小全域木問題を解くアルゴリズムです。 それらのアルゴリズムが学習できる記事たちなどを紹介します。 全探索 全探索には、「全列挙」「ビット全探索」「順列全探索」「再帰関数を用いた全探索」など多くの種類に分かれます。しかし、基本的に以下の記事を読めば全部理解できます。 全列挙 たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】 の 2 章 その他の全探索 たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】 の 3 章 二分探索 アルゴリズムの代表例ともいわれる二分探索は、以下の 2 記事で解説されています。 二分探索とは：アルゴリズムを勉強するなら二分探索から始めよう！ 『なっとく！アルゴリズム』より 競プロで使える二分探索：二分探索アルゴ
競技プログラミングのための代数入門 - beet's soil
モノイド！（素振り） なぜ代数をするのか？ マグマ 半群 モノイド 半群からモノイドへの埋め込み 群 アーベル群 環 整域 体 なぜ代数をするのか？ 代数構造とは、ある性質を持った集合と演算の組に名前をつけたものです。 ある演算そのものに注目するのではなく、より一般にある性質を満たす集合と演算全体に注目することで、その性質を満たすものすべてについての議論を一度に行うことができます。 代数構造はデータ構造とも関連していて、あるデータ構造で扱えるかどうかを代数を用いることで機械的に判定することができます。 例をあげましょう。セグメント木は後述するモノイドを扱うことのできるデータ構造です。 このとき、整数と和や積などの個別の対象がセグメント木で扱えるかどうかをいちいち考える必要はなく、ただ対象がモノイドであるかどうかだけを調べることで判定することができます。 マグマ 集合 と二項演算 の組 のこ
AtCoder ABC 158 E - Divisible Substring (青色, 500 点) - けんちょんの競プロ精進記録
こういう問題を求めてた！！ 問題へのリンク 類題として、こんなのがある。 drken1215.hatenablog.com 問題概要 長さ の、各文字が '0'〜'9' のいずれかとなっている文字列 と、素数 が与えられる。 の空でない連続する区間であって、その整数が で割り切れるものが何個あるかを求めよ。 制約 は を満たす素数 考えたこと 文字列の右側から 個分からなる整数を とおくことにする。たとえば、 S = 1533032 であれば、 = 0 = 2 = 32 = 32 ("032") = 3032 という感じにする。こういう風に「区間に関する問題において、累積和的なものを考える」というのは、Zero-Sum Ranges でもおなじみの考え方！！！！！！！ さて、このとき、S の区間 が条件を満たす条件は と表せることになる。ここで勢いで両辺に をかけて という風にしてしまいた
CODE FESTIVAL 2017 qual C C - Inserting 'x' (緑色, 400 点) - けんちょんの競プロ精進記録
少しでも実装を楽にしたい 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。以下の操作を最小回数行って回文にしたい。その最小回数を求めよ。不可能な場合は -1 を出力せよ。 のどこかに 'x' を挿入する 制約 考えたこと まず可能かどうかの判定だけなら簡単！！！ S から 'x' を取り除いたときに回文でなかったら不可能。回文だったら可能。 最小回数は以下のようにして求まる。たとえば xxxaxxbxxxax とかであれば、'x' なしなら "aba" であって、"aba" の両端と隙間にある 'x' の個数を数えると、 (3, 2, 3, 1) となっている。これに対して 左端の 3 と右端の 1 とを比べて、1 を 3 にする (+2) 左から二番目の 2 と右から二番目の 3 とを比べて、2 を 3 にする (+1) という風にすれば OK。この場合の答え
典型テクニックまとめ - beet's soil
いつも忘れるので整理してまとめるぞい 数え上げ Bell Number: 区別できる n 個のボールを区別できない k 個以下の箱に分割する 特にB(n,n)は n 個のボールを任意個のグループに分割する方法の数である。 Stirling Number: N個の数字をK個の非空のsubsetに分割する通り数 Montmort Number: 撹乱順列の個数 ソートして大きいものから考える 区間の端だけ求めると で求められる 候補の区間が複数ある場合は最長のものだけ考える ちょうどK個 = K個以下 - (K-1)個以下 全てのx∈Gに対しf(x)∈Hを数えるとき、y∈Hに対しf^-1(y)=xなるものを数えることもできる 多項式の係数のGCDは積に対して準同型をなす（ c(P)*c(Q) = c(P*Q) sum(C(i,j)) の形は高速に求められることがある（黒白がX,Y枚あって、その
AtCoder 版！蟻本 (中級編) - Qiita
0 はじめに 前回の初級編に続いて、今度は中級編です。 プログラミングコンテストチャレンジブック (通称、蟻本) は日本の競技プログラミングの普及に多大な貢献を果たしています。多くの競技プログラマたちが蟻本を手に取りながらコンテストの世界に没入して行きます。しかしながら発売から 6 年以上経過する間に競技プログラミング界隈には大きな変化がありました。蟻本的に影響が大きいのは以下の点です: POJ が国内ではあまり使用されなくなった (計算速度が遅いなど) AtCoder 上で問題を解くことが盛んになった 今回はこの完全解決を試みます。具体的には、蟻本に載っている例題たち (ほとんどすべて POJ 上の問題です) を AtCoder 上でジャッジできる問題に対応付けようという試みです。今回は中級編を扱います。AtCoder 上で見つからなかったものは AOJ, yukicoder 上の問題も
AtCoder 版！蟻本 (初級編) - Qiita
0 はじめに プログラミングコンテストチャレンジブック (通称、蟻本) は日本の競技プログラミングの普及に多大な貢献を果たしています。多くの競技プログラマたちが蟻本を手に取りながらコンテストの世界に没入して行きます。しかしながら発売から 6 年以上経過する間に競技プログラミング界隈には大きな変化がありました。蟻本的に影響が大きいのは以下の点です: POJ が国内ではあまり使用されなくなった (計算速度が遅いなど) AtCoder 上で問題を解くことが盛んになった 今回はこの完全解決を試みます。具体的には、蟻本に載っている例題たち (ほとんどすべて POJ 上の問題です) を AtCoder 上でジャッジできる問題に対応付けようという試みです。今回は初級編を扱い、中級編、上級編は別記事に続きます。AtCoder 上で見つからなかったものは AOJ, yukicoder 上の問題も載せています
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
All Div3's Links - Codeforces