こんにちは、CPPXのXです。

atcoderのabc065、D問題です。

最近、pythonだと間に合わないからそのままc++に直すとかいう分けわからん事してます。
物覚え悪いので、python → c++のメモを残しておきます。

初めに
実装概要
step1（入力受け取り）
step2（ソート）
step3（隣接リストを作る）
step4（最小全域木を作る）
- priority queue
- loop else
おわりに
python　ソースコード全体
c++ ソースコード全体

初めに

今回扱う問題です。
D: Built? - AtCoder Beginner Contest 065 | AtCoder

公式が行っている解説がかなり分かりやすいので、細かなアルゴリズムの説明は行いません。
python → c++を考えるときのメモです。

問題概要は、座標がn個が与えられます。
また、座標間のコストがmin(|a - c|, |b - d|)である時の最小全域木を求める感じです。

ただ、nが $10^5$ なので、全部の座標を繋いでしまうと、エッジの数が $(10^5)^2$ になって間に合わないので、ソートして要らない部分のエッジを繋がないようにする必要があります。

参考程度に、最小全域木を求めるための必要な計算回数は、O(nlog(n))です。

実装概要

今回の実装はざっくり分けて以下の通りです。
この項目毎に説明を行っていきます。

入力を受け取ります。
入力座標をxとyに分けてそれぞれソートします。
ソートされたxとyを繋いで隣接リストを作ります。
最小全域木を求めます。

今回載せるpythonだと、時間的に間に合いません。
c++だと間に合いました。

step1（入力受け取り）

python

n = int(input())
xs = []
ys = []
for i in range(n):
    x, y = map(int, input().split())
    xs.append((x, i))
    ys.append((y, i))

c++

  int n;
  cin >> n;

  pii xs[n];
  pii ys[n];

  int x, y;
  for(int i = 0; i < n; i++){
    cin >> x >> y;
    xs[i] = make_pair(x, i);
    ys[i] = make_pair(y, i);
  }

入力の持ち方は、以下のようになっています。
n
xs = [(x0, 0), (x1, 1), (x2, 2), … , (xn, n)]
ys = [(y0, 0), (y1, 1), (y2, 2), … , (yn, n)]

xs = [(xi, i)…] のようにして、x座標とノード番号を持っておきます。

xとyを分けているのは、後々xとyに注目してソートするためです。

pythonだと、2次元配列のような持ち方をしているのですが、c++でそう持つと面倒くさかったのでpairを用います。
pairで持っているのは、(xi, i)の部分です。

step2（ソート）

python

xs.sort(key=lambda x: x[0])
ys.sort(key=lambda x: x[0])

c++

  sort(xs, xs + n, [](const pii& a, const pii& b){ return a.first < b.first; });
  sort(ys, ys + n, [](const pii& a, const pii& b){ return a.first < b.first; });

pythonもc++もkeyを指定してソート出来ました。

c++のlambda式の書き方さえ覚えていれば特にソートで困る事は無さそうです。

c++のlambda式は、キャプチャ{処理}とかいう謎太郎です。
キャプチャは、競プロだと多分使わないので空でいいです。

一点だけ、c++のkeyは戻り値にboolを取り、ltで小さい順、gtで大きい順だけ気を付ける必要があります。

後で出てくるpriory_queueは、gtで小さい順でソートとは逆なので混乱しないように注意してください。

step3（隣接リストを作る）

def make_ad_list(ad_list, material):
    for i, t in enumerate(material[1:]):
        f = material[i]
        ad_list[f[1]].append((abs(f[0] - t[0]), t[1]))
        ad_list[t[1]].append((abs(f[0] - t[0]), f[1]))

ads = [[] for x in range(n)]
make_ad_list(ads, xs)
make_ad_list(ads, ys)

void make_ad_list(ad* ad_list, pii* material, int n){
  for(int i = 1; i < n; i++){
    pii from = material[i - 1];
    pii to = material[i];
    ad_list[from.second].push_back(make_pair(abs(from.first - to.first), to.second));
    ad_list[to.second].push_back(make_pair(abs(from.first - to.first), from.second));
  }
}

  ad ads[n];
  make_ad_list(ads, xs, n);
  make_ad_list(ads, ys, n);

adsが隣接リストです。
make_ad_listで隣接リストの中身を作っていきます。

make_ad_list()の中身では、
from → to に(cost, to)のpairを to → from に(cost, from)のpairを保存して、有向辺を2個貼って無向グラフにしています。

特にメモする事はないです。

vectorは怖くない。
enumerateは普通のforへ、それ以外は拡張forへ。

step4（最小全域木を作る）

python

pque = []

result = 0
visited = [False for x in range(n)]

target = 0
visited[0] = True

while True:
    for edge in ads[target]:
        heapq.heappush(pque, Node(*edge))

    while pque:
        n = heapq.heappop(pque)
        if not visited[n.from_]:
            break
    else:
        print(result)
        __import__("sys").exit()
    target = n.from_
    visited[target] = True
    result += n.cost

c++

  priority_queue<Node, vector<Node>, Comparator> pque;

  int result = 0;
  bool visited[n] = { false };

  int target = 0;
  visited[0] = true;

  while(true){
    for(pii edge: ads[target]){
      pque.push(Node(edge.first, edge.second));
    }
    Node n(0, 0);

    while(!pque.empty()){
      n = pque.top();
      pque.pop();
      if(not visited[n.from]){
        goto WHILELSE;
      }
    }
    cout << result << endl;
    return 0;

WHILELSE:
    target = n.from;
    visited[target] = true;
    result += n.cost;
  }
}

