E - Two Currencies(解説)
[解法]
結論から言えば、拡張ダイクストラというものをする。なにを拡張するのかというと、ノードの数である。 そもそもダイクストラをただ単に移動する最短距離や最小コストを得るものとして捉えるのではなく、 最初の状態から最後の状態 になるための最小コストを得るものだ と捉えてほしい。
ある点からある点への移動 はもっと抽象的にいうと ある状態からある状態への推移
と捉えることができる。 今の状態から次にどのような状態にすることができるかを考えれば、自然にダイクストラを拡張することができる。
今回は、 [街Uにいるときに銀貨をx枚もっている] というものを一つの状態にすることができる。 街Uからは街Vの辺が貼られてるすると遷移先としては、 [街Vにいるときに銀貨をx-A枚持ってる状態]にコストB, [街Uにいるときに銀貨をx+C枚持っている状態]にコストD で遷移することができる。
ここまでくれば、あとは普通のダイクストラをするだけだ。
自分は二次元でダイクストラをしたくないので、[街Uにいるときに銀貨をx枚もっている] という情報を1次元にしたく、 配列で node[U][x] にするのではなく node[U*5000 + x] と変換した。
Aの最大は50,街の最大数は50で必要な銀貨の最大数は50*50=2500枚程度なので かぶることはない。
また、最初に受け取った S を S=min(S,3000) としたのもポイントだ。
以下がACコードになる
1日目 Yokan Party ★4 (競プロ典型90問)
[問題]
問題文は以上の通り。 画像は E8さんのTwitterから拝借。
問題の概要は、「K+1個にバラす時、全てがx以上となる最大のxを見つける」というもの。言い換えれば、最小値の最大値(限界、境界)を見つけるものだ。
なぜ最小の最大 or 最大の最小 は二分探索なのか
なぜこういう類の問題はにぶたんなのか、自分の思考を整理する。
この問題だと、例えば ばらした最小のピースの大きさが 1以上 であるようにはできる。ポイントは、 1であるように ではなくて 1以上であるように という部分だ。
欲しいのは Xであるように だが、 X以上であることができる最大のXを見つけることができれば、それはXであるようにできるということになる。 なぜなら、 全てのピースがX以上であることができるが、(X+1)以上であることができない のならば、最小のピースはXである からだ。
{OK,OK,OK,OK,OK,OK,OK,OK,ng,ng,ng,ng,ng,ng,ng}
上の図の、境界である OKを効率よく見つけられるのができるのが、ご存知二分探索だ。
E - Unique Color(ABC198緑)
DFSの実装で手間取ったのでメモ。
未だに、再帰はイマイチ苦手。
大事なところ
今までdfsを実装する時、"上から下に"行く処理しか書いていなかった。
今回は下から上に上がる(戻る)時にも処理をする必要がある。
木構造の絵を書いてみるとわかる。
具体的には、
void dfs(int now){
//ここにnowに"来た時"の処理
for(auto next:G[now]){
dfs(next);
}
//ここにnowを"抜ける時"の処理
return;
}
の様に書く必要がある。
言われてみれば当たり前だけど、なぜかforの中に抜ける時の処理を書いてたりして脳がバグってた。 再帰をイメージする力を鍛える必要があるようだ。
以下は自分のACコード
E - 常ならずグラフ(緑)
CODE FESTIVAL 2014 決勝のE問題、常ならずグラフを解いた。
過去に問題を見て、解説をみて理解できなかったが、今回は解説を見てすんなり理解したので成長を感じた。
解法
結論からいうとDP
dp[i][0または１]:= R[i]まで見て現在(上昇中 0 or下降中 1)の時の最大値 である。
二重ループで、
if (R[i] > R[j])
chmax(dp[i][0], dp[j][1] + 1);
if (R[i] < R[j])
chmax(dp[i][1], dp[j][0] + 1);
とするのが一番のポイント。
条件を満たす時、過去を使い現在を更新していくイメージ
コード
#include <bits/stdc++.h>
#include "atcoder/all"
using ll = long long;
#define REP(i, n) for (ll i = 0; i < ll(n); i++)
#define DDD fixed << setprecision(10)
#define endl "\n"
#define __MAGIC__
cin.tie(nullptr);
using namespace std;
/*..................DEFINE GLOBAL VARIABLES...................*/
/*.....................DEFINE FUNCTIONS ......................*/
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
/*.........................kemkemG0...........................*/
signed main()
{
__MAGIC__
int N;
cin >> N;
REP(i, N)
cin >> R[i];
// dp[i][0 or 1]:= R[i]まで見た時の最大値 0は今上昇して、１は下降
dp[0][0]=dp[0][1]=1;
REP(i, N)
{
FOR(j, 0, i - 1)
{
if (R[i] > R[j])
chmax(dp[i][0], dp[j][1] + 1);
if (R[i] < R[j])
chmax(dp[i][1], dp[j][0] + 1);
}
}
if(max(dp[N - 1][0], dp[N - 1][1])<3){
cout<<0<<endl;
return 0;
}
cout << max(dp[N - 1][0], dp[N - 1][1]) << endl;
return 0;
}
