Mujin Programming Challenge 2018 を解いてみた
無人コン(参加者800人以上)の解法メモです。
問題文はAtCoder公式からどうぞ。
注:ソースコードの文字と解法中の文字は無関係です
A - コンテスト名
文字列MUJIN
とS
を比較するだけ。
ソースコード
int main(void) { std::string s; std::string ans; cin >> s; ans = "MUJIN"; for (int i = 0; i < 5; i++) { if (ans[i] != s[i]) { cout << "No" << endl; return 0; } } cout << "Yes" << endl; return 0; }
B - セキュリティ
一文字ずつ読んでシミュレート、0になったらYes
を返して即return 0
。
一番最初に0人だった(A==0
)場合もYes
になることに注意。
ソースコード
int main(void) { cout << std::fixed << std::setprecision(10); int a; cin >> a; std::string s; cin >> s; if (a == 0) { cout << "Yes" << endl; return 0; } for (int i = 0; i < (int)s.size(); i++) { if (s[i] == '+') { a++; } else { a--; } if (a == 0) { cout << "Yes" << endl; return 0; } } cout << "No" << endl; return 0; }
C - 右折
解けてないです><
あるマスで右折するルートの総数は、
左、上、右、下に(そのマスを除いて).
がa,b,c,d個並んでいた場合a*d+b*a+c*b+d*c
=(a+c)*(b+d)
で求められる
このことを利用していけばO(NM)
で解けるはずです(通らないよぅ……)。
D - うほょじご
解法
準備
数の組に対して、
enum status { ns = 0, wj, wa, ac }; //ns(No Submission)は未確認 //wj(Waiting for Judging)は確認中 //wa(Wrong Answer)は無限回操作ができないと確定 //ac(Accepted)は無限回操作ができると確定
を定義する。
status grid[x][y]=(x,y)のstatus
としておく。
初期状態では(0,n)(n,0)
(nは任意の整数)のみwa
、その他はns
。
探索
あるns
の数の組(x,y)
に対して、とりあえず一回操作をしてみる。
操作後の数の組(a,b)
の状態によって、以下のことを行う。
grid[a][b]==ns
の場合
grid[a][b]=wj
として、さらにstd::vector<std::pair<int, int>> vec
に数の組をpush_back()
しておく(後で役に立つ)。
vec
は「探索中に通過したwj
の状態の記録」として考えてください。
その後、(a,b)
をもう一度操作。
grid[a][b]==wa
の場合
wa
になっている組になったら、その数の組が向かう先は(0,n)
か(n,0)
しかない。
探索中に通った数の組についても同じことが言える。
vec
に保存しておいたすべての数の組(s,t)
に対して、grid[a][b]=wa
にする。(vec
に保存しないでgrid[][]
を全探索すると時間が掛かるが、vec
に保存すると計算量を落とせる)
grid[a][b]==ac、grid[a][b]==wj
の場合
探索中にwj
にたどり着いた場合、以降は無限回操作ができる。
また、無限回操作ができると確定した状態にたどり着いた場合、無限回操作ができる(それはそう)。
探索中に通った数の組は無限回操作が可能、と言えるので、vec
に保存しておいたすべての数の組(s,t)
に対して、grid[a][b]=ac
にする。
仕上げ
あとはgrid[x][y]==ac
になっている場所を数えて終了。
ソースコード
void dp_search()
となっていますが、DPと言えるかは人それぞれだと思います。
enum status { ns = 0, wj, wa, ac }; int n, m; status grid[1000][1000]; int rev(int x) { int a, b, c; int reverse; if (x >= 100) { a = x / 100; x -= a * 100; b = x / 10; x -= b * 10; c = x; reverse = c * 100 + b * 10 + a; } else if (x <= 9) { reverse = x; } else { b = x / 10; x -= b * 10; c = x; reverse = c * 10 + b; } return reverse; } void dp_search(int x, int y, std::vector<std::pair<int, int>> vec) { if (grid[x][y] == wa) { //終了措置 for (int i = 0; i < vec.size(); i++) { int a = vec[i].first; int b = vec[i].second; grid[a][b] = wa; } } else if (grid[x][y] == ac || grid[x][y] == wj) { //成功措置 grid[x][y] = ac; for (int i = 0; i < vec.size(); i++) { int a = vec[i].first; int b = vec[i].second; grid[a][b] = ac; } return; } else { grid[x][y] = wj; if (x < y) x = rev(x); else y = rev(y); if (x < y) y -= x; else x -= y; vec.push_back(std::make_pair(x, y)); dp_search(x, y, vec); return; } } int main(void) { cout << std::fixed << std::setprecision(10); cin >> n >> m; for (int i = 0; i <= 999; i++) { for (int j = 0; j <= 999; j++) { grid[i][j] = ns; } } for (int i = 0; i <= 999; i++) { grid[0][i] = wa; grid[i][0] = wa; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (grid[i][j] == ns) { std::vector<std::pair<int, int>> vec; vec.push_back(std::make_pair(i, j)); dp_search(i, j, vec); } } } int answer = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (grid[i][j] == ac) { answer++; } } } cout << answer << endl; return 0; }
これ以降
やってません
まとめ
時間内では2完でした。
腕、落ちてないか?? 青になれるのか???