読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

ABC037-D問題

ABC 競技プログラミング

abc037.contest.atcoder.jp

解説通りf(y, x) を再帰的に求めて全てのf(y, x)を足す感じで実装しました。定番のメモ化再帰という印象の問題でした。

ABC038-D問題

ABC 競技プログラミング

abc038.contest.atcoder.jp

解説読んでもわからなかったBainary Indexed Tree(BIT)ってなんだよ!ってのとソートの方法を指定する方法についてのメモ。
BITについては以下のスライドが分かりやすかったです。和ではなくその区間の最大値を保存することである区間の最大値はO(logN)で求められます。BITは1からaまでの区間についての情報を保持していますが、区間[a, b]について考えたいならセグメントツリーのほうが便利そうです。
http://hos.ac/slides/20140319_bit.pdf
hについて昇順でhが等しかったらwの降順になるようにするソートが必要です。以下のサイトを参考にソートの比較用の関数をつくることで実装しました。他にも構造体で > を定義することで行ったり、ラムダ式を用いる方法でもできそうです。
C++(ソートの補足) - アルゴリズム講習会

ABC040D

ABC 競技プログラミング

abc040.contest.atcoder.jp

UnionFindをある程度理解したあとだったので解法が何をやっているのかは割と早く理解できましたが、実装に手間取ってしまいました… 年をキーとして2つの値をもつ組を降順にソートする必要があります。最終的にvector< vector< int > > を使って実装しました。あとは頂点の値を1マイナスするのを忘れていたり、初期化忘れてたりで時間を溶かしたので本番で無駄に時間かけないようにしたいです。

ABC041D

ABC 競技プログラミング

abc041.contest.atcoder.jp

解説を読んでも満点解法がなかなかわからず苦労したのでそのメモです。

 まずトポロジカルソートは有向辺が全て1方向へ向くようにソートをソートをすることです。入力例1についてトポロジカルソートを行ってみると以下の2通りになります。
f:id:ferin_tech:20161226024842p:plain
このトポロジカルソートの種類を求める問題と考えることができます。
 解説のように漸化式を計算することでなぜトポロジカルソートができるか考えます。頂点vをもっとも右に置くことができれば、頂点vを除いた部分集合について同じことを再帰的に行うことでトポロジカルソートとなります。部分集合Sの中でもっとも右における頂点vとは vからS-{v} への有向辺がないことと同義です。その部分集合の他の頂点に対する有向辺があると左向きの有向辺が生じてしまうためトポロジカルソートの条件を満たせないということです。
 このような集合を含んでいる漸化式を扱うときにはBitDPがよくある手段(らしい)です。

頂点 1 2 3 4
   0 0 1 0  S = {3}
   1 1 0 1  S = {1, 2, 4}

といったようにビットが1の部分の頂点を含んでいる部分集合と対応させることで集合を表現します。0から2^Nまで小さい方から順に計算していくことで答えを求めることができます。これをコードで実装します。

以下蛇足。bit演算に慣れていなかったこともあってBitDPの実装に時間をかけてしまった。集合を扱うときは鉄板の方法っぽい。あとN<=16とかでO(N!)だと間に合わないけどO(2^N)だと間に合うときはBitDPを使う方法のことが多いらしい。Nの制約から使うアルゴリズムが想像つくようになってきた。

Atomで使ってるパッケージについて

Package

 あとで忘れて困る未来が浮かんだので忘備録として書いておくことにしました。C++用にパッケージをいじってます。
 OS: Windows10 64bit
 コンパイラ: MinGW(GCC)

atom-beautify

 オートフォーマットしてくれるパッケージです。整形にClang-formatを使ってるのでClangのインストールが必須。
 以下のやり方でインストールしました。
windowsでatom-beautifyを使おうとしてハマったこと - Qiita
LLVM Clang の Windows へのインストールと使い方 | プログラマーズ雑記帳

autocomplete-clang

 補完をしてくれるパッケージです。autocomplete-plusが前提として必要ですが最近のなら標準で入ってます。これもClangのインストールが必須です。

