2023-08-01

マイ競プロ用テンプレート

競技プログラミングでは，コードを記述する「速さ」と「正確さ」が求められます。そのため，競プロerの多くは自前のマクロやエイリアスなど用意し，コード記述をしやすくする工夫を行っています。

今回は私のマイテンプレート (C++) を紹介します。

#include <bits/stdc++.h>
#define REP(i,n)   for(int i=0;i<(int)(n);++i)
#define FOR(i,l,r) for(int i=(int)(l);i<(int)(r);++i)
#define ALL(v)     (v).begin(),(v).end()
using llong = long long;
using vi    = std::vector<int>;
using vvi   = std::vector<vi>;
using pii   = std::pair<int,int>;
using namespace std;
constexpr int       INF  = 1e9;
constexpr long long LINF = 1e18;
constexpr double    EPS  = 1e-10;
constexpr int       MOD  = 998'244'353;
constexpr int       MOD2 = 1e9+7;

template <typename Type>
std::istream &operator>>(std::istream &is, std::vector<Type> &v) {
    for(auto &in : v) is >> in;
    return is;
}

template <typename Type>
std::ostream &operator<<(std::ostream &os, const std::vector<Type> &v) {
    for(auto itr = v.cbegin(); itr != v.cend(); ++itr) os << (itr == v.cbegin() ? "" : " ") << *itr;
    return os;
}

#ifdef DEBUG

#include "debug.hpp"
using namespace algorithm;

#else

#define debug(...) static_cast<void>(0)

#endif

int main(){}

ライブラリ

#include <bits/stdc++.h>
using namespace std;

<bits/stdc++.h> の中身はこちらのようになっており，簡単に言うと「標準ライブラリ全部載せ」です。 GCC が提供しているもので，他の環境（Clang など）では動きません。移植性などの問題を抱える邪道ライブラリですが，「コードがすっきりする」という理由で使ってます。

「using namespace std;」¹は名前空間の修飾を省略するものです。普段の開発では名前衝突が懸念されますが，タイプ量を減らすために記述しています。

REPマクロ

#define REP(i,n)   for(int i=0;i<(int)(n);++i)
#define FOR(i,l,r) for(int i=(int)(l);i<(int)(r);++i)

競プロ界隈では有名なマクロです。

for文は利用場面が多いですが，3つ式を書く必要があり，記述量が多くバグの温床です。例えば，次のような記述ミスはコンパイル時にエラーがでず，発見しづらいバグとなります。

for(int i=0;i<n;++i){
    for(int j=0;j<m;++i){  // 更新式の変数をiになっている！　無限ループに...
        ...
    }
}

REPマクロは，変数を一回しか書く必要がないため，そのようなミスを防ぐことができます。

REP(i,n)REP(j,m){
    ...
}

ALLマクロ

#define ALL(v) (v).begin(),(v).end()

これもよく使われているマクロです。

std::sort() や std::lower_bound() の STL のコンテナの先頭と末尾のイテレータを指定するときに用います。

vector<int> v({3, 9, 6, 1, 2, 12, 30, 15});
sort(ALL(v));
int num = lower_bound(ALL(v), 3) - v.begin();  // num:=(3未満の値の数).

エイリアス

using llong = long long;
using vi    = std::vector<int>;
using vvi   = std::vector<vi>;
using pii   = std::pair<int,int>;

エイリアス²とは，任意の型名に対し別の型名を定義するものです。 long long など利用頻度が多いものは，タイプしやすい短い型名にしています。

const変数

constexpr int       INF  = 1e9;
constexpr long long LINF = 1e18;
constexpr double    EPS  = 1e-10;
constexpr int       MOD  = 998'244'353;
constexpr int       MOD2 = 1e9+7;

競プロで利用頻度の多い数値は const変数として定義しています。 INF や EPS は，無限大や極小値を表すダミー値です。また，MOD は AtCoder に頻出する素数です。

std::vectorの入出力演算子

template <typename Type>
std::istream &operator>>(std::istream &is, std::vector<Type> &v) {
    for(auto &in : v) is >> in;
    return is;
}

template <typename Type>
std::ostream &operator<<(std::ostream &os, const std::vector<Type> &v) {
    for(auto itr = v.cbegin(); itr != v.cend(); ++itr) os << (itr == v.cbegin() ? "" : " ") << *itr;
    return os;
}

