horoyoisawaのゴミ箱

いろいろ書きます

ブラッドウェブみたいなやつ作りたい。

ポエム

（注）これはポエムです。お気をつけてお読みください。

デッドバイデイライトっていうゲーム知ってますか。

非対称の対戦ゲームでサバイバー4人とキラー1人が対戦するゲームです。サバイバーはキラーから逃げることが勝利条件、キラーはサバイバーをなるべく多く屠ることが勝利条件です。

一つの対戦の中で、サバイバー・キラーどちらもパーク(perk)という特殊な能力を4つだけ選んで使うことができます。使うパークは対戦の前に選択します。もう一つアドオンというのもありますが、それもパークと似たような機能を果たします。

そのパークやアドオンというのは、ゲームを始めたばかりだと3つほどしか選択肢がありません。新しいパークを獲得するためには、ゲームを何回もプレイする必要があります。具体的には一つの対戦ごとにプレイヤーのパフォーマンスに応じてブラッドポイントというポイントをプレイヤーは獲得します。獲得したポイントを使って新しいパークやアドオンを取得するというのが通常の流れです。まあポケモンで言うレベル上げ見たいなもんです。

その新しいパークやアドオンを取得する上で出てくるのがブラッドウェブ。蜘蛛の巣上に新しく取得できるパークやアドオンが広がっていて、その中から自分がゲットしたいパークをブラッドポイントを消費して選択して行きます。

具体的には下のリンクから見てください。

www.youtube.com

具体的にブラッドウェブがどんな機能を果たすのかはここでは問題にしません。僕がここで強調したいのがブラッドウェブのデザイン最高じゃね？？と言うことです。

何で好きなのかって言うと、僕個人がグラフがすごい好きだからです。グラフの形をしているものに目がありません。蜘蛛の巣はループがあるので木構造ではありません。単なる無向グラフです。

これを実装したいと言うのがこのポエムの趣旨です。

でなんか良い題材ないかなーと思っていたところ、AtCoder Problemsの問題をグラフの形にしたいなぁなんて思ったりしてます。

AtCoder Problemsの表示形式は今のところコンテストごとの表形式です。それも全然ありなのですが、グラフ形式で表示したい。問題同士の繋がりを見たい。

もっといってしまうとAtCoder ProblemsとAtCoder Tagsの融合したものを作りたいといった感じです。AtCoder Tagsにのっとって問題をクラスタリングして、そのクラスタリングした問題を難しさごとにレベル分けする。一つのレベルに大体10~20くらいの問題を載せて、ACした問題に関しては緑、WAした問題に関しては黄色にしたい（これはAtCoder Problemsと全く一緒）。

まあ単に動的にグラフが作りたいと言うことです。それをヴィジュアライズしたい。

と言うポエムでした。

以上。

一つだけWAが取れない。。(AtCoder Beginner Contest 123 D - Cake 123)（Resolved)

誤答コード ABC Resolved

なぜが一つだけWAが取れない。さらに通っていないのが入力サンプルに置いてだと思われる。目視自分のプログラムの出力と答えが一致しているが、ジャッジにはそうではないと判断された。以下その提出リンクとスクリーンショット。

 

続きを読む

AtCoder Beginner Contest 160に参加した話。

ABC 参加記

AtCoder Beginner Contest160に参加。

結果は以下。

atcoder.jp

  • Ranking: 885th / 9745
  • Performance: 1594
  • Rating: 815 → 929

F問題解きたかった。

A - Coffee

