バチャ途中で2時間抜けるナメ腐ったマネをしたらFまでしか解けませんでした。
新年早々幸先の悪い感じです。
1回目はHまで、2回目はGまで過去問を埋めてて、3回目はリアタイ受験していて中級(64点)でした。
今回の気持ち
A~C:かんたん
D:むずかしい
E:やるだけなんだけど大変
F:Eより簡単
~~
G:解けなかった
H:Gよりかんたん
I:Gよりかんたん
B - 上書き
後ろから見て、まだ出てきてないアルファベットを末尾に足していって最後に反転する。
D - リーディングゼロ
どういう実装をしたら綺麗にできるのかわからん……(;;)
まず2次元配列(~)を持って、0を抜いた桁数ごとに分けてpairで格納。
最後に桁数ごとにソートすると、2つめのほうで-1をかけてるから同じ数でも前についてる0の個数が多いほど前に来るので、もう一度0をつけなおして出力する。
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int MOD = 1000000007;
const int INF = 1e9;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
signed main(){
int N;
cin >> N;
vector<string> A(N);
rep(i, N) cin >> A[i];
vector<pair<string, int>> num(N);
vector<vector<pair<string, int>>> B(100001);
for( int i = 0; i < N; i++ ){
int len = A[i].size();
if( string(len, '0') == A[i] ){
B[0].push_back(make_pair("", -1*len));
continue;
}
for( int j = 0; j < len; j++ ){
if( A[i][j] != '0' ){
B[len-j].push_back(make_pair(A[i].substr(j), -1*j));
break;
}
}
}
for( int i = 0; i <= 100000; i++ ){
if( B[i].size() > 0 ){
sort(B[i].begin(), B[i].end());
for( int j = 0; j < B[i].size(); j++ ) cout << string(-1*B[i][j].second, '0') << B[i][j].first << "\n";
}
}
}
E - ハンコ
これも実装が下手だからすごく面倒くさくなってしまった……(;;)
は入力に加えて上下左右に+10ずつ余白を取る(余白は#で埋める)のと、外に関数(?)を書くのかなり苦手だけどチェック部分はそうするようにした(それでもめっちゃ汚い)。
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int MOD = 1000000007;
const int INF = 1e9;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
bool check(int h, int w, const vector<string> &S, const vector<string> &T){
bool ok = 0;
for( int i = 0; i < 10+h; i++ ){
for( int j = 0; j < 10+w; j++ ){
bool fg = 1;
for( int k = 0; k < h; k++ ){
for( int l = 0; l < w; l++ ){
if( S[i+k][j+l] == '#' && T[k][l] == '#' ){
fg = 0;
break;
}
}
}
if( fg ) ok = 1;
}
}
return ok;
}
bool check2(int h, int w, const vector<string> &S, const vector<string> &Ta){
bool ok = 0;
for( int i = 0; i < 10+h; i++ ){
for( int j = 0; j < 10+w; j++ ){
bool fg = 1;
for( int k = 0; k < w; k++ ){
for( int l = 0; l < h; l++ ){
if( S[i+k][j+l] == '#' && Ta[k][l] == '#' ){
fg = 0;
break;
}
}
}
if( fg ) ok = 1;
}
}
return ok;
}
signed main(){
int H, W;
cin >> H >> W;
vector<string> A(H);
rep(i, H) cin >> A[i];
vector<string> S(H+20);
for( int i = 0; i < 10; i++ ) S[i] = string(20+W, '#');
for( int i = 10; i < 10+H; i++ ){
S[i] = string(10, '#') + A[i-10] + string(10, '#');
}
for( int i = 10+H; i < 20+H; i++ ) S[i] = string(20+W, '#');
vector<string> T(H);
rep(i, H) cin >> T[i];
vector<string> Ta(W);
int c = 0;
for( int i = W-1; i >= 0; i-- ){
string m = "";
for( int j = 0; j < H; j++ ) m += T[j][i];
Ta[c] = m;
c++;
}
bool fg = check(H, W, S, T);
reverse(T.begin(), T.end());
rep(i, H) reverse(T[i].begin(), T[i].end());
if( fg == 0 ) fg = check(H, W, S, T);
if( fg == 0 ) fg = check2(H, W, S, Ta);
reverse(Ta.begin(), Ta.end());
rep(i, W) reverse(Ta[i].begin(), Ta[i].end());
if( fg == 0 ) fg = check2(H, W, S, Ta);
if( fg ) cout << "Yes" << endl;
else cout << "No" << endl;
}
F - 一触即発
制約が小さいので薬の組み合わせについてbit全探索をする。「新たに追加すると爆発するような薬品 」についてはsetで管理する。
G - ヘビ
これも制約が小さいので何をやっても計算量は大丈夫そうで、どこを通ったかチェックしながらのdfsを書いてみるけど通らず……。
後で教えてもらうと、return;を書いているところが間違っていて(return;で再帰関数が終了しないので)、exit(0);にしたら無事ACできた。
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int MOD = 1000000007;
const int INF = 1e9;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
void dfs( int sh, int sw, int& h, int& w, int& k, vector<string> &S, vector<pair<int, int>>& ans, vector<vector<bool>> &fg){
fg[sh][sw] = 1;
ans.emplace_back(make_pair(sh, sw));
if(ans.size()==k){
cout << k << "\n";
rep(i, k) cout << ans[i].first+1 << " " << ans[i].second+1 << "\n";
exit(0);
}
for (int dir = 0; dir < 4; ++dir){
int nh = sh + dx[dir];
int nw = sw + dy[dir];
if (nh < 0 || nh >= h || nw < 0 || nw >= w) continue;
if( S[nh][nw] == '.' ) continue;
if( fg[nh][nw] ) continue;
dfs(nh, nw, h, w, k, S, ans, fg);
}
fg[sh][sw] = 0;
ans.pop_back();
}
signed main(){
int H, W;
cin >> H >> W;
vector<string> S(H);
rep(i, H) cin >> S[i];
int k = 0;
rep(i, H){
rep(j, W){
if( S[i][j] == '#' ) k++;
}
}
vector<pair<int, int>> ans;
vector<vector<bool>> fg(H, vector<bool>(W));
rep(i, H){
rep(j, W){
if( S[i][j] == '#' ) dfs(i, j, H, W, k, S, ans, fg);
}
}
}
H - コンベア
各点からゴールに向かってBFSをすると間に合わないので、ゴールからどこまで行けるかのBFSをする(ので、矢印のことは反対向きにとらえる)。
I - 避難計画
避難所について、標高が高いものから順にBFS。辺は逆に標高が低いほうから高いほうに張る。既に見たものでも、distの距離が今より遠い場合は更新する。計算量はわからない……。
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int MOD = 1000000007;
const int INF = 1e9;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
signed main(){
int N, M, K;
cin >> N >> M >> K;
vector<int> H(N);
rep(i, N) cin >> H[i];
vector<pair<int, int>> C(K);
rep(i, K){
int c;
cin >> c;
c--;
C[i] = {H[c], c};
}
Graph G(N);
rep(i, M){
int A, B;
cin >> A >> B;
A--;
B--;
if( H[A] > H[B] ) swap(A, B);
G[A].emplace_back(B);
}
sort(C.rbegin(), C.rend());
vector<int> dist(N, -1);
queue<int> que;
for( int i = 0; i < K; i++ ){
dist[C[i].second] = 0;
que.push(C[i].second);
while( !que.empty() ){
int v = que.front();
que.pop();
for( auto nv : G[v] ){
if( dist[nv] != -1 && dist[nv] <= dist[v]+1 ) continue;
dist[nv] = dist[v]+1;
que.push(nv);
}
}
}
rep(i, N) cout << dist[i] << "\n";
}
「アルゴリズム」の検定だからABCより実装が多くなるのかなーと思いました。算数できないのでこっちのほうが好き説はあります(?)
J以降もぼちもち見ていきたいです。