[AtCoder] ABC 194 E – Mex Min
まず初めに、セットに \( 1 \) から \( M \) までの値を入れます。次に、先頭から \( M \) 個までの \( M \) 未満の値の頻度をマップで管理します。このとき現れた値をセット ...
[AtCoder] ABC 194 C – Squared Error
各要素同士の差の \( 2 \) 乗の和を求めるために、\( A_i \) の頻度を数えます。
コード#include <bits/stdc++.h>using namespace std;typedef long ...
[AtCoder] ABC 189 C – Mandarin Orange
\( x = A_i \) としたとき、\( i – 1\) 番目から先頭に向かって、\( A_i \leq A_j \) を連続的に満たす \( j \) の個数を \( a \) とします。また、\( i + ...
[AtCoder] ARC 108 B – Abbreviate Fox
括弧の対応の問題で良く使うスタックを使います。スタックに \( s \) の先頭から入れていき、\( s_i = o \) のとき、スタックの先頭から “xf” と積まれていたら “fox& ...
[AtCoder] ACL Beginner Contest D – Flat Subsequence
最長増加部分列を解くような感じで解けるみたいですが、あまり理解できませんでした。
まず初めに、\( A_i \leftarrow A_i + K \) と再定義します。ここで、\( d(i) \) を末尾が \( ...
[Codeforces] Codeforces Round #672 (Div. 2) A. Cubes Sorting
バブルソートを行った回数を求めるために、フェニック木 (BIT) を使います。詳しくは下記の参考を参照してください。
コード#include <bits/stdc++.h>using namespace std;t ...
[AtCoder] ABC 179 D – Leaping Tak
動的計画法のようなことを遅延セグメント木を使って行います。\( v_i \) をマス \( i \) まで行く方法の個数とします。初期値は \( v_1 = 1 \) です。区間 \( \) から整数を選 ...
[yukicoder] No. 1226 I hate Robot Arms
関節 \( i \) の位置を \( P_i = (x_i, y_i) \) とします。初期値は、\( P_i = (i, 0) \) となり、\( P_0 = (0, 0) \) となります。ここで、ベクトル \ ...
[AtCoder] ABC 170 E – Smart Infants
ある集合の最大値を管理し、その集合の最大値の中の最小値を答える問題です。これは、multiset を使って管理できるそうです。multiset は順序が保たれます。
ここで、幼稚園 \( i \) のレートの集合を ...
[AtCoder] ABC 157 E – Simple String Queries
区間和のような情報が必要なので、セグメント木を使います。\( 1 \) 文字目から \( i \) 文字目までの文字の種類を \( 2 \) 進数を用いて表現します。これは、\( 26 \) ビットで表現できます。これをセグメ ...