ARC#032 B:道路工事

未解決

22個あるケースのうち一つだけ通らないので謎だ…

#include <iostream>
#include <set>
using namespace std;

#define pb push_back 
#define MAX_N 1000000


int par[MAX_N]; // 親
int Rank[MAX_N]; // 木の深さ

void init(int n) {
  for (int i = 0; i <= n; i++) { 
    par[i] = i;
    Rank[i] = 0;
  } 
}

int find(int x) {
  if (par[x] == x) { return x;
  } else {
    return par[x] = find(par[x]);
  } 
}

void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;
  if (Rank[x] < Rank[y]) { par[x] = y;
  } else {
    par[y] = x;
    if (Rank[x] == Rank[y]) Rank[x]++;
  } 
}

bool same(int x, int y) {
  return find(x) == find(y);
}

int main(void){

  int N, M;

  cin >> N >> M;
  init(N);

  while(M--){
    int a,b;
    cin >> a >> b;
    unite(a,b);
  }

  set<int> s;
  for(int i = 1; i <= N; i++){
    s.insert(par[i]);
  }
  
  cout << s.size()-1 << endl;
  return 0;
}

ヨセフスの問題

Algorithm

ヨセフスの問題（ヨセフスのもんだい、英: Josephus problem）は、計算機科学および数学の理論的問題のひとつ。ジョセファスの問題とも。
n 人の人間が円を描くように並び、処刑されるのを待っている。最初の人をスキップし、さらに k-2 人をスキップし（つまり、k-1 人をスキップして k番目の人に到達する）、k番目の人を処刑する。そしてそこから、再度 k-1 人をスキップして k番目の人を処刑する。これを延々と続け（円は徐々に小さくなっていく）、最後に残った1人を釈放する。問題は、n と k が与えられたとき、起点をどこにしたら特定の人を最後まで残せるかである。

http://ja.wikipedia.org/wiki/%E3%83%A8%E3%82%BB%E3%83%95%E3%82%B9%E3%81%AE%E5%95%8F%E9%A1%8C

f(n,k)=(f(n-1,k)+k) mod n （ただし f(1,k)=0）

これを使って、And Then There Was Oneを解いた。ふつうにシュミレーションすると間に合わなかった。（工夫するといけるっぽいけど）

コーディングを支える技術

読書メモ

コーディングを支える技術 ~成り立ちから学ぶプログラミング作法 (WEB+DB PRESS plus)

コーディングを支える技術 ~成り立ちから学ぶプログラミング作法 (WEB+DB PRESS plus)

1章 言語を深く効率的に学ぶには

  • Rubyは0が真になる
  • false と nil 以外は真なだけ
  • 言語に依存しない知識を身につける
  • 歴史から学ぶ
  • 比較から学ぶ

2章 プログラミング言語を俯瞰する

  • ENIACはケーブルをつなぎ替えることでプログラミングしていた
  • EDSACが開発された
  • 紙テープ
  • FORTRANが登場
  • 「私の成果の大部分は怠惰から来ている」 - John Backus
  • 楽をする ≠ 手抜き
  • プログラマの三大美徳
  • 無精・短気・傲慢
  • PHPはWebサービスを楽にかけるが言語処理系を楽に書くことを目指していない
  • 何が楽になるかは言語によって異なる
  • 適材適所で良い道具を選ぼう

3章 文法の誕生

  • FORTH
  • スタックを使って処理
  • スタックマシンは現代でも使用されている
  • Java,Python,RubyなどのVMで
  • 構文木
  • Pythonはastライブラリで構文木を見れる
  • (前|中|後)置記法
  • 人間は中置記法に慣れている
  • FORTRANはこの慣れている記法で書けるように作られた
  • 構文解析器（パーサー）
  • 構文木を作るもの
  • 最初から完璧なものを作ろうととするな
  • 簡単なものでいいから作れ
  • そこから上達する
  • 文法ルールの競合
  • X vector>
  • O vector >
  • スペースを開けなければシフト演算子として解釈されてしまう
  • こういう矛盾が起きないように言語にはとっつきにくい仕様があったりする

4章 処理の流れのコントロール

  • 構造化プログラミング
  • if, whileとかの構文を導入してコード構造をわかりやすく
  • gotohは原始的すぎる

5章 関数

  • 関数の利点 => 理解、再利用
  • 入れ子のデータ構造は再帰で簡単に処理できる

6章 エラー処理

  • 失敗を伝える仕組みが大切
  • 返り値で失敗を伝える
  • 失敗を見落とす可能性　＝＞返り値チェックし忘れ
  • エラー処理のせいでコードが見づらい
  • 【C++の設計と進化】
  • ついなる処理を確実に行いたい
  • finallyによる解決
  • C++ではRAII
  • 例外とは
  • 引数不足
  • 配列範囲外
  • Pythonはこのうちどれでも例外を返す
  • Rubyは配列範囲外はnilを返す
  • 必要なところからかじろう
  • 全部読まなければならないという完璧主義がやる気をくじいているなら捨てたほうがよい

7章 名前とスコープ

  • 衝突を回避する
  • 長い名前をつける
  • スコープを利用する
  • 動的スコープ
  • 静的スコープ

8章 型

  • IEEE 754 浮動小数点数の標準
  • テンプレート(C++)
  • 動的型付け
  • 型推論
  • おおまかにつかんで徐々に詳細化する
  • ナナメ読みする
  • ざっくりと処理の流れを追う

9章 コンテナと文字列

10章 並行処理

  • 細かく区切って実行する
  • 協調的マルチタスク
  • きりの良い所で交代
  • プリエンプティブマルチタスク
  • 一定時間で交代する
  • 競合状態
  • 2つの処理が変数共有
  • 少なくともひとつの処理がその変数を置き換える
  • 一方の処理が一段落付く前にもう一方の処理が割り込む可能性がある
  • 共有でなければよい
  • OS「Multics」(1969)
  • OS「UNICS」(1970)
  • 後のUNIX
  • アクターモデル
  • Erlang, Scala
  • 書き換えない
  • const
  • 割り込まない
  • ロックの問題
  • デッドロック
  • 合成できない
  • トランザクショナルメモリ

11章 オブジェクトとクラス

  • 変数と関数を束ねて模型を作る方法
  • 関数もハッシュに入れる
  • クロージャ
  • クラス
  • まとまったものを作る生成器
  • どういう操作ができるかという仕様
  • コードを再利用する単位
  • 言語によって実現方法や「オブジェクト指向」の意味が異なる

12章 継承によるコードの再利用

  • 委譲
  • インターフェイス
  • 実装をまったくもたないクラス
  • メソッド解決順序を工夫する
  • ダイアモンド継承
  • C3線形化
  • 親クラスは子クラスより先に探索されない
  • あるクラスが複数の親クラスを継承している場合は先に書いてあるものが優先される
  • 処理を混ぜ込む（Mix-in）
  • モジュールはクラスからインスタンス生成器としての役割を取り除いたもの
  • トレイト
  • メソッドの束