ABC179の感想

abc179の感想を書いていきます。

以前の問題の作成の際に、様々な方の記事を読んでるのでどのようなレイアウトで書こうか試行錯誤してます。

今回の結果はこちら

いい感じでCまできて、Dもコードを書き上げたのですがTLEで通りませんでした。やはりdに壁を感じます。

問題はこちらから
https://atcoder.jp/contests/abc179/tasks

A問題から行きます。

Aは言語を複数形にする問題。文字の末尾に注目して、場合分けをするだけです。stringやらcharやらの文字列操作ができればすぐに書けます。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
 
 string s;
 cin >> s;
 
 int l = s.length();
 if(s[l-1] != 's') s += "s";
 else s += "es";
 cout << s << endl;
 return 0;
}

B問題は、刑務所に行く問題です。これはモノポリーの問題でした。さいころを2個振って3連続でぞろ目が出たら刑務所に行きます。

入力の際に、一致してるかどうかの判定結果を作って、3回続いている箇所があれば、yesで終わりでした。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
 int n;
 cin >> n;
 
 vector<bool> eq;
 rep(i,n){
   int a, b;
   cin >> a >> b;
   if(a == b) eq.emplace_back(1);
   else eq.emplace_back(0);
 }
 
 int cnt = 0;
 rep(i,n){
   if(eq[i]) cnt++;
   else cnt = 0;
   
   if(cnt >=3){
     cout << "Yes" << endl;
     return 0;
   }
 }
 cout << "No" << endl; 
 return 0;
}

C問題は整数の問題でした。n = a * b + cを満たす正の整数組を求めます。

どうしようかなーと悩みました。n - c = a * bで素因数分解でもするんかなと思いましたが、cの最小値は1なので、n - 1 > a * bとなるa, b が何個あるかに置き換えられると気づきました。

それをfor文で回せばいいのですが、O(n^2)は通らないだろうなーと薄々感じ出ました。そのため、a <= bの要素だけ計算して（そのとき a = bの回数をカウントする）、それを2倍する。そのあと、a = bは重複してるから引いてあげる。

とすれば少し削減できました。しかし、これでもダメでした。

結局、n-1 を a で割った商 d を用いました。掛け算はつまるところ複数回の足し算なので、a は d 回足してもn-1より小さいです。つまり、a の相方となる b の取りうるパターン数は d となります。足りない部分はcで補います。

このdを足し合わせていけば答えとなります。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
 
 int n;
 cin >> n;
 int n1 = n-1;
 int ans = 0;
 
 for(int i = 1; i < n+1; i++){
   ans += n1 / i;    
 }
 
 cout << ans << endl;
 return 0;
}

この解放がぱっと浮かんだときは気持ちよかったです。

D問題はすごろくみたいな問題です。nマスのマス目があり、一回の移動で何歩進めるかが与えられます。nマス目までの行き方は何通りあるか求めます。

これは一次元のdpで簡単に解けるんじゃないか、dp[i]として、iマス目までの行き方をdpで更新していけば解けると思いました。それはその通りで、dpの実装は簡単にできました。

ただし、TLEとなり結果最後まで解けませんでした。悲しいです。

公式放送を見たら、まったく同じ境遇の人がいました。一緒に頑張りましょう。

移動方法は区間で与えられることを、上手く使わないといけないのかな、と考えましたが、頭が追いつきませんでした。

TLEするコードを残しておきます。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
const int mod = 998244353;
int dp[200010];
int main(){
 int n, k;
 cin >> n >> k;
 
 vector<int> act;
 rep(i,k){
   int l ,r;
   cin >> l >> r;
   for(int i = l; i<r+1; ++i){
     act.emplace_back(i);
   }
 }
 
 dp[0] = 1;
 rep(i,n){ 
   for(auto a : act){
     int nx = i + a;
     if(nx >= n) continue;
     dp[nx] = (dp[nx] + dp[i]) % mod;
   }
 } 
 int ans = dp[n-1];
 cout << ans << endl;
 
 return 0;
}

E問題にも手を出しました。似たような問題を解いたことがあるなーとうっすら思い出ました。abc175のDでした。
https://note.com/momomo0214/n/n8324236c348e#b4GM0

余りが循環することに気が付いたので、循環したら循環の総和を残りの循環回数分足して、循環の余りだけforを回す

というのを最後の10分で実装しましたが、計算が壊れて時間切れでした。

おそらくですが、今回は簡単だったのではないかと思います。そのなかでも、cまでサクッと解いて、d,eにも手が出せたので、少しずつですが進歩してるなと感じます。dが解ける日も近いですね。