ひいい。。。多分もっと綺麗な書き方があります。

priority queueと、loop elseです。

priority queue

pythonだと、priority queueはheapqを用います。

普通のリストに対して、heapqの操作をすることで、priority queueの振る舞いをさせています。
heappush、heappopで出し入れを行うみたいです。

c++だと、priority_queueがあります。

priority_queueに対して、pushとpopで操作します。
ただ、popがvoidなので、topで取ってからpopします。

loop else

pythonには、loopのblockの後ろにelseを付けられる構文があります。
for elseとか、while elseです。

loopのblockの中でbreakすると、elseを通らないので、一度もこの処理を行わなかったら・・・みたいな処理を書くときに使っています。

c++だとbreakしたいタイミングでgotoで飛べばそれっぽくなりました。

javaだと、elseをしたいloopの1個外側でforを1回回してラベル付けてbreakとかいう汚ソース撒き散らしています。

おわりに

完全に個人用メモを残しておきます。

(a, b)とかはpairで持つ。
- (a, b, c)とか増えたらclass作る。
- 配列をtypedefしてもいいかもしれない。
lambda式：キャプチャー{処理}
- キャプチャーはとりあえず空でいい。
vectorは怖くない
forの書き換え
- enumerate → 普通のfor
- 普通のfor → 拡張for
priority_queue
loop else → goto
ぐちゃぐちゃになる前にtypedefするなりする。
and or notが使える。

当面の目標は、頭の中でpython組み立てながらc++を書くことです。

また、そのままだとデバッグしにくいのでその辺りをテンプレートにまとめたらまた記事を書きます。

python　ソースコード全体

import heapq


class Node:
    def __init__(self, cost, from_):
        self.cost = cost
        self.from_ = from_

    def __lt__(self, a):
        return self.cost < a.cost


def make_ad_list(ad_list, material):
    for i, t in enumerate(material[1:]):
        f = material[i]
        ad_list[f[1]].append((abs(f[0] - t[0]), t[1]))
        ad_list[t[1]].append((abs(f[0] - t[0]), f[1]))


# -- main --
n = int(input())
xs = []
ys = []
for i in range(n):
    x, y = map(int, input().split())
    xs.append((x, i))
    ys.append((y, i))

xs.sort(key=lambda x: x[0])
ys.sort(key=lambda x: x[0])

ads = [[] for x in range(n)]
make_ad_list(ads, xs)
make_ad_list(ads, ys)

pque = []

result = 0
visited = [False for x in range(n)]

target = 0
visited[0] = True

while True:
    for edge in ads[target]:
        heapq.heappush(pque, Node(*edge))

    while pque:
        n = heapq.heappop(pque)
        if not visited[n.from_]:
            break
    else:
        print(result)
        __import__("sys").exit()
    target = n.from_
    visited[target] = True
    result += n.cost

c++ ソースコード全体

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

class Node{
  public:
    int cost;
    int from;

    Node(int cost, int from){
      this -> cost = cost;
      this -> from = from;
    }
};

struct Comparator{
  bool operator()(const Node& a, const Node& b){
    return a.cost > b.cost;
  }
};

typedef pair<int, int> pii;
typedef vector<pii> ad;

void make_ad_list(ad* ad_list, pii* material, int n){
  for(int i = 1; i < n; i++){
    pii from = material[i - 1];
    pii to = material[i];
    ad_list[from.second].push_back(make_pair(abs(from.first - to.first), to.second));
    ad_list[to.second].push_back(make_pair(abs(from.first - to.first), from.second));
  }
}

int main(){
  int n;
  cin >> n;

  pii xs[n];
  pii ys[n];

  int x, y;
  for(int i = 0; i < n; i++){
    cin >> x >> y;
    xs[i] = make_pair(x, i);
    ys[i] = make_pair(y, i);
  }

  sort(xs, xs + n, [](const pii& a, const pii& b){ return a.first < b.first; });
  sort(ys, ys + n, [](const pii& a, const pii& b){ return a.first < b.first; });

  ad ads[n];
  make_ad_list(ads, xs, n);
  make_ad_list(ads, ys, n);

  priority_queue<Node, vector<Node>, Comparator> pque;

  int result = 0;
  bool visited[n] = { false };

  int target = 0;
  visited[0] = true;

  while(true){
    for(pii edge: ads[target]){
      pque.push(Node(edge.first, edge.second));
    }
    Node n(0, 0);

    while(!pque.empty()){
      n = pque.top();
      pque.pop();
      if(not visited[n.from]){
        goto WHILELSE;
      }
    }
    cout << result << endl;
    return 0;

WHILELSE:
    target = n.from;
    visited[target] = true;
    result += n.cost;
  }
}

Hello Wor.log

IT系大学生4人による備忘録のようなもの

Built?（python → c++メモ）

初めに

実装概要

step1（入力受け取り）

step2（ソート）

step3（隣接リストを作る）

step4（最小全域木を作る）

priority queue

loop else

おわりに

python　ソースコード全体

c++ ソースコード全体

初めに

実装概要

step1（入力受け取り）

step2（ソート）

step3（隣接リストを作る）

step4（最小全域木を作る）

priority queue

loop else

おわりに

python ソースコード全体

c++ ソースコード全体

python　ソースコード全体