3文字目と4文字目が等しくかつ5文字目と6文字目が等しい時にYes、そうでなければNoを出力する問題。1:15でAC。

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
int main() {
  string s;
  cin >> s;
  if(s[2] == s[3] && s[4] == s[5]) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

B - Golden Coins

現在Xを持っていて両替をすることができる。500円硬貨でhappiness1000、5円硬貨でhappiness5をゲットできる。hapipnessを最大化する。

3:12でAC。

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
int main() {
  long long x;
  cin >> x;
  cout << x / 500 * 1000LL + x % 500 / 5LL * 5 << endl;
  return 0;
}

C - Traveling Salesman around Lake

湖の周りに家が立っている。どこかの家から出発して全ての家を周り切りたい。最短経路を求めよ。

湖の周の長さをKとする。家間の距離で最も長い距離をd_{max}とすると、K-d_{max}が求める答えである。

7:24でAC。

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
int main() {
  ll k, n;
  cin >> k >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  ll ma = 0;
  for(int i=0;i<n-1;i++) chmax(ma, a[i+1] - a[i]);
  chmax(ma, a[0] + k - a.back());
  cout << k - ma << endl;
  return 0;
}

D - Line++

1からNの頂点が一列に並んでおり、隣通りの頂点は辺で結ばれている。加えて頂点Xと頂点Yも辺で結ばれている。

この時、1 \leq k \leq N-1を満たす各kに対して以下の問に答えよ。

  • 最短距離がkの頂点のペアの数を出力する。

最初どう解くかを考えていて最初にN回ダイクストラを書けば良いと思ったがダイクストラを書けないという絶望に気づいた。絶望しても仕方ないので、他の方法を考える。幅優先探索とかどうだろとか色々考えて、結果もっと簡単にいくのではと考えた。

予想通り簡単な方法が見つかった。頂点iから頂点jに最短でいく方法は以下の3通りに限られる。

  • 素直に頂点iからjに行く方法。
  • まず頂点Xに行き、頂点Yに行く。頂点Yから頂点jに向かう。
  • まず頂点Yに生き、頂点Xに行く。頂点Xから頂点jに向かう。

この3つのうちの最小値がわかれば良い。

この結果をmapでもvectorでもに格納しておき、最後に順に出力する。

29:36にAC。

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
int main() {
  int n, x, y;
  cin >> n >> x >> y;
  x--;y--;
  vector<vector<int>> dis(n, vector<int>(n, 100100100));
  rep(i, n) {
    for(int j=i+1;j<n;j++) {
      int d = j - i;
      int dd = abs(i - x) + 1 + abs(j - y);
      int ddd = abs(i - y) + 1 + abs(j - x);
      vector<int> dist({d, dd, ddd});
      dis[i][j] = *min_element(dist.begin(), dist.end());
    }
  }
  vector<int> ans(n);
  for(int i=0;i<n;i++) {
    for(int j=0;j<n;j++) {
      if(dis[i][j] == 100100100) continue;
      ans[dis[i][j]]++;
    }
  }
  for(int i=1;i<n;i++) {
    cout << ans[i] << endl;
  }
  return 0;
}

E - Red and Green Apples

赤いリンゴがA個、緑のリンゴがB個、そして無色のリンゴがC個ある。それぞれに美味しさのパラメータ付与されている。無色のリンゴに関しては赤が緑の色を塗ることができる。

赤色のリンゴをX個、緑のリンゴをY個とった時、手に入れたX+Y個のリンゴの美味しさの合計を最大化したい。最大値を求めよ。

色々やり方あると思うが、僕が取った方法を紹介する。

既に赤色のリンゴのうち選ばれる可能性があるのは美味しさに関して降順に並べて、上からX個のリンゴまでである。同様に緑のリンゴも上からY個を考えれば良い。

無色のリンゴをどのように入れるかというのが問題。結論貪欲にやれば良い。

つまり、赤色のリンゴの中で最も美味しさの小さいものと緑のリンゴの中で最も美味しさの小さいものを比較し、その小さい方と無色のリンゴの中で最も美味しさパラメータの高いリンゴを比較する。もし前者の方が大きければ無色のリンゴをわざわざ使う必要はない。後者の方が大きい時は、無色のリンゴと小さい方をスワップする。

これをスワップの必要がなくなるまでもしくは無色のリンゴがなくなるまで続ける。

最後に残った合計X+Yのリンゴの美味しさの合計を求めれば良い。

49:40でAC。

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
int main() {
  ll x, y, a, b, c;
  cin >> x >> y >> a >> b >> c;
  vector<ll> p(a);
  vector<ll> q(b);
  vector<ll> r(c);
  rep(i, a) cin >> p[i];
  rep(i, b) cin >> q[i];
  rep(i, c) cin >> r[i];
  sort(p.rbegin(), p.rend());
  sort(q.rbegin(), q.rend());
  sort(r.begin(), r.end());
  vector<int> tp(x);
  vector<int> tq(y);
  rep(i, x) tp[i] = p[i];
  rep(i, y) tq[i] = q[i];
  int pback = x-1;
  int qback = y-1;
  int voi = c-1;
  while(voi != -1 && (pback != -1 || qback != -1)) {
    if(pback == -1) {
      if(tq[qback] >= r[voi]) break;
      else {
        tq[qback] = r[voi];
        voi--;
        qback--;
      }
    }
    else if(qback == -1) {
      if(tp[pback] >= r[voi]) break;
      else {
        tp[pback] = r[voi];
        voi--;
        pback--;
      }
    }
    else {
      ll v = r[voi] - tp[pback];
      ll u = r[voi] - tq[qback];
      if(v <= 0 && u <= 0) break;
      if(v < u) {
        tq[qback] = r[voi];
        qback--;
      }
      else {
        tp[pback] = r[voi];
        pback--;
      }
      voi--;
    }
  }
  ll ans = 0;
  rep(i, x) ans += tp[i];
  rep(i, y) ans += tq[i];
  cout << ans << endl;
  return 0;
}

最後の処理で一個ずつ見ていっているけれど、本当はもっと簡単な方法がある。Editorialを見てもらえれば分かるけれど、X+Y個＋無色のリンゴC個を一つの配列にまとめてソートして上からX+Y個が答えになる。無色のリンゴには適当に色を塗る。

このE問題は大体の人が解けてそう。スピードで相当差が出る問題。実際E問題まで解けていて最速の人はパフォーマンス2000を超えていた。そのデータは以下。

atcoder.jp

  • Ranking：328th / 9745
  • Performance: 2029

14分でE問題まで解けるのはすごいわ。

F - Distributing Integers

わからんかった。

全体を通して

まあ悪くはなかった。E問題まで解くことはできたし、さらに間違えることがなかったのは良かった。反省点は以下。

  • 超手震えるやばい。慣れるしかない。。
  • コンパイルするコマンドを何回も打っていて時間の無駄。もっと短縮する方法あるはず。
  • 違うファイルでやっていたからか開くファイルを間違えたりしていた。いっそのこと同じファイルでやるのが良いかもしれない。
  • HHKBの調子が悪く、Mac内臓のキーボードを使用した。突然キーボードを変えるのはよくない。ずっと内蔵キーボードを使い続けるか、もしくは新しいキーボードを買うのが良いかもしれない。
  • コンテスト中に新しいアプリの構想が思いついてかなり注意散漫になってた。コンテストに集中。

では。

AtCoder Regular Contest 009 B - otogi no kuni no takahashi kun 誤答コード(Resolved)

ARC Resolved

定番やらかしコードーーーー。

今回も間違い探しをしていく。（まだ発見していない）

以下問題と提出コード。見たい人は見て。

問題

atcoder.jp

提出コード

#include <bits/stdc++.h> using namespace std; using P = pair<int, int>; #define chmin(i, j) i = min(i, j); #define chmax(i, j) i = max(i, j); vector<int> b(10); bool custom(int p, int q) { string s = to_string(p); string t = to_string(q); if(s.size() < t.size()) return true; else if(s.size() > t.size()) return false; else { bool res = true; for(int i=0;i<s.size();i++) { int j = s[i] - '0'; int k = t[i] - '0'; if(i == j) continue; else if(b[j] < b[k]) { res = true; break; } if(b[j] > b[k]) { res = false; break; } } return res; } } int main() { for(int i=0;i<10;i++) { int num; cin >> num; b[num] = i; } int n; cin >> n; vector<int> a(n); for(int i=0;i<n;i++) cin >> a[i]; sort(a.begin(), a.end(), custom); for(int i=0;i<n;i++) cout << a[i] << endl; return 0; }

追記用

もしわかったら追記する。

(2020/04/10)

if(i == j) continue→if(j == k) continueに修正。結果AC。

AtCoder Beginner Contest E - Sequence Decomposing 解いた感想

ABC

問題はこちら。

素直にやれば解ける問題。

atcoder.jp

解法

setでデータを管理する。データの中身は同じ色で塗られている塔の中で高さが最大のもの。

新しく塔i（高さh_i）に色を塗る（setに追加する）ことを考える。色を増やさない方が良いので、自分より高さの小さい塔を探し出し、その塔の色と同じ色をiに塗れば良い。

例えばset: {1, 3, 6, 2, 10}で新しく8の塔に色を着けるとすると、候補になるのは{1, 2, 3, 6}である(10は8より大きいので同じ色を使うことができない）。この4つの候補のうちどれと同じ色を使ってもルール上良いのだが、最適なのは6と同じ色を塗ることである。

例えば1と同じ色を塗ってしまうと、setは{8, 3, 6, 2, 10}と更新される。このあと高さ2 の塔に色つけをしようとすると、新しい色を使わなければならない。（setの最大値が2だから）。

これは最適ではない。塔iを6と同じ色を塗ると、{1, 3, 8, 2, 10}と更新され、高さ2の塔に色を付けようと思ったときに高さ1の塔と同じ色を使うことができる。結果色を使う総数は増えない。

そうなると色の候補の中で最も最大値が大きい塔と同じ色を塗るのが良いことがわかる。候補の最大値の求め方はset.lower_boundでh_i以上の要素の中で最小の要素のイテレータを取得、その直前の要素が求めるものである。(prev()で取得可能)

候補が0個だったときには(lower_boundで取得したイテレータが先頭のイテレータだった場合）、すでに使った色と同じ色を使う事はできないのでsetの要素として新しくh_iを追加する。

lower_boundはサイズに対して対数時間で計算できるので、十分早い。少なくとも今回の問題に関しては問題ない。

提出コード

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin >> a[i];
  multiset<int> s;
  for(int i=0;i<n;i++) {
    if(i == 0) s.emplace(a[i]);
    else {
      auto it = s.lower_bound(a[i]);
      if(it == s.begin()) s.emplace(a[i]);
      else {
        s.erase(prev(it));
        s.emplace(a[i]);
      }
    }
  }
  cout << s.size() << endl;
}

 Editorialに面白いことが書いてあった気がする。時間があれば追記予定。

M-Solutions プロコンオープン D - Maximum Sum of Minimum 解いた感想

企業コン

問題はこちら。

atcoder.jp

最初、次数の大きい頂点にCの大きい値を割り振ればええやろと適当解放を思いつき見事WA。アホ。

解法

結論を言ってしまうと深さ優先探索をして、その順にCを大きい値から割り振っていく。

Cの最大値をC_{max}とすると、一つの辺にC_{max}を書き込む事はできない。

次に大きい値をC'_{max}として、C'_{max}を辺に書き込むことができるかを考えると、C_{max}の値を持つ頂点とC'_{max}の間の辺に書き込むことができる。この作業を続けると、全ての辺に書き込まれた値の合計値はC_{total} - C_{max}になる。(C_{total}はCの値の合計値）

これが最大値になる理由は自明っぽい。正直いうと説明するのが面倒。詳しく知りたい方は以下のリンクからEditorialを見て。

https://img.atcoder.jp/m-solutions2019/editorial.pdf

 

最大値を求める計算のところでとんでもなく面倒な計算をしているのは許して。提出したコードは以下。

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
int id = 0;
vector<int> c;
vector<vector<int>> g;
vector<int> seen;
vector<int> value;
void dfs(int node) {
  if(seen[node]) return;
  seen[node] = 1;
  value[node] = c[id];
  id++;
  for(auto& next : g[node]) {
    if(!seen[next]) dfs(next);
  }
}
int main() {
  int n;
  cin >> n;
  g.resize(n);
  c.resize(n);
  seen.resize(n);
  value.resize(n);
  for(int i=0;i<n-1;i++) {
    int a, b;
    cin >> a >> b;
    a--;b--;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  for(int i=0;i<n;i++) cin >> c[i];
  sort(c.rbegin(), c.rend());
  dfs(0);
  long long m = 0;
  for(int i=0;i<n;i++) {
    for(auto& el : g[i]) {
      m += min(value[i], value[el]);
    }
  }
  cout << m / 2 << endl;
  for(int i=0;i<n;i++) cout << value[i] << endl;
  return 0;
}

AtCoder Beginner Contest 138 E - Strings of Impurity 誤答コード(Resolved)

ABC 誤答コード

問題はこちら。

atcoder.jp

誤答コード

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int main() {
  string s, t;
  bool yes = true;
  cin >> s >> t;
  int n = s.size();
  s += s;
  vector<vector<int>> ss(26);
  vector<vector<int>> tt(26);
  for(int i=0;i<s.size();i++) {
    ss[s[i]-'a'].emplace_back(i);
  }
  for(int i=0;i<t.size();i++) {
    tt[t[i]-'a'].emplace_back(i);
  }
  for(int i=0;i<26;i++) {
    if(tt[i].size() != 0 && ss[i].size() == 0) yes = false;
  }
  if(!yes) {
    cout << -1 << endl;
    return 0;
  }
  vector<vector<int>> next(n, vector<int>(26));
  for(int i=0;i<n;i++) {
    for(int j=0;j<26;j++) {
      if(ss[j].size() == 0) next[i][j] = INT_MAX;
      else {
        auto it = upper_bound(ss[j].begin(), ss[j].end(), i);
        next[i][j] = *it - i;
      }
    }
  }
  long long ans = 0;
  for(int i=0;i<t.size();i++) {
    int id = t[i] - 'a';
    int pos = ans % n;
    ans += next[pos][id];
  }
  cout << ans + 1LL << endl;
}

ところどころWAになっていてデバッグがしづらい。回収する誤答コードが増えてきたなぁ。早いところ回収せねば。。

追記用

（2020年3月27日追記）

最後のfor文のところでi==0の時を例外として処理するのを忘れていた。i==0の時最初の地点の文字も候補として含めて良い。しかし上のコードでは一番初めの文字が除外されている。それを修正しAC。