B
double型の絶対値はfabs()で返す。
C
# include<iostream>
# include<vector>
# include<algorithm>
# include<string>
# include<map>
# include<math.h>
# include<queue>
# include<deque>
# include<stack>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
int main() {
int N, M;
cin >> N >> M;
vector<pii>v(M);
vector<int>x[100010];
for (int i = 0; i < M; ++i) {
int p, y;
cin >> p >> y;
v.at(i).first = p;
v.at(i).second = y;
x[p].push_back(y);
sort(x[p].begin(), x[p].end());
}
for (int i = 0; i < M; ++i) {
int num;
for (int j = 0; j < x[v.at(i).first].size(); ++j) {
if (x[v.at(i).first][j] == v.at(i).second) {
num = j + 1;
}
}
int a = 0, b = 0;
int z = v.at(i).first;
while (z > 0) {
a++;
z /= 10;
}
int y = num;
while (y > 0) {
b++;
y /= 10;
}
for (int j = 0; j + a <= 5; ++j) {
cout << 0;
}
cout << v.at(i).first;
for (int j = 0; j + b <= 5; ++j) {
cout << 0;
}
cout << num;
cout << endl;
}
return 0;
}
３つTLEくらった。なんかクソコードを乗せるブログだな完全に。最初からだけど
# include<iostream>
# include<vector>
# include<algorithm>
# include<string>
# include<map>
# include<math.h>
# include<queue>
# include<deque>
# include<stack>
# include<cstdio>
# include<utility>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
int main() {
int N, M;
cin >> N >> M;
vector<vector<pii>>A(N);//A[k-1]の中に、県kに属する市の誕生年と番号をを格納していく
for (int i = 0; i < M; ++i) {
int P, Y;
cin >> P >> Y;//県の番号を1下げる
A[P - 1].push_back(pii(Y, i));//市の誕生年と番号を格納
}
vector<pii>B(M);//B[k].firstは市kの属する県、secondは市kの属する県の中での誕生年の順番
for (int i = 0; i < N; ++i) {//
sort(A[i].begin(), A[i].end());
for (int j = 0; j < A[i].size(); ++j) {
B[A[i][j].second] = pii(i, j);
}
}
for (int i = 0; i < M; ++i) {
B[i].first++; B[i].second++;
string newpr = to_string(B[i].first);
string newpl = to_string(B[i].second);
for (int j = 0; j < 6 - newpr.length(); ++j) {
cout << 0;
}
cout << newpr;
for (int j = 0; j < 6 - newpl.length(); ++j) {
cout << 0;
}
cout << newpl;
cout << endl;
}
return 0;
}
D
横W列高さHの縦棒に対して適当に横棒を入れてあみだくじをつくり、一番左から出発してK番目に到達するあみだくじの個数を求める
動的計画法で、高さIにおける左からj本目へ到達するあみだくじの横棒の起き方をカウントしていけばよいIからI+1への推移は高さI+1での横棒の起き方全てに対してあみだくじとして不適切なものを除いて適宜加算を行う。
# include<iostream>
# include<vector>
# include<algorithm>
# include<string>
# include<map>
# include<math.h>
# include<queue>
# include<deque>
# include<stack>
# include<cstdio>
# include<utility>
# include<set>
# include<list>
# include<cmath>
# include<stdio.h>
# include<cstdio>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9 + 7;
int main() {
int H, W, K;
cin >> H >> W >> K;
vector<vector<int>>dp(H + 1, vector<int>(W, 0));
dp[0][0] = 1;
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
//同じ列の線パターン全てをbit全探索を使って表している
for (int k = 0; k < 1 << (W - 1); ++k) {
bool ok = true;
//l番目に線があれば１ここではとなりあっていた場合を弾いている
for (int l = 0; l < W - 2; ++l) {
if (((k >> l) & 1) && (k >> (l + 1)) & 1)
ok = false;
}
if (ok) {
if (j >= 1 && ((k >> (j - 1)) & 1)) {
dp[i + 1][j - 1] += dp[i][j];
dp[i + 1][j - 1] %= INF;
}
else if (j <= W - 2 && ((k >> j) & 1)) {
dp[i + 1][j + 1] += dp[i][j];
dp[i + 1][j + 1] %= INF;
}
else {
dp[i + 1][j] += dp[i][j];
dp[i + 1][j] %= INF;
}
}
}
}
}
cout << dp[H][K - 1] << endl;
return 0;
}
bitdpでの解き方
ところで、次のような事実がある。
縦棒がW本のあみだくじのある位置での横線の置き方の数はフィボナッチ数列の第I項をFiとするとFwに等しい。
これは帰納法で証明できる。
左から順に縦棒に1,2,,,W-2,W-1,Wと番号をつける。W=0,1の時はそれぞれ1通りである。W-2,W-1での成立を仮定してWのときの横棒の置き方を求める。W-2,W-1での成立を仮定してWの時の置き方の数を求めよう。WとW-1の間に横棒を置かない時横棒の置き方は１からW-1までの横棒の置き方に等しくFw-1通りある。縦棒WとW-1の間に横棒を置くとき横棒の置き方は１からW-2までの横棒の置き方に等しくFw-2通りある。よってWのときの横棒の置き方の数はFw-1+Fw-2=Fw通りである。
これを利用する。dp[I][j]からdp[I+1][j-1]への遷移を考える。
このような遷移が起きるための条件は
1,jとj-1の間に横棒がある。
2,j-1とj-2の間に横棒がない。
3,jとj+1の間に横棒がない。
の3つである。これらの条件を満たすような位置I+1での横棒の置き方は縦棒1から縦棒j-2までの横棒の置き方と縦棒ｊから縦棒Wまでの横棒の置き方の積である。から、Fj-2*FW-j通りある。
# include<iostream>
# include<vector>
# include<algorithm>
# include<string>
# include<map>
# include<math.h>
# include<queue>
# include<deque>
# include<stack>
# include<cstdio>
# include<utility>
# include<set>
# include<list>
# include<cmath>
# include<stdio.h>
# include<cstdio>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9 + 7;
int H, W, K;
ll fib[10] = { 0 };
ll dp[101][10] = { {0} };//dp[x][y]で高さxにおける左からy本目に到達する横棒の置き方
int main() {
cin >> H >> W >> K;
fib[0] = 1; fib[1] = 1;
for (int i = 2; i <= 9; ++i) {
fib[i] = fib[i - 1] + fib[i - 2];
}
dp[0][1] = 1;
for (int i = 0; i < H; ++i) {
for (int j = 1; j <= W; ++j) {
if (j >= 2) {
dp[i + 1][j - 1] += dp[i][j] * (fib[j - 2] * fib[W - j]);
dp[i + 1][j - 1] %= INF;
}
if (j <= W - 1) {
dp[i + 1][j + 1] += dp[i][j] * (fib[j-1] * fib[W - j-1]);
dp[i + 1][j + 1] %= INF;
}
dp[i + 1][j] += dp[i][j] * (fib[j-1] * fib[W - j]);
dp[i + 1][j] %= INF;
}
}
cout << dp[H][K] << endl;
return 0;
}
いやー頭いい