配列の入出力を行う際，for文で記述しますが，タイプ量が多くて面倒です。そのため，std::vector の入出力演算子を定義しています。

vector<int> v(n);
cin >> v;
...
cout << v << endl;

debugマクロ

#ifdef DEBUG

#include "debug.hpp"
using namespace algorithm;

#else

#define debug(...) static_cast<void>(0)

#endif

ifdef を用いて，ローカル環境のみで動作するデバッグマクロを定義しています。

ライブラリの中身はこちらのようになっています。詳しいデバッグマクロの説明は別記事に書こうと思います。

あとがき

あくまで競プロ用として。

【参考】他の方のテンプレート

一部世間では「575」と表現されるそうです。↩
C++でエイリアス宣言する方法は，typedef と using の2通りありますが，usingの方がモダンな方法として推奨されているようです（こちらの記事参照）。↩

2023-04-12

【AtCoder】M-SOLUTIONSプロコンオープン D - Maximum Sum of Minimum

問題概要
初めに考えたこと
考察
実装
感想

問題概要

N頂点の木とN個の正整数が与えられ，各頂点に1つずつ正整数を任意の順で書き込んでいく。そして各辺の両端に書かれいている正整数 a,b のうち小さいほう (min(a,b)) をスコアに加算していく。

このとき取り得るスコアの最大値とその場合の書き込み方を出力せよ。

atcoder.jp

初めに考えたこと

次数の少ない頂点から順に小さい正整数を書き込めば，小さい正整数が評価される回数が少なくなるのではと考えた。

しかしこの方針ではWAとなった......。

atcoder.jp

どうやら下図のような場合がダメとなるよう（「5と6, 6と7」と評価できるところを「5と6, 5と7」と評価している）。

考察

最大の正整数はスコアに加算できない。二番目以降に大きい正整数は，自分より大きいものと繋がればスコアに加算される。

大きい正整数から書き込んでいくと，二番目に大きい正整数は1回しかスコアに貢献できず，また同様に三番目以降の正整数も1回しかスコアに貢献できなくなる。これが最大のスコアを取る方法のようだ。

実装

DFSで大きい正整数から書き込んでいけばよい。

atcoder.jp

感想

なかなか解法が思い浮かばなかったんですが，他の方のコード見ると確かにと納得できました。もっとセンスよく正解のイメージをできるようになりたいですね。

2023-03-02

無向・有向グラフにおける閉路検出方法

競技プログラミングでは「グラフの閉路検出」は頻出です。しかし，解法が複数あるため，実践において時々どうアプローチしようか迷ったりすることがあります（個人的に......）。本記事では，本番で適当な方法を選択できるように「無向・有向グラフにおける閉路検出方法」についてまとめます。

無向グラフ
- 方法(1)：DFS（深さ優先探索）
- 方法(2)：Union-Find
有向グラフ
- 方法(3)：トポロジカルソート
参考文献

無向グラフ

無向グラフにおいて，閉路がないグラフは，木である連結成分が1つまたは複数（森）ある状態です。

方法(1)：DFS（深さ優先探索）

ある連結成分において，任意の頂点を根として選択し，DFSを行います。そのDFSの途中で，ある頂点に再度訪問した場合，その連結成分には閉路があると判断できます。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;  // n:=(グラフの頂点数), m:=(辺の数).
    cin >> n >> m;

    vector<vector<int> > g(n);  // g[v][]:=(頂点vの隣接リスト).
    for(int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        // 頂点uとvに辺を張る。
        g[u].push_back(v);
        g[v].push_back(u);
    }

    bool seen[n] = {};  // seen[v]:=(頂点vを訪問したか).
    auto dfs = [&g, &seen](auto self, int u, int p) -> bool {
        seen[u] = true;
        for(auto v : g[u]) {
            if(v == p) continue;      // DFS木において頂点vが親の場合.
            if(seen[v]) return true;  // 頂点vがすでに訪問している場合。閉路ありと判断する。
            if(self(self, v, u)) return true;
        }
        return false;
    };

    for(int i = 0; i < n; ++i) {
        if(!seen[i]) {  // まだ未探索の連結成分がある場合。
            auto res = dfs(dfs, i, -1);
            if(res) {
                cout << "Find cycle" << endl;
                return 0;
            }
        }
    }

    cout << "No cycle" << endl;
}

方法(2)：Union-Find

Union-Find木を用い，各頂点を管理します。グラフの辺リストを走査し，辺を結ぶ2頂点を連結していきます。この走査の途中で，2頂点がすでに連結である場合，閉路があると判断できます。

