半分全列挙
半分全列挙の典型問題！ 問題へのリンク 問題概要 長さが の 4 つの数列が与えられる。これらから要素を 1 個ずつとってきて、総和を にすることが可能か判定せよ。 制約 メモ 「半分全列挙」を用いる。詳細は鉄則本にて。 コード #include <bits/stdc++.h> using namespace</bits/stdc++.h>…
これも最近よく見る「整数の式で表された条件を扱う探索問題」の一味ですね！ 問題へのリンク 問題概要 整数 が与えられる。 正の整数 の組であって、 を満たすものの個数を求めよ。 制約 考えたこと もし計算時間をまったく気にしなくてよいならば、次のよ…
面白かった 問題へのリンク 問題概要 以下の素数のみを素因数に持つ正整数を -smooth number と呼ぶ。 整数 および 、100 以下の素数 が与えられるので、 以下の -smooth number の個数を求めよ。 制約 考えたこと コンテスト中には、愚直 DFS を頑張って通…
これ FFT を使えば でもできるね。実際は で間に合う。 ジャッジページ 問題文 問題概要 正の素数 と、正の整数 が与えられる。 は 以上 以下の整数 を満たすような の組の個数を求めよ。 制約 は素数 考えたこと まずは次のように集計処理をしよう。このよ…
半分全列挙 + Binary Trie！！ あるいは、Binary Trie 自体を意識しなくても、上の位から順に桁 DP 的発想で考えていると、それが自然に Binary Trie 上の探索そのものとみなせる！ すごくいい Binary Trie の経験になった！！ 問題へのリンク editorial 問…
AtCoder 版蟻本記事で、登竜門として紹介している問題。 ずばり「半分全列挙 + 二分探索」です！ 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらの整数のうちから重複を許して 4 個まで選んで総和をとる (1 …
まさかの超典型な半分全列挙！！！(蟻本にもほぼ同じ問題あり！！) 問題へのリンク 問題概要 個の正の整数 と、正の整数 が与えられる。 個の整数の中からいくつか選んで総和をとる。その値が より大きくならない範囲内での、その値の最大値を求めよ。 制約 …
ちょっと面白い感じの構築問題！ 問題へのリンク 問題概要 正の整数 が与えられる。 以下の条件を満たす 3 つの格子点 の組を一つ求めよ。 座標値はすべて 以上 以下の整数値 3 つの格子点からなる三角形の面積を 2 倍すると に一致 制約 考えたこと 仮に 1 …
TLE が厳しかった... 問題へのリンク editorial 問題概要 頂点数 の単純無向グラフ が与えられる (連結とは限らない)。各頂点 には重み がついている。 頂点 1 を含む の安定集合をすべて考えたときの、安定集合中の頂点の重もの総和の最大値を求めよ。 制約…
半分全列挙した！ 問題へのリンク 問題概要 正の整数 と整数 が与えられる。以下の条件を満たす正の整数 の組の個数を求めよ。 制約 考えたこと 愚直な方法としては、次のように 4 重ループをする解法が考えられるかもしれない。しかしこれでは の計算量を要…
落ち着いて頭を整理。。。 問題へのリンク 問題概要 'R', 'G', 'B' のみからなる長さ の文字列 が与えられる。 の index の組 であって、 と と はすべて互いに異なる である という条件を満たすものの個数を求めよ。 制約 考えたこと 頭がごっちゃになりそ…
これはマジで天才やと思うやが... いや本当にどこから Grundy 数を導けるのか、わからぬ... 問題へのリンク 問題概要 頂点数 のグラフが 3 つ与えられる。それらのグラフのカルテシアン積を考える。この頂点数 のカルテシアングラフの独立集合のうち、以下の…
めちゃくちゃ面白い！！！ 問題へのリンク 問題概要 (意訳) 思いを寄せている先輩に 週後に告白したいので、その日までに先輩の好感度を最大化しておきたいです。最初、「所持金」と「好感度」はともに 0 です。毎週、以下のいずれかの行動を起こすことがで…
教育的ないい問題！！！！！ 問題へのリンク 問題概要 本の棒があって、それぞれ の長さをもっている。 このうちの 3 本を選ぶ方法であって、その 3 本で三角形が作れるものは何通あるか？ 制約 解法の overview ものすごく色んな解法が考えられる問題だと思…
大変だった ^^; 問題へのリンク 問題概要 全部で 色の色がある。 下図のような 枚の正方形があって、それぞれ のラベルがついていて、各正方形の四隅にはいずれかの色が塗られている。 枚の中から 6 枚を選んで立方体を作る。ただしどの頂点についても、そこ…
priority_queue で動的に 個出力する問題作りたいな〜と思ってぼんやりストックしてた問題と一緒だった！！！！！！ 問題へのリンク 問題概要 個の要素からなる数列 個の要素からなる数列 個の要素からなる数列 が与えられる。 からそれぞれ 1 個ずつとりだ…
なんだろ 問題へのリンク 問題概要 個の薬品があって、それぞれ成分 A, B を グラムずつ含んでいる (すべて整数値)。 これらのうちのいくつかを選んで混ぜ合わせることで、成分 A, B の比がちょうど : となるようにしたい。 そのようなことが可能となる薬品…
スライド最小値の練習 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 個のアイテムがって、それぞれ市場価値 と貴重度 が与えられる。 今、A さんと B さんがそれぞれアイテムのうちの何個かをとる。このとき、A さんと B さんは同じアイテム…
なんかこれは TL で「 という制約が意味するものは...！？」という感じの TL を先に見てしまった。。。 とはいえ確かに半分全列挙一択ではあるか... 問題へのリンク 問題概要 (AGC 026 C) 長さ の、英小文字のみからなる文字列 が与えられる。 の各文字を赤…
