初回 -> はじめに
ABC137を解きました。
4完です。
E問題は解説を見て解きました。
| 問題 | 時間 | アルゴリズム | 実行時間 |
|---|---|---|---|
| A | 1min | - | 7ms |
| B | 3min | - | 6ms |
| C | 12min | ヒストグラム | 53ms |
| D | 27min | 動的計画法 | 41ms |
| E | - | ベルマンフォード法 | 88ms |
A - +-x
int a, b;
cin >> a >> b;
cout << max( { a + b, a - b, a * b } );
そのままですね。
3つの計算結果のmaxをとると答えになります。
max関数の引数にタプルをもってこれるのは初めて知りましたw
B - One Clue
int k, x;
cin >> k >> x;
for(int i = x - k + 1; i < x + k; ++i)
{
cout << i << " ";
}
座標Xに黒い石が置かれていて、その左右隣が白い石になる場合を考えるといいですね。
つまり境界値を考えます。
[ x - k + 1, x + k - 1 ] の範囲が答えになります。
C - Green Bin
int n;
cin >> n;
unordered_map< string, ll > ana_list;
string s;
for(int i = 0; i < n; ++i)
{
cin >> s;
sort(s.begin(), s.end());
ana_list[s]++;
}
ll ans = 0;
for(const auto& ana : ana_list)
{
ans += ana.second * (ana.second - 1LL) / 2LL;
}
cout << ans;
ヒストグラムが使えますね。
ヒストグラムはbin sortで使う考え方ですが、問題名の「Green Bin」より想起されました。
受け取った文字列をソートすると、アナグラムの関係にある文字列は同じ一意の結果になります。
つまり、ソート後の文字列が何回現れたかを記憶しておけば答えは出せます。
ハッシュマップより、ソート後の文字列をkeyとして発生回数を記憶しています。
最後に組み合わせ nC2の計算式をつかって答えを出しました。
D - Summer Vacation
int n, m;
cin >> n >> m;
vector<P> job(n);
for(int i = 0; i < n; ++i)
{
int a, b;
cin >> a >> b;
job[i] = P(a, b);
}
sort(job.begin(), job.end());
priority_queue<int> job_score;
ll ans = 0;
int job_index = 0;
for(int i = 1; i <= m; ++i)
{
while(job_index < n && job[job_index].first <= i)
{
job_score.push(job[job_index].second);
job_index++;
}
if (!job_score.empty())
{
ans += job_score.top();
job_score.pop();
}
}
cout << ans;
残りi日の時にできる最も報酬の多い仕事をするのが基本方針です。
ですが、それだけでは入力例 2のような場合に解くのが難しくなります。
問題文をそのまま受け取ると、残り日数をM日から1日まで減らしていくように読み取れます。
残り日数を減らしていくと選べる仕事が減っていき、考えるべき変数が残り日数, 仕事の期間, 報酬の3つになります。
逆に、残り日数を1日からM日まで増やしてみます。
すると、残り日数を増やしていくと選べる仕事が増えていき、残り日数と仕事の期間は考える必要がなくなります。
つまり、報酬のみを考えればいいです。
逆に考えると変数が1つになって考えやすくなりましたね。この方針なら解けそうです。
そしてこれが正しい考え方です。
今回は報酬の合計を最大化するので、選べる仕事のうち最も報酬が大きいものを選べば答えになります。
最大値だけわかればいいのでpriority_queue(heap)の出番ですね。
選べる仕事を抽出し、その報酬をpriority_queueに入れて計算すれば答えになります。
E - Coins Respawn
vector<int> to[2505];
vector<int> reverse_to[2505];
bool ok[2505];
bool reachableFrom1[2505];
bool reachableFromN[2505];
void dfs(int v) {
if (reachableFrom1[v]) return;
reachableFrom1[v] = true;
for(const auto& u : to[v]) dfs(u);
}
void dfs_reverse(int v) {
if (reachableFromN[v]) return;
reachableFromN[v] = true;
for(const auto& u : reverse_to[v]) dfs_reverse(u);
}
void solve() {
fill(ok, ok + 2505, false);
fill(reachableFrom1, reachableFrom1 + 2505, false);
fill(reachableFromN, reachableFromN + 2505, false);
int n, m, p;
cin >> n >> m >> p;
vector<Edge> edges;
vector<int> dist(n, INF);
dist[0] = 0;
for(int i = 0; i < m; ++i) {
Edge edge;
cin >> edge.from >> edge.to >> edge.cost;
edge.from--;
edge.to--;
edge.cost -= p;
edge.cost *= -1; // コストを反転させて最短経路問題を解けば、最長経路になる
edges.emplace_back(edge);
to[edge.from].emplace_back(edge.to);
reverse_to[edge.to].emplace_back(edge.from);
}
dfs(0);
dfs_reverse(n - 1);
for(int i = 0; i < n; ++i) ok[i] = reachableFrom1[i] & reachableFromN[i];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
Edge e = edges[j];
if(!ok[e.to]) continue;
if(!ok[e.from]) continue;
if (dist[e.to] > dist[e.from] + e.cost) {
dist[e.to] = dist[e.from] + e.cost;
if (i == n - 1) {
cout << -1;
return;
}
}
}
}
cout << max(dist[n - 1] * -1, 0);
}
長いです。。。行数をおさえるためにすこし整形しました。
青difficultyの問題です。
あまり多く解いたことはありませんが、青difficultyの問題は長いものが多い印象です。慣れなきゃ。
この問題について･･･
・始点が決まっています。
・グラフ上を移動するたびに報酬がもらえて、最後に移動した回数だけpが引かれます。
ただ、最後にpを引く処理は移動中にしても結果は同じです。
つまり、各枝の報酬から先にpを引いても大丈夫です。この時に負の値が出てきます。
・閉路が存在して報酬が無限に大きくなります。
・報酬を最大化する問題ですが、報酬の正負を反転すれば報酬を最小化する問題になります。
つまり最短経路問題です。
長くなりましたが、この問題は「負閉路あり負数重み付き有向グラフの単一始点最短経路問題」に帰着できます。
つまりベルマンフォード法ですね。使ったのは今回が初めてです。
ただ、ここで終わらないのが青difficultyというか、それだけでは解けません。
始点と終点の間に負閉路があった場合には-1を出力するのですが、その検出はベルマンフォード法ではできません。
（始点と終点に関係なく負閉路があるかは検出できます。）
その検出を先にDFSでやります。
dfs(0);
dfs_reverse(n - 1);
の部分ですね。
始点と終点の両方から到達できない点について、ベルマンフォード法の処理をさせないようにします。
ここまでやってACです。長かった。
できるひとは「おっ、ベルマンフォードか」「でも閉路がちょっと良くないな」「始点と終点からdfsするか」
と一瞬でなるのでしょうか。その高みにいきたいです。これはその高みに続く一歩ですね。
以上です。ありがとうございました。