#include <bits/stdc++.h>
using namespace std;

// 素集合データ構造。
class UnionFind {
    int m_vn;                // m_vn:=(ノード数).
    int m_gn;                // m_gn:=(連結成分数).
    std::vector<int> m_par;  // m_par[v]:=(ノードvの親番号). 0未満の場合，vは根であり，値の絶対値は連結成分のサイズを表す。

public:
    UnionFind() : UnionFind(0) {}
    explicit UnionFind(size_t vn) : m_vn(vn), m_gn(vn), m_par(vn, -1) {}

    // ノードの総数を返す。
    int vn() const { return m_vn; };
    // 連結成分の数を返す。
    int gn() const { return m_gn; };
    // ノードvが属する連結成分の根番号を返す。
    int root(int v) {
        assert(0 <= v and v < vn());
        if(m_par[v] < 0) return v;
        return m_par[v] = root(m_par[v]);
    }
    // ノードvが属する連結成分のサイズを返す。
    int size(int v) {
        assert(0 <= v and v < vn());
        return -m_par[root(v)];
    }
    // ノードuとvが連結しているか判定する。
    bool is_same(int u, int v) {
        assert(0 <= u and u < vn());
        assert(0 <= v and v < vn());
        return root(u) == root(v);
    }
    // ノードuとvの属する連結成分を繋げる。
    bool unite(int u, int v) {
        assert(0 <= u and u < vn());
        assert(0 <= v and v < vn());
        u = root(u), v = root(v);
        if(u == v) return false;                // Do nothing.
        if(size(u) < size(v)) std::swap(u, v);  // Merge technique.
        m_par[u] += m_par[v];
        m_par[v] = u;
        m_gn--;
        return true;
    }
    void reset() {
        m_gn = vn();
        std::fill(m_par.begin(), m_par.end(), -1);
    }
};

int main() {
    int n, m;  // n:=(グラフの頂点数), m:=(辺の数).
    cin >> n >> m;

    vector<pair<int, int> > edges(m);  // edges[]:=(頂点firstとsecondを繋ぐ辺のリスト).
    for(auto &[u, v] : edges) {
        cin >> u >> v;
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
    }

    UnionFind uf(n);
    for(const auto &[u, v] : edges) {
        if(uf.is_same(u, v)) {  // 頂点uとvがすでに連結の場合。閉路ありと判断する。
            cout << "Find cycle" << endl;
            return 0;
        }
        uf.unite(u, v);
    }

    cout << "No cycle" << endl;
}

有向グラフ

有向グラフにおいて，閉路がないグラフはDAG (Directed Acyclic Graph) です。

方法(3)：トポロジカルソート

DAGであればトポロジカルソートが可能です。つまり，トポロジカルソートができなければDAG（閉路のないグラフ）ではありません（対偶）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;  // n:=(グラフの頂点数), m:=(辺の数).
    cin >> n >> m;

    vector<vector<int> > g(n);  // g[v][]:=(頂点vが始点となる辺のリスト).
    vector<int> deg(n, 0);           // deg[v]:=(頂点vの入次数).
    for(int i = 0; i < m; ++i) {
        int from, to;
        cin >> from >> to;
        assert(0 <= from and from < n);
        assert(0 <= to and to < n);
        g[from].push_back(to);
        deg[to]++;
    }

    // トポロジカルソート。
    vector<int> res;  // res[]:=(トポロジカルソートの結果).
    queue<int> que;
    for(int i = 0; i < n; ++i) {
        if(deg[i] == 0) que.push(i);
    }
    while(!que.empty()) {
        auto u = que.front();
        que.pop();
        res.push_back(u);

        for(auto v : g[u]) {
            if(--deg[v] == 0) que.push(v);
        }
    }

    for(auto elem : deg) {
        if(elem > 0) {  // 並べていない頂点がある場合。閉路があると判断できる。
            cout << "Find cycle" << endl;
            return 0;
        }
    }

    cout << "No cycle" << endl;
}

以上，無向グラフと有向グラフ合わせて，3つの方法をまとめました。他にも方法はあると思いますが，これだけ覚えておけば何とかなる？と思います。しらんけど。

参考文献

drken, DFS (深さ優先探索) 超入門！〜グラフ・アルゴリズムの世界への入口〜【後編】, 4-6. サイクル検出, Qiita, (参照2023.3.2).

