AGC 022 A問題。
文字数が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
Windows 10上のVisual Studio CodeからWSLのUbuntuにremote接続して開発を行っている人が、clang formatを適用する。
sudo apt-get update
sudo apt-get install clang-format
Visual Studio Codeにclang-formatのextensionをインストール
Visual Studio Code上の設定「Clang-format: Executable」にclang-formatのパスを設定
パスを確認
$ which clang-format
/usr/bin/clang-format
/usr/bin/clang-formatを「Clang-format: Executable」に設定
隣への移動はコスト0、ワープでの移動はコスト1なので、 隣への移動時はdequeの前に、ワープでの移動時はdequeの後に詰めることで、コストの低いところから探索を行うことができる。
ただし、一度訪れた点もコストが改善するときには再度訪問したいので、visitedフラグの管理での訪問判定は結局していない。 Submission #16206218 - AtCoder Beginner Contest 176
大きな数を扱うときに文字列として扱う以外の方法を学んだのでメモ。
今回のC問題のi番目は、
と書ける。
ABC174 C問題のEditorial より引用。 https://img.atcoder.jp/abc174/editorial.pdf
などといった巨大な値を直接
で割ろうとするべきではありません。その代わ りに、 10i を
倍して
仕切りを入れて、部分問題にわける。
sum(ceil(A_i / X) - 1) < kと条件を書き換えて、二分探索
...
蟻本ベースにサンプルコードをきちんと書いたので、メモを残しておきます。
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());
}