[AtCoder] ARC 108 B – Abbreviate Fox
括弧の対応の問題で良く使うスタックを使います。スタックに \( s \) の先頭から入れていき、\( s_i = o \) のとき、スタックの先頭から “xf” と積まれていたら “fox& ...
[AtCoder] ARC 108 A – Sum and Product
\( xy = P\) となるような \( x, y \) を全探索します。このとき、探索は \( x \) についてだけでよく、\( 1 \leq x \leq \sqrt{P} \) の範囲で十分です。
コード#in ...
[AtCoder] ABC 104 C – All Green
問題を解く順番は関係ないので、コンプリートする問題を全探索します。これは、ビット全探索で解くことはできます。コンプリートした問題の集合を \( 2 \) 進数で表し、点数が \( G \) 未満ならば、コンプリートしていない問 ...
[AtCoder] ABC 169 E – Count Median
自然数 \( m \) を
\
とします。
\( N \) が奇数のとき中央値の最小値は \( A \) を昇順に並べた時の \( A_{m} \) となり、最大値は \( B \) を昇順 ...
[AtCoder] ABC 183 F – Confluence
生徒がどの集団に属するかは Union-Find で管理し、ある集団における各クラスの人数はマップを用いて管理します。ある集団をマージするとき、各クラスの情報も更新する必要があるので、人数の少ない集団の各クラスの人数を人数の多 ...
[AtCoder] ABC 183 E – Queen on Grid
まず、壁がない場合を考えます。
\( d(i, j) \) をマス \( (1, 1)\) から マス \( (i, j) \) への移動方法の数とします。\( d(i, j) \) は、\( n = \min ( ...
[AtCoder] ABC 183 D – Water Heater
ある時間において使用される水の最大値が \( W \) を超えなければ良いので、いもす法を使います。
コード#include <bits/stdc++.h>using namespace std;typedef l ...
[AtCoder] ABC 183 C – Travel
\( N \) 個の順列の中で先頭が \( 1 \) であるものを探索します。したがって、順列を生成して全探索します。
コードnext_permutation#include <bits/stdc++.h>usin ...
[AtCoder] ABC 183 B – Billiards
点 \( (S_x, S_y) \) と 点 \( (x, 0) \) を通る直線の傾きを \( a_1\) とし、点 \( (G_x, G_y) \) と 点 \( (x, 0) \) を を通る直線の傾きを \( a_2\ ...
[AtCoder] ABC 182 E – Akari
\( H \) 行 \( W \) 列の情報を \( g(i, j) \) とします。\( g(i, j) = 1 \) のとき電球があり、\( g(i, j) = 2 \) のとき壁があるとします。ここで、\( g(i, j ...