linter, linter-gcc

 静的コード解析、つまりエラーの位置をAtomのエディタ上に出してくれるパッケージです。いちいちコマンドプロンプトコンパイルしてエラーメッセージと行数を照らし合わせてなんて手間はもういりません。linter は linter-gccの前提として必要です。linter-gccの設定にgccやg++のパスを入れる必要があります。MinGWでデフォルトだと C:\MinGW\bin\g++.exe です。

file-icons

 ツリーやタブのアイコンを拡張子に合わせて変えてくれるパッケージです。一目でファイルの種類がわかるので気に入ってます。

highlight-line

 カーソルが入ってる行をハイライトしてくれるパッケージです。これでカーソルを見逃す心配はありません。

japanese-menu

 日本語化してくれるパッケージです。

minimap

 エディタの右側にコードの全体図を表示してくれるパッケージです。

minimap-autohide

 minimapを必要がない時は隠してくれるパッケージです。コード書いてる時は使わないので消えててくれるので便利です。

Design

font

 Ricty Diminished Discordを使ってます。環境設定にフォント名を入れる欄があるのでそこに入力して再起動すればフォントが切り替わります。Ricty Diminished Discordのインストールは以下を参考に行いました。
見やすいプログラミング用フォント「Ricty Diminished」をWindowsにインストールしてSublime Textで利用する方法

Theme

 インターフェーステーマはAtom Dark Slim、シンタックステーマはMonokaiを使っています。

style.less

 選択範囲が灰色で見づらかったので以下のサイトを参考に直しました。
Atomで選択範囲の背景色を見やすく変更する – nocorica
 コメントの色が灰色で同様に見づらかったのでstyle.lessに以下の記述を追加して暗い黄緑のような色に変更しました。

atom-text-editor::shadow {
  .comment {
    color: fade(greenyellow, 40%);
  }
}

ABC049D

ABC 競技プログラミング

abc049.contest.atcoder.jp

自力では手も足も出なかったのでeditorialと解説放送を参考に実装しました。
youtu.be
https://youtu.be/jvAX9Z7beLg

グラフの連結を管理するために、グループ分けを管理するためのデータ構造であるUnion-Find木を使います。
道路での連結を表すUnion-Find木と電車での連結を表すUnion-Find木をそれぞれ用意し管理します。
Union-Find木では連結している頂点同士では根となるノードが同じになります。
よって、道路と電車双方で連結している頂点はその頂点の根がそれぞれ同じとなります。
そのような頂点の数を数えることで両方で連結している頂点数を求めることができます。

GCCとclang間違えてCE出したり、DじゃなくてAに提出したりしてたので本番でやらかさないよう気をつけたい。
あと同じpairを数えるのにcount使ったらTLEだった。よくよく考えたらO(N^2)だし当たり前だった。

ABC030を解いてみた

ABC 競技プログラミング

abc030.contest.atcoder.jp

A問題

 if文で比較しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359

int main(void)
{
  double a, b, c, d;
  cin >> a >> b >> c >> d;
  if(b/a > d/c) cout << "TAKAHASHI" << endl;
  else if(b/a < d/c) cout << "AOKI" << endl;
  else cout << "DRAW" << endl;

  return 0;
}

B問題

 短針が5分刻み以外にも移動することと小さい方の角度を取得することに気をつけて実装しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359

int main(void)
{
  int n, m;
  cin >> n >> m;
  n %= 12;

  double angle = abs(n*30 + m*0.5 - m*6);
  angle = min(angle, 360-angle);

  cout << fixed << setprecision(6) << angle << endl;

  return 0;
}

C問題

 乗れる中で最も早い飛行機に乗る貪欲で解きました。計算量はO(n)のはずです。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define N_MAX 100000
#define M_MAX 100000

