素数砂漠なん！！！ 問題へのリンク 問題概要 整数 が与えられる。 を含む素数砂漠 (連続する合成数) の長さを求めよ。 すなわち、 以上の最小の素数と、 以下の最大の素数との差を求めよ。 制約 解法 エラトステネスの篩で予め 2000000 くらいまでの整数に…

この問題の既存の解説記事は中国剰余定理によるものが多かったので、それ以外の方法を示すのはいいかもなん。 AOJ 2353 Four Arithmetic Operations 問題概要 有理数列 がある。各項は以下のように定義される: ただし は ＋、－、×、÷ のいずれかである。 を…

二重辺連結成分分解と聞いて 問題へのリンク 問題概要 n 頂点 m 辺の連結な無向単純グラフが与えられる。 2 点 s, t を選んで、「その辺を壊したら s と t とが繋がらなくなる」ような辺をすべて壊すことを考える。 できるだけ多くの辺を壊したい。うまく s,…

Garner のアルゴリズムの verify に最適なん 問題へのリンク 問題概要 個の合同式 (mod. ) を満たす最小の正の整数 を 1,000,000,007 で割った余りを求めよ。存在しない場合には -1 をリターンせよ。 制約 < 解法 中国剰余定理で保証される最小の非負整数 を…

中国剰余定理ライブラリの verify 用問題の 1 つ AOJ 2659 箸 問題概要 箸が最初 本あった。また 個の正の整数 が与えられる。 に対して以下の 回の操作を実施したとき、最終的に の値がどのようになるかを答えよ ( が存在し得ない場合には とせよ)。 【操作…

超定番の stack を使うやつですね。類題として 2018 第4回ドワンゴからの挑戦状 予選 B - 2525文字列分解 ABC 064 D - Insertion AOJ 1173 世界の天秤 AOJ 2369 CatChecker AOJ 2490 () がある。これらは見た目は違えど、どれも (()((()())()())())()))(()) …

ちょうど中国剰余定理シリーズやっていたので、ピンポイントだったん。 SRM 735 DIV1 Medium QuadraticIdentity 問題概要 整数 が与えられる。 (mod. ) を満たすような < ) をすべて求め、そのサイズが 500 より大きい場合には 500 以下になるまで以下の操作…

AOJ-ICPC で無作為に問題を選んで実装する練習するなん。いや、つらいのんな^^; あと、桁 DP でやってしまったけど、もっとずっとはるかに楽な方法があったん。。。 問題へのリンク 問題概要 1 から順に FizzBuzz をやって得られる文字列を FizzBuzz 文字列…

中国剰余定理のことをあれこれ調べていたら勢いで解いたん 問題へのリンク 問題概要 整数 が与えられる。 mod. ) が成立するような 以上 以下の整数 を数え上げよ。 制約 は素数 < 解法 Fermat の小定理から以下のことが言える: は mod. において周期 である…

こんなしゃくとり法もあるのんな。面白いん。 ABC 098 D Xor Sum 2 問題概要 長さ の正の整数列 が与えられる。整数列の連続する部分列のうち、「xor 和と加算和とが等しい」という条件を満たすものを数え上げよ。 制約 数値例 1) 答え: 5 (2), (2, 5), (5),…

の Kruskal 法ではダメで、 な Prim 法なら OK という稀有なパターンの問題。Dijkstra 法でも priority_queue を使ったやつは 愚直なやつは と二種類の実装があって前者の方が速いと言及されるケースも多いけど、密グラフ ( なグラフ) では後者の方が速い。P…

FFT 勉強シリーズその 2 なん。 うーん、、、これ思いつけるもんなんかいな...なのん Codeforces 488 DIV1 E - Nikita and Order Statistics 問題概要 要素の整数数列 と整数 が与えられる。数列 の連続する部分列のうち、「 未満の値となっているものが 個…

FFT の勉強シリーズその 1 なん yukicoder 0206 数の積集合を求めるクエリ 問題概要 どの 2 つも互いに相異なるサイズ L の数列 A[0], A[1], ..., A[L-1] と どの 2 つも互いに相異なるサイズ M の数列 B[0], B[1], ..., B[M-1] とが与えられる。 各 A[i], B…

ARC 099 E - Independence の類題という感じ。具体的には「補グラフをとって二部グラフを考えて...」みたいなところのが似てる。 問題へのリンク 問題概要 人の女の子と、 人の男の子がいて、「女の子同士」「男の子同士」はすべて互いに知り合いである。 そ…

いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たい。 類題として AOJ 2370 RabbitWalking (二部グラフ判定からの部分和ナップサックが酷似) POJ 3692 Kindergarten (補グラフとって二部グ…

完全に冷静さを欠いたし、ハマった。。。 ARC 099 D - Snuke Numbers 問題概要 (ARC 099 D / ABC 101 D) 正の整数 N に対してその 10 進法での桁の和を f(N) で表す。今、正の整数 N がすぬけ数であるとは、任意の N より大きい正の整数 M に対して f(N) / N …

ARC 099 C - Minimization 問題概要 (ARC 099 C / ABC 101 C) 1〜N の順列が与えられる。以下の操作を最小回数繰り返すことにより、全部 1 にせよ。 連続する K 個の区間を選んで、その区間のすべての数をその区間にある最小の数に置き換える 制約 1 <= K <=…

しゃくとり法とは違うけど、区間の左端と右端とのどちらかを伸ばしていく感じはしゃくとり法に近いかもなん CS Academy 082 DIV1 C - City Break 問題概要 円環状に 個の街がある。街 i と街 i+1 との間の距離が a[i] で与えられる (i = N のときは街 N と街…

ABC 100 D - Patisserie ABC 問題概要 整数 3 つ組 (xi, yi, zi) が N 個与えられる。 このうちの M 個選んで、 (x の選んだ M 個の総和の絶対値) + (y の選んだ M 個の総和の絶対値) + (z の選んだ M 個の総和の絶対値) が最大になるようにせよ。 制約 1 <=…

結構好きな問題 ABC 100 C - *3 or /2 問題概要 N 個の整数 a1, a2, ..., aN があって 1 回の操作で以下が行える 各整数について「3 倍」「2 で割るなら 2 で割る」のいずれかを行う どれかの整数については「2 で割る」の方をしなければならない 最大で何回…

Yay!Yay!Yay!Yay!Yay!Yay!Yay!Yay! 頭の整理が結構大変な問題だと思うのん。 ABC 100 A - Happy Birthday! へのリンク 問題概要 円形のケーキが 16 等分されている。2 人がそれぞれ A ピース、 B ピースとる。同じ人が隣り合うピースを選ばないように選ぶこ…

slack 勉強会で 600 点の DP として話題になってやってみたん。 DP 自体は素朴だけど、計算量解析含めると 700 点でもいい気はする。 Grouping 問題へのリンク 問題概要 (ARC 067 E) 人をグループ分けしたい。 人は互いに区別される。 どのグループの人数も …

解けたけどもっとちゃんと整理しないとなん 問題へのリンク 問題概要 N 個の整数 a_1, a_2, ..., a_N が与えられる (0 <= a_i <= 9)。これを並び替えて順につないでできる整数 (leading zero は除く) として考えられるものの総和を 109 + 7 で割った余りで求…

バチャやりました！ vjudge.net バチャの中では 4 問中 3 番目の難易度。問題の構造自体はこの記事の最後の章で書いたような典型的な区間分割型のナップサック DP なのですが、条件がゴチャゴチャしていてややこしかったです。。。 類題として、RUPC の以下…

バチャやりました！ vjudge.net E 問題で、バチャに選定した 4 問の中では 2 番目の難度、AtCoder で言うと 400 点くらいの難易度でした。 問題へのリンク 問題概要 N 頂点 M 辺の重み付き無向単純グラフが与えられる。頂点 1 から頂点 N への経路のうち、「…

バチャやりました！ vjudge.net L 問題ですが、一番易しい問題です。 問題へのリンク 問題概要 N 個の値 a_1, a_2, ..., a_N が与えられる。 このうちの 3 つをうまく選ぶことで、3 辺の長さがそれらになるような三角形を作ることができるかどうか判定せよ。…

1. 典型的な二項係数の求め方 競プロをしていると、「 mod 」を計算する場面にしばしば出くわします。最近では、 であることが多いですね。 mod の計算方法は、時と場合によって色んな方法が考えられますが、すぐ下で紹介する方法が最も頻繁に使用されていま…

600 にしちゃムズイ。 ARC 097 E Sorted and Sorted 問題概要 (白, 1), (白, 2), ..., (白, N), (黒, 1), (黒, 2), ..., (黒, N) の 2N 個の要素の順列が与えられる。「隣同士を swap する」を最小回数行うことで、「白」についても「黒」についてもソートさ…

本番出てなかったけどこれは... ARC 097 C K-th Substring 問題概要 文字列 s が与えられる。s の連続する部分文字列のうち、辞書順で K 番目の文字列を求めよ。 制約 1 <= |s| <= 5000 1 <= K <= 5 解法 K が小さいのが怪しい。 冷静に考えると、辞書順 K …

本番中に解きたかった... ARC 098 F Donation 問題概要 N 頂点 M 辺の連結な単純無向グラフがあります。 頂点 i には二つの整数 Ai, Bi が定められています。 このグラフ上で次のようなゲームをします。 初めに、W 円を持った状態で好きな頂点に立つ。 ただ…