std::setの使い方

問題

AGC 022 A問題。

A - Diverse Word

解法のポイントとsetの使いどころ

文字数が26文字のとき、後ろから見て最長の昇順文字列（接尾文字列）を取得し、最長の昇順文字列の1つ手前の文字より大きい中で接尾文字列に含まれる一番小さな文字を最後に付け足したい。

ここでsetが役に立つ。

コメント付きメモ。

  set<char> g;
  while (s.size()) {
    char c = s.back();
    s.pop_back();
    auto it = g.upper_bound(c);
    // cが詰めてきた文字より大きな文字の場合、it == g.end() => trueとなる
    if (it != g.end()) {
      // it: cより大きい中で一番小さな文字
      s += *it;
      cout << s << '\n';
      return 0;
    }
    g.insert(c);
  }
  cout << -1 << "\n";

提出

Submission #16563738 - AtCoder Grand Contest 022

参考

Submission #16520821 - AtCoder Grand Contest 022

clang-format on WSL on Windows with Visual Studio Code

この記事が助けになるかもしれない人

Windows 10上のVisual Studio CodeからWSLのUbuntuにremote接続して開発を行っている人が、clang formatを適用する。

適用方法

1. WSL上のUbuntuにclang-formatをインストールする必要がある。

sudo apt-get update sudo apt-get install clang-format

1. Visual Studio Codeにclang-formatのextensionをインストール

2. Visual Studio Code上の設定「Clang-format: Executable」にclang-formatのパスを設定

パスを確認 $ which clang-format /usr/bin/clang-format

/usr/bin/clang-formatを「Clang-format: Executable」に設定

1. 動いた！

0 1 BFS

0 1 BFSとは

betrue12.hateblo.jp

例題

D - Wizard in Maze

実装例

隣への移動はコスト0、ワープでの移動はコスト1なので、 隣への移動時はdequeの前に、ワープでの移動時はdequeの後に詰めることで、コストの低いところから探索を行うことができる。

ただし、一度訪れた点もコストが改善するときには再度訪問したいので、visitedフラグの管理での訪問判定は結局していない。 Submission #16206218 - AtCoder Beginner Contest 176

要復習リスト

ABC

C - Repsept

Atcoder Beginner Contest 174(バチャ)

C問題

大きな数を扱うときに文字列として扱う以外の方法を学んだのでメモ。

等比数列として考える

今回のC問題のi番目は、

と書ける。

大きな数の除算

ABC174 C問題のEditorial より引用。 https://img.atcoder.jp/abc174/editorial.pdf

などといった巨大な値を直接 で割ろうとするべきではありません。その代わ りに、 10ⁱ を で割った余りを 倍して で割れば、 10ⁱ+1 を で割った余りが求まります。

D問題

仕切りを入れて、部分問題にわける。

E問題

sum(ceil(A_i / X) - 1) < kと条件を書き換えて、二分探索

F問題

...

ダイクストラ法と経路復元

蟻本ベースにサンプルコードをきちんと書いたので、メモを残しておきます。

コード

struct edge
{
public:
    int to;
    int cost;
};

// O(|E|(log|V|))
void dijkstra(std::vector<int> &dist, const std::vector<std::vector<edge>> &graph, int s)
{
    typedef std::pair<int, int> P;
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    for (auto &e : dist)
    {
        e = INF;
    }
    dist[s] = 0;
    // P(distance from start, vertex index)
    pq.push(P(0, s));
    while (!pq.empty())
    {
        P cur = pq.top();
        pq.pop();
        int v = cur.second;
        int cost = cur.first;
        if (dist[v] < cost)
        {
            continue;
        }
        for (const auto &next : graph[v])
        {
            if (dist[next.to] > next.cost + dist[v])
            {
                dist[next.to] = next.cost + dist[v];
                pq.push(P(dist[next.to], next.to));
            }
        }
    }
}

// O(|E|)
void restorePath(
    std::vector<int> &path,
    const std::vector<int> &dist,
    const std::vector<std::vector<edge>> &graph,
    int e)
{
    int cur = e;
    path.push_back(e);
    while (dist[cur] != 0)
    {
        for (const auto &n : graph[cur])
        {
            if (dist[n.to] + n.cost == dist[cur])
            {
                path.push_back(n.to);
                cur = n.to;
                break;
            }
        }
    }
    std::reverse(path.begin(), path.end());
}

競技プログラミングtips(特定範囲の条件満たす要素数え上げ)

想定問題形式

「L以上、R以下の整数値のうち、条件にあてはまるものを数えよ。」というような形式を想定。

取り組み方

1..L-1、1...Rと分けて、(1..Rで条件を満たす数) - (1..L-1で条件を満たす数) として計算