int main(void)
{
  int n, m, x, y;
  cin >> n >> m;
  cin >> x >> y;

  ll a[N_MAX], b[M_MAX];
  for(int i=0; i<n; i++) {cin >> a[i];}
  for(int i=0; i<m; i++) cin >> b[i];

  // true ならAにいる
  bool isA = true;
  int ans=0, i=0, j=0;
  ll now=0;
  while(i < n && j < m) {
    if(isA) {
      // a[i]がnow以上になるまで
      while(a[i] < now) {
        i++;
        //乗れる飛行機がもうない
        if(i == n) {cout << ans << endl; return 0;}
      }
      now = a[i] + x;
      isA = false;
    } else {
      // b[j]がnow以上になるまで
      while(b[j] < now) {
        j++;
        // 乗れる飛行機がもうない
        if(j == m) {cout << ans << endl; return 0;}
      }
      now = b[j] + y;
      ans++;
      isA = true;
    }
  }

  return 0;
}

D問題

 10^10000ってlong longでも受け取れないしどうするんだ…?とか思って分からなかったので自力では部分点まで実装。

//部分点
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define MAX_N 100000

int main(void)
{
  int n, a, b[MAX_N];
  ll k;
  cin >> n >> a; a--;
  cin >> k;
  for(int i=0; i<n; i++) {cin >> b[i]; b[i]--;}

  //ループに入るまで
  bool toLoop[MAX_N] = {false};
  int c_num = a, toLoop_num = 0;
  vector<int> v_toLoop;
  while(true) {
    toLoop[c_num] = true;
    toLoop_num++;
    v_toLoop.push_back(c_num);
    c_num = b[c_num];
    if(toLoop[c_num]) break;
    //cout << "toLoop_num:" << toLoop_num << " c_num:" << c_num << endl;
  }

  //ループ中
  bool loop[MAX_N];
  int loop_num = 0;
  vector<int> v;
  while(true) {
    loop[c_num] = true;
    loop_num++;
    v.push_back(c_num);
    c_num = b[c_num];
    if(loop[c_num]) break;
    //cout << "loop_num:" << loop_num << " c_num:" << c_num << endl;
  }

  if(toLoop_num > k) cout << v_toLoop[k]+1 << endl;
  else cout << v[(k-toLoop_num)%loop_num]+1 << endl;

  return 0;
}

 string型で入力を受け取って、桁ごとに計算することでMODを計算できる(by解説)で実装しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define MAX_N 100000

int main(void)
{
  int n, a, b[MAX_N];
  string k;
  cin >> n >> a; a--;
  cin >> k;
  for(int i=0; i<n; i++) {cin >> b[i]; b[i]--;}

  //ループに入るまで
  bool toLoop[MAX_N] = {false};
  int c_num = a, toLoop_num = 0;
  vector<int> v_toLoop;
  while(true) {
    toLoop[c_num] = true;
    toLoop_num++;
    v_toLoop.push_back(c_num);
    c_num = b[c_num];
    if(toLoop[c_num]) break;
    //cout << "toLoop_num:" << toLoop_num << " c_num:" << c_num << endl;
  }

  //ループ中
  bool loop[MAX_N];
  int loop_num = 0;
  vector<int> v;
  while(true) {
    loop[c_num] = true;
    loop_num++;
    v.push_back(c_num);
    c_num = b[c_num];
    if(loop[c_num]) break;
    //cout << "loop_num:" << loop_num << " c_num:" << c_num << endl;
  }

/*
  cout << "loop_num:" << loop_num << " toLoop_num:" << toLoop_num << endl;
  for(int i=0; i<toLoop_num; i++) cout << v_toLoop[i] << " "; cout << endl;
  for(int i=0; i<loop_num; i++) cout << v[i] << " "; cout << endl;
*/

  //kが6桁あればn<=10^5だし閉路に入る気がした
  if(k.size() < 7) {
    int num_k = stoi(k);
    int c_num = a;
    for(int i=0; i<num_k; i++) c_num = b[c_num];
    cout << c_num + 1 << endl;
    return 0;
  }

  ll k_mod_c = 0;
  for(int i=0; i<k.size(); i++) k_mod_c = (k_mod_c*10+k[i]-'0')%loop_num;
  while(k_mod_c < toLoop_num) k_mod_c += loop_num;

  c_num = a;
  for(int i=0; i<k_mod_c; i++) c_num = b[c_num];
  cout << c_num+1 << endl;

  return 0;
}