競技プログラミングのための精進履歴をブログ形式で残していきます。
目標は AtCoder 水色！
今のレートは茶色です。
本日の精進ツリーは以下のとおり。
精進ツリー
ABC167: C – Skill Up
ABC167 より、C – Skill Upを解きました。
難易度は茶色。
求める解が「金額の最小値」ということで、一瞬 DP かと思って迷いましたが、制約を見て全探索でいけると判断しました。
N と M は最大12なので、各本に対して、「買う」or「買わない」のパターンを網羅させても計算量の最大値は 12 * 2^12 で済みそうだと考えました。
本を「買う」or「買わない」の選び方を探索していくので bit 全探索を使おうと思いましたが、何となく使い慣れていないこともあり、普通に再帰で解きました。
提出コードはこちら。
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;
#define MAX 100010
#define NIL -1
using lint = long long int;
using P = pair<lint, lint>;
/*************************************************************************************
NOTE:
・目標を達成するのに必要な金額の最小値・・・
・NとMは最大12なので、各本に対して、買うor買わないのパターンを網羅させても 2^12 * 12で済みそう
*************************************************************************************/
/*************************************************************************************
LOGIC:
1. 各本について、買うor買わないのパターンを網羅した再帰関数を作成する
2. 全パターン網羅した時にすべての理解度がXを超えたもののうち、最もコストが小さいものが回答
*************************************************************************************/
vector<vector<lint>> my_input(13);
lint N, M, X;
lint ans = MAX * 13;
bool flag = false;
bool is_enough(vector<lint> known)
{
bool is_enough = true;
for (int i = 1; i <= M; i++)
{
if (known[i] < X)
{
is_enough = false;
break;
}
}
return is_enough;
}
void buy_or_notbuy(vector<lint> known, int book)
{
if (book == N + 1)
{
if (is_enough(known))
{
flag = true;
ans = min(ans, known[0]);
return;
}
return;
}
// 買わない
buy_or_notbuy(known, book + 1);
// 買う
vector<lint> bought(13, 0);
for (int i = 0; i <= M; i++)
{
bought[i] = my_input[book][i] + known[i];
}
buy_or_notbuy(bought, book + 1);
return;
}
int main()
{
cin >> N >> M >> X;
lint a, c;
for (int i = 1; i <= N; i++)
{
cin >> c;
my_input[i].push_back(c);
for (int j = 1; j <= M; j++)
{
cin >> a;
my_input[i].push_back(a);
}
}
vector<lint> known(13, 0);
buy_or_notbuy(known, 1);
if (flag) cout << ans << endl;
else cout << -1 << endl;
return 0;
}
ABC167: D – Teleporter
ABC167 より、ABC167: D – Teleporterを解きました。
難易度は茶色。
始めは手前から順に試していこうかと思いましたが、 K の制約が 10^18 だったので断念。
それぞれの街は、必ずどこかの街にテレポートできるという点と、街の最大数が 2 * 10^5 ということに着目しました。
最悪でも、2 * 10^5 回テレポートする間に、ループ区間が発生するはずなので、ループ区間の移動回数と、残りの K の剰余が分かれば、 K 回テレポートした場合の行先きがわかります。
ちなみに、 K が 2 * 10^5 以下の値で、ループ区間が発生しない場合には、 K の回数普通にワープさせれば答えになります。
ということで、 O(N) に帰着しました。
提出コードはこちら。
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;
#define MAX 200010
#define NIL -1
using lint = long long int;
using P = pair<lint, lint>;
/*************************************************************************************
NOTE:
・街 A からテレポートできる先は 1 つのみ。
・スタートは 1 で固定されているので、各テレポート先の情報を持った配列を作成すれば、O(K)で解けそう
→ K の制約が 10^18 なので、これでは NG
・N の制約が 2 * 10^5 なので、何とか O(N) の計算量で答えを出したい
→ ワープを 2 * 10^5 回以上やるまでの間に、必ず繰り返しが発生するはず
・ループの最小単位を見つける
*************************************************************************************/
/*************************************************************************************
LOGIC:
1. 2 * 10^5 個の要素を持つ配列を作成する
2. インプットされたテレポート先を対応する配列に入力していく
3. K をたどっていく
→ K の制約が 10^18 なので、これでは NG
4. K をたどっていくなかで、ループの最小単位を見つける
*************************************************************************************/
int main()
{
lint N, K, cycle, food;
cin >> N >> K;
vector<pair<lint, lint>> vec(MAX);
for(int i = 1; i <= N; i++)
{
cin >> vec[i].first;
vec[i].second = 0;
}
lint now = 1;
lint loop_start = 1;
lint moved = 0;
while(K > 0)
{
if (vec[now].second != 0)
{
loop_start = now;
break;
}
else
{
vec[now].second = moved;
now = vec[now].first;
}
moved++;
K--;
}
if (K > 0)
{
// ループ区間
cycle = moved - vec[loop_start].second;
food = K % cycle;
while (food > 0)
{
vec[now].second = moved;
now = vec[now].first;
food--;
}
}
cout << now << endl;
return 0;
}
まとめ
今日解いた問題は、かなりすんなり解法を思いつくことができました。
ただ、 D 問題のループの実装は脳内シミュがうまくいかずに躓いてしまいました。
脳内メモリ拡張したい。
