A. Nastya and Rice
問題文
n個の穀物がある
穀物1個の重さはを満たす
n個の穀物の重さの総和がを満たすことが可能かどうか判定せよ
解法
もしくは
なら"NO"
それ以外は"YES"
void solve(){ int n, a, b, c, d; cin >> n >> a >> b >> c >> d; int x = n * (a - b); int y = n * (a + b); int l = c - d; int r = c + d; if(!(r < x || y < l)) puts("YES"); else puts("NO"); }
B. Nastya and Door
問題文
n個の整数からなる数列aと整数kが与えられる
与えられた数列のうち、長さkの連続部分列を考える
この連続部分列の区間を[l:r]で表す
and
を満たす個数をpとする
この時、長さkの連続部分列のうち、p+1が最大かつ、lが最小となるような連続部分列を見つけたい
この連続部分列のp+1とlを出力せよ
解法
読解が難しい
長さkで固定なのでしゃくとりっぽく区間の左端を抜いて、右端を追加しながらpのmaxを取っていく
提出コード
void solve(){ int n, k; cin >> n >> k; vector<int> a(n); REP(i,n) cin >> a[i]; int minL = 0, right = 0; int cnt = 0; int ans = 0; for(int i=1;i<k-1;i++){ if(a[i-1] < a[i] && a[i] > a[i+1]) cnt++; } chmax(ans, cnt); for(int i=k-1;i<n-1;i++){ if(a[i-k+1] < a[i-k+2] && a[i-k+2] > a[i-k+3]) cnt--; if(a[i-1] < a[i] && a[i] > a[i+1]) cnt++; if(chmax(ans, cnt)) minL = i-k+2; // cerr << i << " " << cnt << endl; } cout << ans + 1 << " " << minL + 1 << endl; }
C. Nastya and Strange Generator
問題文
長さnの順列が与えられる
以下の操作で順列を作っていくとき、与えられた順列が作成可能がどうか答えよ
1. をまだ埋まっていない順列のマスのindexのうち、最小のindexと定義する
2. を
を満たす個数と定義する
3. まだ埋まっていないマスのうち、が最大のマスを選ぶ
4. そのようなマスが複数あれば、そのいずれかを選ぶ
解法
読解が辛い
言われてる操作を実装すればいい
一回使ったマスは必ず消えるのでsetなどで管理するのが楽そう
また、その次の要素を取得するのもsetで出来る
後は、を取得したいので、セグ木などを使えば出来る
setとセグ木でゴリ押したけどもっと楽な実装ありそう
提出コード
void solve(){ int n; cin >> n; vector<pair<int,int>> p(n); REP(i,n){ cin >> p[i].first; p[i].second = i + 1; } sort(p.begin(), p.end()); vector<int> cnt(n+1, 1); SegmentTree seg(cnt); set<int> st; REP(i,n) st.insert(i+1); st.insert(INF); bool ok = true; for(auto [x, idx] : p){ int ma = seg.getmax(1, n+2); // cerr << ma << " " << seg.getmax(idx, idx+1) << endl; if(ma != seg.getmax(idx, idx+1)){ ok = false; break; } auto itr = st.find(idx); auto next = itr; next++; // cerr << *itr << " " << *next << endl; if(*next == INF) seg.update(*itr, 0); else{ seg.update(*itr, 0); int t = seg.getmax(*next, *next + 1); seg.update(*next, t + ma); } st.erase(itr); } if(ok) cout << "YES" << endl; else cout << "NO" << endl; }
D. Nastya and Scoreboard
問題文
n個の数字がスコアボードに表示されている
このうち、k本の棒が正常に表示されていないことがわかっている
今表示されている情報に、丁度k本棒を付け足して作ることが出来る数字のうち、最大のものを答えよ
解法
最初文字列でDPしてたけどMLEとかTLEになるらしい（それはそう）
まず最初に、どの数字を作れるかをboolでDPをする
その時点で丁度k本使って作れないならば"-1"
それ以外は、各桁ごとに最大のものを選びながらDPを復元していけばいい
string num[10] = { "1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011" }; int needCount(string &s, string &t){ int cnt = 0; REP(l,7){ if(s[l] == '1' && t[l] == '0'){ cnt = -1; break; } if(s[l] == '0' && t[l] == '1') cnt++; } return cnt; } void solve(){ int n, k; cin >> n >> k; vector<string> s(n); REP(i,n) cin >> s[i]; vector<vector<bool>> dp(n+10, vector<bool>(k+10, false)); vector<vector<bool>> pre(n+10, vector<bool>(k+10, false)); dp[0][0] = true; REP(i,n){ REP(j,k+1){ if(!dp[i][j]) continue; REP(l,10){ int cnt = needCount(s[i], num[l]); if(cnt == -1) continue; if(j + cnt > k) continue; dp[i+1][j+cnt] = true; } } } if(!dp[n][k]){ cout << -1 << endl; return; } pre[n][k] = true; for(int i=n;i>0;i--){ REP(j,k+1){ if(!dp[i-1][j]) continue; REP(l,10){ int cnt = needCount(s[i-1], num[l]); if(cnt == -1) continue; if(j + cnt > k) continue; if(!pre[i][j+cnt]) continue; pre[i-1][j] = true; } } } string ans = ""; int cur = 0; REP(i,n){ int ma = -1; int next = -1; REP(j,10){ int cnt = needCount(s[i], num[j]); if(cnt == -1) continue; if(cur + cnt > k) continue; if(!pre[i+1][cur + cnt]) continue; if(chmax(ma, j)) next = cur + cnt; } ans += char(ma + '0'); cur = next; } cout << ans << endl; }
おわりに
読解が辛い回だった…