2023-01-03

ns3におけるシミュレーションシナリオ作成法

本記事では，ネットワークシミュレータであるns3におけるシナリオコードの書き方を大雑把にまとめ，説明しています．

想定している読者さんは，

C++をある程度知っている方
ns3での基本的なシナリオ作成方法を知りたい方
「Helperって結局裏で何してるの？」と疑問をお持ちの方

です．

（本記事にあるプログラムコードはns-3.37をベースにしています．）

（本記事は著者の備忘録としてまとめたものです．また著者自身ns3の経験が浅いため，誤った表記をしているかもしれません．その際はコメント等でご指摘いただけると有難いです．）

1. ns3の概念
2. オブジェクトモデル
3. オブジェクトの生成，設定，Tips
4. 主な構成要素
5. シナリオプログラミング実践例
参考文献
- 書籍
- Webサイト

1. ns3の概念

ns3では，実世界でのネットワークを構築する作業と同じような論理的なプロセスを採用している．まず，物理層とデータリンク層では，ノードと呼ばれる通信デバイスの筐体にNICなどのネットワークデバイスを装着して，有線，または無線メディアをその通信属性に合わせて「配線」する．次に，IPアドレスや，ルーティング方式などのネットワーク層の情報を設定した後，トランスポート層で使用するプロトコルの設定を行う．最後に，ネットワーク上で使用されるアプリケーションを装着する．

銭飛著『ns3によるネットワークシミュレーション』森北出版 (2014) p.18より

ns3はC++で記述されたオブジェクトベースのシステムです． "通信端末"や"NIC"，"伝送媒体"，"プロトコル"，"アプリケーション"，"パケット"などといったネットワークシステムの構成要素の概念が，それぞれ抽象化され，C++のクラスで定義されています．

シナリオプログラミングでは，ns3のライブラリをインクルードし，必要となる構成要素のクラスからオブジェクトを生成して，属性値を変更したり互いに組み合わせながら，任意のネットワークシステムを構築します．この構築作業は「各PC (Node) にNIC (NetDevice) を装着し，ケーブル (Channel) をつなげ，アプリケーション (Application) を動かし通信する......」といったように，実際にネットワークを構築するようなイメージをもつとわかりやすいと思います．

2. オブジェクトモデル

構成要素を表しているクラスのモデルについて説明します．

ns3ではオブジェクト指向の設計をとっています．例えば，エコーサーバアプリを表すns3::UdpEchoServerクラスは，ns3::Applicationクラスから継承して定義されています．

すべての構成要素のクラスは基本的にns3::SimpleRefCountクラス，ns3::ObjectBaseクラス，ns3::Objectクラスのいずれかを継承しています（ns3::Objectクラスは他2つから派生しています）．これらの違いはサポートしている機能の有無です．

	スマートポインタ (ns3::Ptr)	ns3::TypeId, 属性値	オブジェクトの集約機能
class ns3::SimpleRefCount	o	x	x
class ns3::ObjectBase	x	o	o
class ns3::Object	o	o	o

ns3のクラスはすべてこちらのドキュメントにまとめられています．

2.1. スマートポインタ (ns3::Ptr)

ns3ではメモリ管理を容易にするため，スマートポインタをベースにしたns3::Ptrを用いてオブジェクトを参照します．

2.2. ns3::TypeId

ns3::ObjectBaseおよびns3::Objectクラスから派生するクラスは，クラスのメタデータを表すns3::TypeIdを含んでいます．

クラスを一意に識別する文字列
親クラス
コンストラクタで用いるクラス
属性値（値の種類，最小値や最大値の制約など）

2.3. 属性値 (Attribute)

先のns3::TypeIdを用いて，そのオブジェクトの性質を表す属性値 (Attribute) が設定されます．この属性値は，シミュレーションシナリオに沿って変更できます（属性値の設定および変更方法については後述します）．

属性値の一覧はこちらから確認できます．

2.4. オブジェクトの集約

多くのオブジェクトを作成すると参照が大変になります．このときオブジェクトの集約機能を使うと，オブジェクト間で関連付けがされ参照を簡単にできます（この方法についても後述します）．

3. オブジェクトの生成，設定，Tips

オブジェクトの生成や属性値の設定はいくつかやり方があるのですが，ここでは基本的な方法を紹介します．

3.1. オブジェクトの生成

new演算子の代わりにns3::CreateObject(), ns3::Create()を用います．返り値はns3::Ptrとなります．

