All Articles

ARC 108 振り返り

結果

結果としては2完1100くらいパフォーマンスがでて+30くらいレーティングが上がった。

各問の復習

A

A - Sum and Product

N+M=S,N×M=PN + M = S, N \times M = P

見抜くまでに時間がかかったが、片方を移行してもう一方に代入すると変数が一つになる。

(SM)M=P(S-M)M = P あとは、sqrt(P)の間でMを探して完了。

B

Abbreviate Fox

foxという文字を取り除いていくと最後何文字になるかを出力する。

紙に書いてシュミレーションしてみるとスタックをもちいて解けそうだということに気がついたので実装して終了。

データ構造をいち早く見つけられたのは良かった。

C

Keep Graph Connected

深さ優先探索を使えば解けそうだと考え実装してみたがうまくいかなかった。

  • 全てのケースで連結にできる
  • 番号割り振りのアルゴリズム

あたりを思い付けなかったのが敗因。

first ACの人の実装を参考にして振り返りしてみた。

先頭から順に割り振っていくと親は必ず番号を持っていることを利用してうまく番号を付けていく。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD = 1000000007;
const long long INF = 1LL << 60;

const int N = 200200;
vector<pair<int, int>> g[N];
int a[N];
int n, m;

void dfs(int v) {
  for (pair<int, int> e : g[v]) {
    int u = e.first;
    int c = e.second;
    // 探索できているなら飛ばす
    if (a[u] != 0) continue;

    // 探索できていないなら重みcと現在のノードの
    // 番号の関係を調べる
    // 等しいのであれば次のノードには+1をしたものを記録する
    // 等しくなければ重みを番号とする
    if (a[v] == c) {
      a[u] = c % n + 1;
    } else {
      a[u] = c;
    }
    // 繰り返し
    dfs(u);
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> m;

  for (ll i = 0; i < m; i++) {
    int u, v, c;
    cin >> v >> u >> c;
    // 無効グラフ
    // 重みはpairで保存
    g[v].push_back(make_pair(u, c));
    g[u].push_back(make_pair(v, c));
  }
  // 開始地点は1に初期化  
  a[1] = 1;
  dfs(1);
  for (int i = 1; i <= n; i++) {
    cout << a[i] << endl;
  }
  return 0;
}

頑張って考察すれば解けそうだった。

感想

精進はできていないのでせめてコンテストくらいは毎週出る予定。水色目指して頑張る。