【AtCoder】ABC301 A~Dの解説・反省
A - Overall Winner
問題概要
T,Aからなる文字列が与えられるので、どちらが多いかを出力せよ。- ただし、同数だったとき、先に最後のが出現した方を出力する。
解説
基本的にはやるだけ。T,Aの数をカウントして多い方を出力。
nが偶数で、n/2までカウントされた瞬間そっちを出力。
/*mainまで省略*/ using lint = long long; int main() { lint n; cin >> n; string s; cin >> s; lint cnt_t = 0; lint cnt_a = 0; for (int i = 0; i < n; i++) { if (s[i] == 'T') { cnt_t++; if (n % 2 == 0 && cnt_t == n / 2) { cout << "T" << endl; return 0; } } else { cnt_a++; if (n % 2 == 0 && cnt_a == n / 2) { cout << "A" << endl; return 0; } } } if (cnt_t > cnt_a) { cout << "T" << endl; } else { cout << "A" << endl; } }
勉強になったこと
「同点のとき、先に勝った人が勝利」
→逆に言えば最後に負けた人が勝利だから、 cout << char('T' + 'A' - s.back()) << endl;で判定できるのが勉強になった！
参考：公式解説
B - Fill the Gaps
問題概要
長さNの数列Aに対して、以下を操作せよ。
1. Aのどの隣接する2項の差の絶対値も1ならそれを出力
2. そうでない箇所について、その間に連続する数字を補完し、差の絶対値が1になるようにする
解説
こういうのは愚直にやってもいいけど、別の配列に入れて、後から加工してつじつまが合うようにならないか考えるのが大事だと思う。
今回は、vector<int>を用意しておいて、絶対値の差が1ならそのまま元の値をpush_backして、そうでないなら連番を1つずつpush_backしていけばいいと分かった。
int main() { lint n; cin >> n; vector<lint> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<lint> ans; ans.push_back(a[0]); for (int i = 0; i < n - 1; i++) { const lint diff = abs(a[i] - a[i + 1]); if (diff == 1) { ans.push_back(a[i + 1]); continue; } if (a[i] < a[i+1]) { for(lint j = a[i] + 1; j <= a[i + 1]; j++) { ans.push_back(j); } } else { for (lint j = a[i] - 1; j >= a[i + 1]; j--) { ans.push_back(j); } } } for (const auto val : ans) { cout << val << " "; } cout << endl; }
C - AtCoder Cards
問題概要
英小文字か@から成る文字列S,Tが与えられる。以下の操作をしたとき2つの列が一致するかを判定せよ。
S,Tの各文字を適当に並べ替えたものをそれぞれ1列に並べ、計2列作る。@をa,t,c,o,d,e,rの中の1文字に置換する。
解説
そもそもちょっと元の問題文が難しく書かれているので、そういうときは自分なりに問題を必要十分に（過不足なく）言い換えると見通しが良くなることが多い。
要は、以下を満たせばいいことが分かる。
S,Tに含まれるa,t,c,o,d,e,r,@以外の文字の数がそれぞれ一致する。- 一致しない
a,t,c,o,d,e,rについて、(一致しない数) <= (@の数)である。
1を簡単に検証できるのはmapなのでそれを使う。あとは2だが、mapにて一致していないときにその数だけ@の数から引いていって、0を下回らなければいい。
実装では英小文字をintに変換したけど、そこまではしなくてもいい。そのせいで逆にatcoderを数字にしないといけなくなって余計面倒だった...。
int main() { const string atc = "atcoder"; // 0 2 3 4 14 17 19 string s, t; cin >> s >> t; map<int, int> s_map; map<int, int> t_map; for (int i = 0; i < s.size(); ++i) { s_map[s[i] - 'a']++; t_map[t[i] - 'a']++; } for (int i = 0; i < 26; i++) { // 数が同じならスルー if (s_map[i] == t_map[i]) continue; // atcoderじゃないとこで数が違ったらNo if(i != 0 && i != 2 && i != 3 && i != 4 && i != 14 && i != 17 && i != 19) { cout << "No" << endl; return 0; } if (s_map[i] < t_map[i]) { const lint diff = t_map[i] - s_map[i]; // s_map[-33] -> `@`の数 // 合ってない数だけ`@`を減らしていく s_map[-33] -= diff; if(s_map[-33] < 0) { cout << "No" << endl; return 0; } } else { const lint diff = s_map[i] - t_map[i]; t_map[-33] -= diff; if (t_map[-33] < 0) { cout << "No" << endl; return 0; } } } cout << "Yes" << endl; }
ここからは解けなかったので反省。
D - Bitmask
問題概要
0,1,?からなる文字列Sがある。Sの?をすべて0か1に置き換えて2進数としたときの値の集合の中で、int N以下の最大値を出力せよ。- そのような値がない場合は
-1を出力せよ。
考えたこと（メモ）
- N以下のうち最大→
lower_boundかとちょっと思ったけど違う（Tは最大であるからそもそも無理）
- 適当な例を考えたとき、上下で違うbitのとこが大事だと分かる
同じ桁数のとき、
S: ?1???
N: 10110
-> 01111
S: ?010? N: 11010 -> 10101
このとき、一番上のbitで違うやつだけ考える S: 1 N: 0 なら、一番上の桁の?1は01、下の桁は1で埋める 上に1が無ければ-1 S: 0 N: 1 なら、上はトレースして、下は1で埋める
ここまで考えたけど時間無くなって終了！
多分この考察のまま実装したらいけそう（公式解説もそんな感じだった）だけど、もっと簡単な方法も書いてあった
反省
- まず
-1を出力する判定が上手く分かっていなかったので整理した方が良かった- 貪欲に全部0で埋めても
N以下にならなかったら-1でよかった
- 貪欲に全部0で埋めても
-1じゃないとき、上から順にNを超えないように判定しながら1を埋めていけばいい- 2進数を10進数に変換するのはそんなに計算時間かからないから、別にループ内に書いても基本大丈夫
int main() { string s; lint n; cin >> s >> n; lint ans = 0; const lint s_size = s.size(); // 2進数を10進数に変換する for (int i = 0; i < s_size; i++) { if(s[i] == '1') { ans += 1LL << (s_size - i - 1); } } // このとき、ansはsにて`?`を全て`0`にしたときの値になっている if(n < ans) { cout << -1 << endl; return 0; } for (int i = 0; i < s_size; i++) { if(s[i] == '?') { // 貪欲に1を選んでいって、大丈夫だったらansを更新する if(ans + (1LL << (s_size - i - 1)) <= n) { ans += 1LL << (s_size - i - 1); } } } cout << ans << endl; }
（以下編集中...(編集しないかも)）
E
- [tex: w<=300, h <= 300, t <= 2*106]
- 'dp[w][h][time][..]'ってやるとオーダーやばいからdp無理
F
考えたこと(メモ)
- 同じ大文字が２つ、i<kで存在 && 小文字がi<k<jの範囲に存在 && 大文字がk<jに存在
- 4文字目の大文字がない
- 3文字目の小文字がない
- 1,2文字目の大文字がない
いつか実力が追い付いたら書きます...。