ns3::Objectから派生したクラスのオブジェクトの生成は，ns3::CreateObject()を使います．

Ptr<Node> node = CreateObject<Node>();

それ以外のns3::SimpleRefCountクラスから派生するクラス（ns3::Ptrをサポートするクラス）のオブジェクトの生成は，ns3::Create()を使います．

Ptr<Packet> packet = Create<Packet>();

3.2. 属性値の設定

オブジェクトの属性値の設定，変更はns3::ObjectBaseクラスのメンバ関数 SetAttribute()を用います．第一引数に属性名，第二引数に指定の属性値を与えます．

Ptr<UdpEchoServer> app = CreateObject<UdpEchoServer>();
app->SetAttribute("Port", UintegerValue(12345));
app->SetAttribute("StartTime", TimeValue(Seconds(10.0)));
app->SetAttribute("StopTime", TimeValue(Seconds(20.0)));
node->AddApplication(app);

3.3. ObjectFactory

同じ属性値のオブジェクトを複数生成したい場合，それぞれにSetAttribute()で設定していくのは面倒です．そのときはObjectFactoryが便利です．

ObjectFactory factory;
factory.SetTypeId("ns3::UdpEchoServer");
factory.Set("Port", UintegerValue(12345));
factory.Set("StartTime", TimeValue(Seconds(10.0)));
factory.Set("StopTime", TimeValue(Seconds(20.0)));

Ptr<UdpEchoServer> app1 = factory.Create<UdpEchoServer>();
node1->AddApplication(app1);

Ptr<UdpEchoServer> app2 = factory.Create<UdpEchoServer>();
node2->AddApplication(app2);

3.4. Helper API

規模が巨大なシナリオを構成する場合，必要となる構成要素が膨大となり，各オブジェクト間の依存関係が複雑になります．そこでns3では，モデルごとにHelper APIが提供されています． Helper APIを用いれば，そのモデルの構成要素ををまとめて生成し，構築してくれます．

UdpEchoServerHelper helper(12345);
server.SetAttribute("StartTime", TimeValue(Seconds(10.0)));
server.SetAttribute("StopTime", TimeValue(Seconds(20.0)));

ApplicationContainer apps = helper.Install(nodes);

3.5. Container

ns3ではContainerというオブジェクトをよく用います． Containerは同じクラスのオブジェクトをまとめて管理するためのもので，ns3::NodeContainerやns3::ApplicationContainerなどがあります．中身のデータ構造はただのstd::vectorです．

3.6. オブジェクトの集約方法

オブジェクトの集約は，ns3::Objectクラスのメンバ関数 AggregateObject()を用います．次の例では，ns3::Nodeオブジェクトとns3::Socketオブジェクトを関連付けしています．

int main(){
    Ptr<Node> node = CreateObject<Node>();
    ...
    Ptr<Socket> socket = Socket::CreateSocket(node, UdpSocketFactory::GetTypeId());
    node->AggregateObject(socket);
    ...
    f(node);
    ...
}

2つのオブジェクトを関連付けした後は，ns3::Objectクラスのメンバ関数 GetObject()を用いてクラスの型を指定することで，任意のオブジェクトを参照できます．

void f(Ptr<Node> node){
    Ptr<Socket> socket = node->GetObject<Socket>();
    ...
}

ただし，1つのオブジェクトに2つ以上の同じクラスのオブジェクトを集約できません．

4. 主な構成要素

次にns3においてネットワークを構築する際に必要となる主な構成要素について説明します．

4.1. Node

ネットワークに接続している機器（ホスト，エンドシステム）を指します．例えばPCやルータ，サーバ，他にもIoT機器もこれに対応します． ns3ではこれらをもまとめて抽象化し，ns3::Nodeクラスで表しています．

さらにワイヤレスネットワークにおける移動端末を表現するため，Nodeの位置や速度といったモビリティも指定できます（モビリティはns3::MobilityModelクラスで定義されています）．

4.2. NetDevice

NIC（機器とネットワークをつなぐ拡張装置，ネットワークへのインターフェイス）に相当します． ns3ではns3::NetDeviceクラスで表されており，さらにこの子クラスで，Point-to-PointリンクやEthernet，Wi-Fiなど使用するネットワークモデルに対応したNetDeviceが定義されています．

ns3::PointToPointNetDevice
ns3::CsmaNetDevice
ns3::WifiNetDevice etc.

