ABC041D
解説を読んでも満点解法がなかなかわからず苦労したのでそのメモです。
まずトポロジカルソートは有向辺が全て1方向へ向くようにソートをソートをすることです。入力例1についてトポロジカルソートを行ってみると以下の2通りになります。
このトポロジカルソートの種類を求める問題と考えることができます。
解説のように漸化式を計算することでなぜトポロジカルソートができるか考えます。頂点vをもっとも右に置くことができれば、頂点vを除いた部分集合について同じことを再帰的に行うことでトポロジカルソートとなります。部分集合Sの中でもっとも右における頂点vとは vからS-{v} への有向辺がないことと同義です。その部分集合の他の頂点に対する有向辺があると左向きの有向辺が生じてしまうためトポロジカルソートの条件を満たせないということです。
このような集合を含んでいる漸化式を扱うときにはBitDPがよくある手段（らしい）です。
頂点 1 2 3 4
0 0 1 0 S = {3}
1 1 0 1 S = {1, 2, 4}といったようにビットが1の部分の頂点を含んでいる部分集合と対応させることで集合を表現します。0から2^Nまで小さい方から順に計算していくことで答えを求めることができます。これをコードで実装します。
以下蛇足。bit演算に慣れていなかったこともあってBitDPの実装に時間をかけてしまった。集合を扱うときは鉄板の方法っぽい。あとN<=16とかでO(N!)だと間に合わないけどO(2^N)だと間に合うときはBitDPを使う方法のことが多いらしい。Nの制約から使うアルゴリズムが想像つくようになってきた。
Atomで使ってるパッケージについて
Package
あとで忘れて困る未来が浮かんだので忘備録として書いておくことにしました。C++用にパッケージをいじってます。
OS: Windows10 64bit
コンパイラ: MinGW(GCC)
atom-beautify
オートフォーマットしてくれるパッケージです。整形にClang-formatを使ってるのでClangのインストールが必須。
以下のやり方でインストールしました。
windowsでatom-beautifyを使おうとしてハマったこと - Qiita
LLVM Clang の Windows へのインストールと使い方 | プログラマーズ雑記帳
autocomplete-clang
補完をしてくれるパッケージです。autocomplete-plusが前提として必要ですが最近のなら標準で入ってます。これもClangのインストールが必須です。
linter, linter-gcc
静的コード解析、つまりエラーの位置をAtomのエディタ上に出してくれるパッケージです。いちいちコマンドプロンプトでコンパイルしてエラーメッセージと行数を照らし合わせてなんて手間はもういりません。linter は linter-gccの前提として必要です。linter-gccの設定にgccやg++のパスを入れる必要があります。MinGWでデフォルトだと C:\MinGW\bin\g++.exe です。
file-icons
ツリーやタブのアイコンを拡張子に合わせて変えてくれるパッケージです。一目でファイルの種類がわかるので気に入ってます。
highlight-line
カーソルが入ってる行をハイライトしてくれるパッケージです。これでカーソルを見逃す心配はありません。
japanese-menu
日本語化してくれるパッケージです。
minimap
エディタの右側にコードの全体図を表示してくれるパッケージです。
minimap-autohide
minimapを必要がない時は隠してくれるパッケージです。コード書いてる時は使わないので消えててくれるので便利です。
Design
font
Ricty Diminished Discordを使ってます。環境設定にフォント名を入れる欄があるのでそこに入力して再起動すればフォントが切り替わります。Ricty Diminished Discordのインストールは以下を参考に行いました。
見やすいプログラミング用フォント「Ricty Diminished」をWindowsにインストールしてSublime Textで利用する方法
style.less
選択範囲が灰色で見づらかったので以下のサイトを参考に直しました。
Atomで選択範囲の背景色を見やすく変更する – nocorica
コメントの色が灰色で同様に見づらかったのでstyle.lessに以下の記述を追加して暗い黄緑のような色に変更しました。
atom-text-editor::shadow {
.comment {
color: fade(greenyellow, 40%);
}
}
ABC049D
自力では手も足も出なかったのでeditorialと解説放送を参考に実装しました。
youtu.be
https://youtu.be/jvAX9Z7beLg
グラフの連結を管理するために、グループ分けを管理するためのデータ構造であるUnion-Find木を使います。
道路での連結を表すUnion-Find木と電車での連結を表すUnion-Find木をそれぞれ用意し管理します。
Union-Find木では連結している頂点同士では根となるノードが同じになります。
よって、道路と電車双方で連結している頂点はその頂点の根がそれぞれ同じとなります。
そのような頂点の数を数えることで両方で連結している頂点数を求めることができます。
GCCとclang間違えてCE出したり、DじゃなくてAに提出したりしてたので本番でやらかさないよう気をつけたい。
あと同じpairを数えるのにcount使ったらTLEだった。よくよく考えたらO(N^2)だし当たり前だった。
ABC030を解いてみた
A問題
if文で比較しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
int main(void)
{
double a, b, c, d;
cin >> a >> b >> c >> d;
if(b/a > d/c) cout << "TAKAHASHI" << endl;
else if(b/a < d/c) cout << "AOKI" << endl;
else cout << "DRAW" << endl;
return 0;
}
B問題
短針が5分刻み以外にも移動することと小さい方の角度を取得することに気をつけて実装しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
int main(void)
{
int n, m;
cin >> n >> m;
n %= 12;
double angle = abs(n*30 + m*0.5 - m*6);
angle = min(angle, 360-angle);
cout << fixed << setprecision(6) << angle << endl;
return 0;
}
C問題
乗れる中で最も早い飛行機に乗る貪欲で解きました。計算量はO(n)のはずです。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define N_MAX 100000
#define M_MAX 100000
int main(void)
{
int n, m, x, y;
cin >> n >> m;
cin >> x >> y;
ll a[N_MAX], b[M_MAX];
for(int i=0; i<n; i++) {cin >> a[i];}
for(int i=0; i<m; i++) cin >> b[i];
// true ならAにいる
bool isA = true;
int ans=0, i=0, j=0;
ll now=0;
while(i < n && j < m) {
if(isA) {
// a[i]がnow以上になるまで
while(a[i] < now) {
i++;
//乗れる飛行機がもうない
if(i == n) {cout << ans << endl; return 0;}
}
now = a[i] + x;
isA = false;
} else {
// b[j]がnow以上になるまで
while(b[j] < now) {
j++;
// 乗れる飛行機がもうない
if(j == m) {cout << ans << endl; return 0;}
}
now = b[j] + y;
ans++;
isA = true;
}
}
return 0;
}
D問題
10^10000ってlong longでも受け取れないしどうするんだ…？とか思って分からなかったので自力では部分点まで実装。
//部分点
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define MAX_N 100000
int main(void)
{
int n, a, b[MAX_N];
ll k;
cin >> n >> a; a--;
cin >> k;
for(int i=0; i<n; i++) {cin >> b[i]; b[i]--;}
//ループに入るまで
bool toLoop[MAX_N] = {false};
int c_num = a, toLoop_num = 0;
vector<int> v_toLoop;
while(true) {
toLoop[c_num] = true;
toLoop_num++;
v_toLoop.push_back(c_num);
c_num = b[c_num];
if(toLoop[c_num]) break;
//cout << "toLoop_num:" << toLoop_num << " c_num:" << c_num << endl;
}
//ループ中
bool loop[MAX_N];
int loop_num = 0;
vector<int> v;
while(true) {
loop[c_num] = true;
loop_num++;
v.push_back(c_num);
c_num = b[c_num];
if(loop[c_num]) break;
//cout << "loop_num:" << loop_num << " c_num:" << c_num << endl;
}
if(toLoop_num > k) cout << v_toLoop[k]+1 << endl;
else cout << v[(k-toLoop_num)%loop_num]+1 << endl;
return 0;
}string型で入力を受け取って、桁ごとに計算することでMODを計算できる(by解説)で実装しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define MAX_N 100000
int main(void)
{
int n, a, b[MAX_N];
string k;
cin >> n >> a; a--;
cin >> k;
for(int i=0; i<n; i++) {cin >> b[i]; b[i]--;}
//ループに入るまで
bool toLoop[MAX_N] = {false};
int c_num = a, toLoop_num = 0;
vector<int> v_toLoop;
while(true) {
toLoop[c_num] = true;
toLoop_num++;
v_toLoop.push_back(c_num);
c_num = b[c_num];
if(toLoop[c_num]) break;
//cout << "toLoop_num:" << toLoop_num << " c_num:" << c_num << endl;
}
//ループ中
bool loop[MAX_N];
int loop_num = 0;
vector<int> v;
while(true) {
loop[c_num] = true;
loop_num++;
v.push_back(c_num);
c_num = b[c_num];
if(loop[c_num]) break;
//cout << "loop_num:" << loop_num << " c_num:" << c_num << endl;
}
/*
cout << "loop_num:" << loop_num << " toLoop_num:" << toLoop_num << endl;
for(int i=0; i<toLoop_num; i++) cout << v_toLoop[i] << " "; cout << endl;
for(int i=0; i<loop_num; i++) cout << v[i] << " "; cout << endl;
*/
//kが6桁あればn<=10^5だし閉路に入る気がした
if(k.size() < 7) {
int num_k = stoi(k);
int c_num = a;
for(int i=0; i<num_k; i++) c_num = b[c_num];
cout << c_num + 1 << endl;
return 0;
}
ll k_mod_c = 0;
for(int i=0; i<k.size(); i++) k_mod_c = (k_mod_c*10+k[i]-'0')%loop_num;
while(k_mod_c < toLoop_num) k_mod_c += loop_num;
c_num = a;
for(int i=0; i<k_mod_c; i++) c_num = b[c_num];
cout << c_num+1 << endl;
return 0;
}
ABC029を解いてみた
A問題
文字列の最後にsを連結しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
int main(void)
{
string s;
cin >> s;
cout << s + 's' << endl;
return 0;
}
B問題
全ての文字列についてrが含まれているか全探索しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
int main(void)
{
string s[12];
for(int i=0; i<12; i++) cin >> s[i];
int ans = 0;
for(int i=0; i<12; i++) {
for(int j=0; j<s[i].size(); j++) {
if(s[i][j] == 'r') {ans++; break;}
}
}
cout << ans << endl;
return 0;
}
C問題
8重のforループを書く気はしなかったので深さ優先探索で全列挙しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
int n;
char s[3] = {'a', 'b', 'c'}, ans[10];
int dfs(int i) {
if(i == n) {cout << ans << endl; return 0;}
for(int j=0; j<3; j++) {
ans[i] = s[j];
dfs(i+1);
}
return 0;
}
int main(void)
{
cin >> n;
dfs(0);
return 0;
}
D問題
9まで、99まで、999まで…に1が出てくる数を求め、この数と各桁の数に応じて場合分けして全パターンを求めました。
昔算数でこんな問題解いた気がします。解説の解法がシンプルでわかりやすかった。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
//10のべき乗を求める
ll mypow(int i) {
ll ret = 1;
for(int j=0; j<i; j++) ret *= 10;
return ret;
}
int main(void)
{
ll memo[15], n, ans = 0;
cin >> n;
//桁数を求める
int digit = 0;
ll _n = n;
while(_n > 0) {
_n /= 10;
digit++;
}
// 9まで、99まで、999まで…に含まれる1の数を求める
memo[0] = 1;
for(int i=1; i < digit; i++) {
memo[i] = mypow(i) + (memo[i-1]*10);
}
int temp;
for(int i=digit-1; i > 0; i--) {
// i桁目の数
temp = n / mypow(i);
if(temp >= 2) {
ans += mypow(i) + temp*memo[i-1];
} else if(temp == 1) {
// a = n % 10^i
ll a = n - temp*mypow(i);
ans += a + memo[i-1] + 1;
}
// temp * 10^i までに含まれるiの数が求められている
n -= temp * mypow(i);
}
// 1の位が1以上なら1の数はプラス1
if(n >= 1) {ans++;}
cout << ans << endl;
return 0;
}
ABC028を解いてみた
A問題
条件に合わせて分岐して出力しました。Perfectのスペル間違えてWA出したので気をつけたい。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
int main(void)
{
int n;
cin >> n;
if(n <= 59) cout << "Bad" << endl;
else if(n <= 89) cout << "Good" << endl;
else if(n <= 99) cout << "Great" << endl;
else cout << "Perfect" << endl;
return 0;
}
B問題
文字コードでint(s[i])-int('A')が0,1,2,3,4,5になるのを使いました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
int main(void)
{
string s;
cin >> s;
int a[6]={0};
for(int i=0; i<s.size(); i++) {
a[int(s[i])-int('A')]++;
}
cout << a[0] << " " << a[1] << " " << a[2] << " " << a[3] << " " << a[4] << " " << a[5] << endl;
return 0;
}
C問題
5C3なら全探索でも余裕そうなので、１番大きい、２番目に大きい、３番目に大きい数字を記録しつつ全ての組み合わせについて全探索しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
int main(void)
{
int a[5];
cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
int ret = 0, max1 = -INF, max2 = -INF, max3 = -INF;
for(int i=0; i<5; i++) {
for(int j=i+1; j<5; j++) {
for(int k=j+1; k<5; k++) {
ret = a[i] + a[j] + a[k];
if(ret > max1) {
max3 = max2;
max2 = max1;
max1 = ret;
} else if(ret > max2) {
max3 = max2;
max2 = ret;
} else if(ret > max3) {
max3 = ret;
}
}
}
}
cout << max3 << endl;
return 0;
}
D問題
全ての数字が異なる場合、kが一つとkより小さい数が一つ、kより大きい数が一つになります。3P3=6より(k-1)*(n-k)*6通りのパターンが存在します。同じ数が2つの場合、kが二つとk以外の数が一つになります。3P1=3より(n-1)*3通りのパターンが存在します。同じ数が3つの場合、kが3つになります。これは1通りしかありません。答えは {(k-1)*(n-k)*6+(n-1)*3+1}/(n*n*n) になります。
数学っぽく解くだけだったのでそんなに手こずらなかったです。doubleとintで何回かWA出したので気をつけたい。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
int main(void)
{
double n, k;
cin >> n >> k;
double ans = (k-1)*(n-k)*6 + (n-1)*3 + 1;
cout << fixed << setprecision(15) << ans/(n*n*n) << endl;
return 0;
}
