結果
47:42(4) です。
E, F がかなり簡単なセットでしたから、これは痛いです。 F で軽々しくたくさん提出をしてしまったのが良くなかったでしょうか。
A - Lucky 7 (00:01:07)
string で受け取って、std::find などのシーケンシャルです。
std::string s;std::cin>>s; std::cout<<(std::find(ALL(s),'7')!=s.end()?"Yes":"No")<<'\n';
B - FizzBuzz Sum (00:02:17)
N までイテレートをして、足しましょう。N < 10 ^ 18 ですと、D 相当でしょうか。 2 分台は早いです。私も序盤が強くなってきました。
lint n;std::cin>>n; lint ans=0; for(lint i=1;i<=n;i++)ans+=i*(i%3&&i%5); std::cout<<ans<<'\n';
C - Sum of gcd of Tuples (Easy) (00:21:09)
3 乗ループで良いのですが、E を解いて貼ってしまいました。 誤って 10 億 7 で余りを取らないように、注意です。(これをしてしまったかたは、挙手です。)
D - RGB Triplets (00:09:30)
ABD で 9 分、ここまでは比較的順調でしょうか。
始め "RGB" の順番でないと行けないと誤読をしていましたから、"RGB" をソートして next_permutation で足し合わせてリカバリーです。(はい?) "RGB" でしたら、左から順に見て、"R" の個数、"RG" を作れる個数を管理です。 等間隔なものは後で引きましょう。これは間隔を全探索です。
lint n;std::cin>>n; std::string s;std::cin>>s; lint ans=0; std::string t="RGB"; std::sort(ALL(t)); do { for(lint i=0,a=0,ab=0;i<n;i++){ a+=s.at(i)==t.at(0); ab+=(s.at(i)==t.at(1))*a; ans+=(s.at(i)==t.at(2))*ab; } for(lint d=1;d<n;d++){ for(lint i=0;i+2*d<n;i++){ ans-=s.at(i)==t.at(0)&&s.at(i+d)==t.at(1)&&s.at(i+d+d)==t.at(2); } } } while(std::next_permutation(ALL(t))); std::cout<<ans<<'\n';
そして輝く next_permutation (はい?)
ミス
- 誤読
E - Sum of gcd of Tuples (Hard) (00:19:34)
約数累積和です。 各 x について、GCD が x であるような対 の個数を求めればよいです。 ここで、 と置きましょう。 これは、すべての成分が x で割り切れるものですから、掛け算です。 あとは、ここから累積和の逆をすると復元ができて、それを GCD と足し合わせましょう。
ミス
- GCD を掛け忘れました。
- 累積和の逆は上から見ないと行けないのですが、下から計算しました。
とくに 2 つ目は本質的にだめです。 ナップザックなどならば手が勝手に逆順ループを書くのですが、まだまだです。
F - Select Half (00:47:42(4))
4 ペナをするような問題でしょうか。 F にしては相当簡単な部類です。
カツカツな状態から 1 + n%2 個足りなければよいです。 左から順に見て、いくつ足りないときに最大いくつになるのかを DP です。
ただそのままやると
- 初期値は、a[0], a[1], a[2] を見なければなりません。
- n = 2 がコーナーケースになってしまいます。
- 答えも dp[n-3], dp[n-2], dp[n-1] を見なければなりません。
など、かなり厳しい状況になり、こうなると、大変なことが待っているかもしれません。 たとえば 4 ペナを食らうなどです。(はい?)
番兵を入れましょう。前と後ろに 2 つずつ 0 を入れておけば、最初と最後を必ず選ぶとして良いです。
ミス
- 番兵を入れるのを思いついたのが、バグってからでした。
- 番兵なしのときに、初期値と答えを 3 箇所ずつ見なければいけないことに気づいていませんでした。
- 番兵なしのときに、n = 2 がコーナーケースであることにも気づいていませんでした。
- 番兵を入れるとよいということには、1 WA 時点で気づいたのですが、面倒を厭い、ちょっと直して提出を繰り返してしまいました。
バグ全部盛りです……(泣) せっかくの勝てるはずの回を逃してしまって、とっても悲しい気持ちです。
lint inf=numr<lint>::max(); lint n;std::cin>>n; std::vector<lint>a(n+4); for(lint i=2;i<n+2;i++)std::cin>>a.at(i); n+=4; std::vector<std::array<lint,3>>dp(n,std::array<lint,3>{-inf,-inf,-inf}); dp.at(0).at(0)=0; for(lint i=0;i<n;i++){ for(lint j=0;j<3;j++){ if(dp.at(i).at(j)==-inf)continue; for(lint k=0;j+k<3&&i+2+k<n;k++){ cmx(dp.at(i+2+k).at(j+k),dp.at(i).at(j)+a.at(i+2+k)); } } } std::cout<<dp.at(n-1).at(1+n%2)<<'\n';