4.3. Channel

有線や無線などの伝送媒体を指します． ns3ではns3::Channelクラスで定義されており，これも同様にネットワークモデルに応じて子クラスが定義されています．

ns3::PointToPointChannel
ns3::CsmaChannel
ns3::WifiChannel etc.

4.4. Application

トラフィックを生成したり，パケットを送受信するなど任意のアクションを行う，Node上で実行されるアプリケーションを指します．これはns3::Applicationで定義されており，よく使われるアプリケーションはすでに子クラスで定義，提供されています．

ns3::PacketSinkApplication
ns3::OnOffApplication
ns3::BulkSendApplication
ns3::UdpEchoServer
ns3::UdpEchoClient etc.

またns3ではソケットAPIも提供しており (ns3::Socket)，ソケットプログラミングを行えば任意の通信を行うApplicationを定義することも可能です．

5. シナリオプログラミング実践例

5.1. シナリオ概要

2つのNodeをP2Pリンクで繋ぎ，200bytesのデータを送受信させる，といったシナリオを考えます．

時間	イベント
	シミュレーション開始．
5秒後	サーバを起動する．
10秒後	クライアントからサーバへ，UDPで200bytesのデータを送信する．
25秒後	サーバを停止する．
30秒後	シミュレーション終了．

5.2. 基本的なシナリオプログラミング

オブジェクトを意識して構築します．

Nodeを作成する．
NetDeviceを作成し，各Nodeに搭載する．
Channelを作成し，各NetDeviceに配線する．
Applicationを作成し，各Nodeにインストールする．

#include "ns3/applications-module.h"
#include "ns3/core-module.h"
#include "ns3/internet-module.h"
#include "ns3/network-module.h"
#include "ns3/point-to-point-module.h"
using namespace ns3;

int main() {
    LogComponentEnable("UdpServer", LOG_LEVEL_INFO);
    LogComponentEnable("UdpClient", LOG_LEVEL_INFO);
    LogComponentEnableAll(LOG_PREFIX_ALL);

    // (1) Nodeを作成する．
    NodeContainer nodes;

    Ptr<Node> node1 = CreateObject<Node>();  // 送信側のNodeを作成する．
    nodes.Add(node1);

    Ptr<Node> node2 = CreateObject<Node>();  // 受信側のNodeを作成する．
    nodes.Add(node2);

    // (2) NetDeviceを作成し，各Nodeに搭載する．
    NetDeviceContainer devices;

    ObjectFactory deviceFactory("ns3::PointToPointNetDevice");
    deviceFactory.Set("DataRate", StringValue("5Mbps"));  // NetDeviceの送信レートを設定する．

    Ptr<PointToPointNetDevice> device1 = deviceFactory.Create<PointToPointNetDevice>();  // NetDeviceを作成する．
    device1->SetAddress(Mac48Address::Allocate());                                       // MACアドレスを割り当てる．
    node1->AddDevice(device1);                                                           // Nodeに搭載する．
    devices.Add(device1);

    Ptr<PointToPointNetDevice> device2 = deviceFactory.Create<PointToPointNetDevice>();
    device2->SetAddress(Mac48Address::Allocate());
    node2->AddDevice(device2);
    devices.Add(device2);

    // パケットキューを設定する．
    ObjectFactory queuelFactory("ns3::DropTailQueue<Packet>");

    Ptr<Queue<Packet> > queue1 = queuelFactory.Create<Queue<Packet> >();
    device1->SetQueue(queue1);

    Ptr<Queue<Packet> > queue2 = queuelFactory.Create<Queue<Packet> >();
    device2->SetQueue(queue2);

    // (3) Channelを設定する．
    ObjectFactory channelFactory("ns3::PointToPointChannel");
    channelFactory.Set("Delay", StringValue("2ms"));  // 伝搬による遅延時間を設定する．

    Ptr<PointToPointChannel> channel = channelFactory.Create<PointToPointChannel>();  // Channelを作成する．
    // 各NetDeviceにChannelを配線する．
    device1->Attach(channel);
    device2->Attach(channel);

    // 各Nodeにプロトコルスタックを積む．
    InternetStackHelper internet;
    internet.Install(node1);
    internet.Install(node2);

    // 各NetDeviceにIPアドレスを割り当てる．
    Ipv4AddressHelper ipv4;
    ipv4.SetBase("10.1.1.0", "255.255.255.0");
    Ipv4InterfaceContainer ifs = ipv4.Assign(devices);

    // (4) Applicationを作成する．
    uint16_t port = 12345;

    Ptr<UdpServer> serverApp = CreateObject<UdpServer>();
    serverApp->SetAttribute("Port", UintegerValue(port));           // ポート番号を設定する．
    serverApp->SetAttribute("StartTime", TimeValue(Seconds(5.0)));  // サーバアプリの開始時間を設定する．
    serverApp->SetAttribute("StopTime", TimeValue(Seconds(25.0)));  // サーバアプリの終了時間を設定する．
    node2->AddApplication(serverApp);

    Ptr<UdpClient> clientApp = CreateObject<UdpClient>();
    clientApp->SetAttribute("RemoteAddress", AddressValue(Ipv4Address("10.1.1.2")));  // 宛先のIPアドレスを設定する．
    clientApp->SetAttribute("RemotePort", UintegerValue(port));                       // 宛先のポート番号を設定する．
    clientApp->SetAttribute("PacketSize", UintegerValue(200));                        // 送信データサイズを200bytesと設定する．
    clientApp->SetAttribute("MaxPackets", UintegerValue(1));                          // 送信回数を1回と設定する．
    clientApp->SetAttribute("StartTime", TimeValue(Seconds(10.0)));                   // 送信開始時間を設定する．
    node1->AddApplication(clientApp);

    Simulator::Stop(Seconds(30.0));

    Simulator::Run();
    Simulator::Destroy();
}

