AtCoder Beginner Contest 137 - zeronosu77108’s blog

はい． AtCoder Beginner Contest 137 です

A,B,C の3完でした．
D難しかった…

f:id:zeronosu77108:20190813165414p:plain

C までが割りと早かったということもあり，パフォーマンスは水色手前でした
（難しくてみんな D 解けなかったのかな？）

今回で，緑色になれました！

f:id:zeronosu77108:20190813165411p:plain

A - +-x
B - One Clue
C - Green Bin
D - Summer Vacation
E - Coins Respawn
まとめ

A - +-x

問題文

そのまま最大値取るだけですね．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  int a,b;
  int ans = INT_MIN;
  cin >> a >> b;

  ans = max(ans,a+b);
  ans = max(ans,a-b);
  ans = max(ans,a*b);

  cout << ans << endl;
}

B - One Clue

問題文

-1000000 〜 1000000 のうち，連続して $K$ 個の石が黒く塗られているので，
その塗られている可能性がある座標を出力して下さいという問題．ヒントとして座標 $X$ が黒だと教えられます．

$X$ が左端のパターンと右端のパターンがあるので， $X-K$ から $X+K$ まで出力したら良いですね． -1000000 とか 1000000 付近は値を考慮する必要がありますが，今回は， $1 \leq K \leq 100$ と $0 \leq X \leq 100$ なので考慮する必要はないです．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  int k,x;
  cin >> k >> x;
  k--;

  for(int i=x-k; i<=x+k; i++) {
    cout << i << (i==x+k ? "\n" : " ");
  }
}

C - Green Bin

問題文

アナグラムになるような組み合わせがいくつあるかという問題．
アナグラムになるかどうかは，出現するアルファベットによって一意に決まる形に変換してやれば良いですね．

まぁ，一番簡単なのはソートで，ソートした後にそれを数え上げれば良いです．

数え上げて $_ 3 C _2$ みたいなことしても良いんですが， $i$ 番目が見つかったときに，他のやつとの組み合わせが増えるので， $i-1$ を足してあげれば良いです．

$_ 1 C _ 2 = 0$ ， $_ 2 C _ 2 = 1$ ， $_ 3 C _ 2 = 3$ ， $_ 4 C _ 2 = 6$ を逐次で加算していく感じですね．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  int n;
  long ans=0;
  cin >> n;
  map<string, int> ex;

  for (int i=0; i<n; i++) {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    if (ex[s]) ans+=ex[s];
    ex[s]++;
  }

  cout << ans << endl;
}

D - Summer Vacation

問題文

これ，考え方はあっていたのですが， TLE を大量に出してしまい時間ないに解けませんでした．
priority queue を使うんですね．

考え方はあっていただけに悔しい…
もっとデータ構造勉強しなくては！！！

考え方としては， $m-1$ 日目に仕事をして $m$ 日目までに給料をもらえるものは $A=1$ の物しかないので，その中から最大の物を選ぶ．
$m-2$ 日目に仕事をして $m$ 日目までに給料をもらうには， $A=1$ のものと $A=2$ のものから最大の物（ $m-1$ 日目の仕事とは別の物）という風に決めいく感じです．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <queue>

using namespace std;

typedef pair<long,long> P;

int main() {
  long n,m;
  long ans=0;
  cin >> n >> m;
  vector< vector<long> > jobs(m+1);

  for (int i=0; i<n; i++) {
    int a,b;
    cin >> a >> b;
    if(a>m) continue;
    jobs[a].push_back(b);
  }

  priority_queue<int> pq;
  for (int i=1; i<=m; i++) {
    for (auto j : jobs[i]) pq.push(j);

    if(pq.empty()) continue;

    ans += pq.top();
    pq.pop();
  }

  cout << ans << endl;
}

E - Coins Respawn

問題文

解説聞いたあとに自分で書いてみました．

この問題は，負の辺を持つグラフの最短経路問題に落とし込むことができるようです．負辺を持つグラフの最短経路問題は Bellman-Ford アルゴリズムで解くことができるらしく．

聞いたとおりに実装してみました．
（プログラムは解説とは少し違うかもしれない）

書いてみるとそんなに難しくなかったので，コンテスト中に E まで解けるようになりたいですね．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

void dfs(int v, vector<vector<int>>& to, vector<bool>& f) {
  if(f[v]) return;
  f[v] = true;
  for (auto u : to[v]) {
    dfs(u,to,f);
  }
}

int main() {
  int n,m,p;
  int ans = -1;
  cin >> n >> m >> p;
  vector<vector<int>> to(n+1);
  vector<vector<int>> ot(n+1);
  vector< tuple<int,int,int> > edges;

  for (int i=0; i<m; i++) {
    int a,b,c;
    cin >> a >> b >> c;
    c = -1 * (c-p);
    to[a].push_back(b);
    ot[b].push_back(a);
    edges.emplace_back(a,b,c);
  }

  // 1 からたどり着けないやつと Nにたどり着けないやつは考慮する必要が無い
  vector<bool> from1Flag(n+1,false);
  vector<bool> toNFlag(n+1,false);
  dfs(1,to,from1Flag);
  dfs(n,ot,toNFlag);
  vector<bool> ok(n+1,false);
  for (int i=1; i<=n; i++)
    ok[i] = from1Flag[i] && toNFlag[i];

  // Bellman-Ford アルゴリズム
  vector<long> d(n+1,INT_MAX);
  d[1] = 0;
  bool updated = true;
  int step = 0;

  while(updated) {
    updated = false;
    step++;
    if(step >= n+1) break;

    for(int i=0; i<m; i++) {
      int a,b,c;
      tie(a,b,c) = edges[i];
      if (!ok[a]) continue;
      if (!ok[b]) continue;

      if (d[a]+c < d[b]) {
        updated = true;
        d[b] = d[a]+c;
      }
    }
  }

  if(step <= n) ans = max(0, (int)(-1*d[n]));
  cout << ans << endl;
}