5.3. Helper APIを用いたシナリオプログラミング

Helper APIを利用すれば，ぐっとコード量が減り，わかりやすくなります．

#include "ns3/applications-module.h"
#include "ns3/core-module.h"
#include "ns3/internet-module.h"
#include "ns3/network-module.h"
#include "ns3/point-to-point-module.h"
using namespace ns3;

int main() {
    LogComponentEnable("UdpServer", LOG_LEVEL_INFO);
    LogComponentEnable("UdpClient", LOG_LEVEL_INFO);
    LogComponentEnableAll(LOG_PREFIX_ALL);

    // (1) Nodeを作成する．
    NodeContainer nodes(2);

    // (2, 3) Node間にP2Pリンクを張る．
    PointToPointHelper p2p;
    p2p.SetDeviceAttribute("DataRate", StringValue("5Mbps"));
    p2p.SetChannelAttribute("Delay", StringValue("2ms"));
    NetDeviceContainer devices = p2p.Install(nodes);

    // 各Nodeにプロトコルスタックを積む．
    InternetStackHelper internet;
    internet.Install(nodes);

    // 各NetDeviceにIPアドレスを割り当てる．
    Ipv4AddressHelper ipv4;
    ipv4.SetBase("10.1.1.0", "255.255.255.0");
    Ipv4InterfaceContainer ifs = ipv4.Assign(devices);

    // (4) Applicationを作成する．
    uint16_t port = 12345;

    UdpServerHelper server(port);
    server.SetAttribute("StartTime", TimeValue(Seconds(5.0)));
    server.SetAttribute("StopTime", TimeValue(Seconds(25.0)));
    ApplicationContainer serverApp = server.Install(nodes.Get(1));

    UdpClientHelper client(Ipv4Address("10.1.1.2"), port);
    client.SetAttribute("PacketSize", UintegerValue(200));
    client.SetAttribute("MaxPackets", UintegerValue(1));
    client.SetAttribute("StartTime", TimeValue(Seconds(10.0)));
    ApplicationContainer clientApp = client.Install(nodes.Get(0));

    Simulator::Stop(Seconds(30.0));

    Simulator::Run();
    Simulator::Destroy();
}

5.4. シミュレーション結果

ログの出力結果は次のようになりました．クライアントがデータを送信した2.368ms後にサーバが受信しています．

+10.000000000s 0 UdpClient:Send(): [INFO ] TraceDelay TX 200 bytes to 10.1.1.2 Uid: 0 Time: +10s
+10.002368000s 1 UdpServer:HandleRead(): [INFO ] TraceDelay: RX 200 bytes from 10.1.1.1 Sequence Number: 0 Uid: 0 TXtime: +1e+10ns RXtime: +1.00024e+10ns Delay: +2.368e+06ns

今回送受信されたパケットサイズは230bytes (ペイロード：200bytes，UDPヘッダ：8bytes，IPv4ヘッダ：20bytes，PPPのヘッダ：2bytes) ，データレートは5Mbpsなので，伝送遅延は $(230 \rm{[bytes]} \times 8 \rm{[bits/byte]} ) / (5 \rm{[Mbits/s]} \times 10^{6} \rm{[bits/Mbit]} ) = 3.68 \times 10^{-4} \rm{[s]}$ です．さらにChannelによる伝搬遅延は2ms．よって全体の遅延は2.368msとなります．

参考文献

書籍

銭飛著，ns3によるネットワークシミュレーション，森北出版 (2014).

Webサイト

※ 記事中のアイコンはwww.flaticon.comを利用しています． Icons made by srip from www.flaticon.com.

2022-07-31

【AtCoder】ARC145 A - "AB Palindrome"

一見複雑そうに見えるが，ある規則を見つけると，考えるべき問題は単純になる．

問題概要
- 制約
考察
解法
- 実装 (C++)
感想

問題概要

atcoder.jp

英文字の'A', 'B'からなる長さ $N$ 文字列 $S$ が与えられる．
$S$ 中の隣接する2文字を"AB"に置き換える操作を，0回以上の任意の回数繰り返すことで，回文を得られるか判定せよ．

制約

$2 \leq N \leq 2 \times 10^5$

考察

まず，利用できそうな置き換え方法を探ってみる．

任意の位置から順方向に（ $S[i:i+2], S[i+1:i+3], \cdots$ の順で）"AB"に置き換えると，"AAA...AAB"という部分文字列が作れる．
同様に，任意の位置から逆方向に（ $S[i-2:i], S[i-3:i-1], \cdots$ の順で）"AB"に置きかえると，"ABB...BBB"という部分文字列が作れる．

これらより

$S[0]=\rm{'B'}$ の場合は，"BAA...AAB"
$S[N-1]=\rm{'A'}$ の場合は，"ABB...BBA"

とすれば回文ができる．

あとは

先頭 $S[0]$ を'A'から'B'に
末尾 $S[N-1]$ を'B'から'A'に

置き換えることができないことなどに注意しながら， $S[0]=\rm{'A'}$ の場合と， $S[n-1]=\rm{'B'}$ の場合を考えればよい．

（ただし， $N=2$ の場合は上記が適用ができないので別に考える必要がある．）

解法

$N=2$ の場合．

$S=\rm{"AA"}$ または $S=\rm{"BB"}$ のとき：すでに回文である．
$S=\rm{"AB"}$ または $S=\rm{"BA"}$ のとき：置換しても"AB"しかできず，回文を得ることはできない．

$N \geq 3$ の場合．

$S[0], S[N-1]$ について，それぞれ場合分けして考える．

$S[0]=\rm{'A'}$ のとき
- $S[N-1]=\rm{'A'}$ の場合：回文"ABB...BBA"を得る．
- $S[N-1]=\rm{'B'}$ の場合：先頭 $S[0]$ と末尾 $S[N-1]$ はどちらも置き換えできないので，回文を得られない．
$S[0]=\rm{'B'}$ のとき：回文"BAA...AAB"を得る．

以上■

実装 (C++)

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

int main(){
    int n;
    string s;
    cin>>n>>s;
    
    bool ans;
    if(n==2){
        if(s=="AA" or s=="BB") ans=true;
        else ans=false;
    }else{
        if(s[0]=='A'){
            if(s[n-1]=='A') ans=true;
            else ans=false;
        }else{
            ans=true;
        }
    }
    
    cout<<(ans?"Yes":"No")<<endl;
}

感想

本番はDPで考えて複雑になり，解けなかったです......．上手いこと利用できそうな操作方法を見つけ出すのがカギでしたね．

久々のARCだったんですが，やはり典型解法が多いABCとは違い，頭の柔軟さがより求められる印象です．
ARCの過去問もいっぱい解いて慣れようと思います．

2022-05-05

自己紹介

はじめまして。Todayです。

以前別のアカウントでブログを書いてましたが、今年度から新生活を始めるにあたり心機一転、新しい場で書き始めることにしました。

本ブログの位置づけは、私が思ったことや吸収したことを書いていく「雑記帳」です。
日々インプットすることが多いのですが、それを自身の中で留めておくと考えがこんがらがったり忘れたりするので、アウトプットし整理する場として活用していく所存です。
内容は多分、競技プログラミングのことが中心になると思います。

投稿頻度は特に決めず、書きたいと思ったときに書きます。