ABC175の解答

ABC175の自分なりの解答を書きます。
競技プログラミング初心者の私でも理解できるように、可能な限り、冗長に書いていくので、のんびりとお付き合いいただけると幸いです。

問題は以下リンクからお願いします。
https://atcoder.jp/contests/abc175/tasks

A Rainy Season

A問題は3日間の天気が与えられて、何日間連続で雨が降ったか。という問題。様々な手法で解けるとは思いますが、abcのA問題の特徴として「for文を用いなくとも解ける」というものがあるらしく、今回はそれに則って解いていきます。

と言ってもif文で分岐させるだけです。

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
int main()
{
  string s;
  cin >> s;
int ans = 0;
if(s == "RRR") ans =3;
  if(s == "RRS") ans =2;
  if(s == "RSR") ans =1;
  if(s == "SRR") ans =2;
  if(s == "RSS") ans =1;
  if(s == "SRS") ans =1;
  if(s == "SSR") ans =1;
  if(s == "SSS") ans =0;
cout << ans << endl;
  return 0;
}

状態が2^3=8通りしかないからこんな感じでいけますね。これが増えたときは腕の見せ所となりそうですね。次。

B Making Triangle

三角形を作る問題です。前回は距離を求めるだけでしたが、それと比較をすると少し難しく戸惑いました。

まず、どのような3辺を選択したら三角形ができるのか、と言いますか、どのようなとき三角形ができないかを考えます。

条件としては1番長い辺より他の2辺の和が長ければ良いです。直感ですと、この条件を満たさないと2辺が届かないという感じになります。

この条件は色々と表現の仕方があります。

長さl,m,nが与えらえたとき

max({l,m,n}) < maxとなる辺を除く2辺の和
↓
l + m + n - 2*max({l,m,n}) > 0

と直感的な条件式でもいいですし、

l + m > n
m + n > l
n + l > m

の積集合(全部“かつ”の条件)でもいいと思います。

あとは問題文の条件にある、l≠m≠nに注意をして、要素を満たすものだけ数え上げます。

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
int main()
{
  int n;
  cin >> n;
  vector<ll> l(n);
  rep(i,n) cin >> l[i];
int ans = 0;
  rep(i,n)rep(j,n)rep(k,n)
  {
    if(i<j && j<k)
    {
      if(l[i] == l[j]) continue;
      if(l[j] == l[k]) continue;
      if(l[k] == l[i]) continue;
if(l[i]+l[j]+l[k] > max({l[i],l[j],l[k]})*2)  ++ans;
}
}
  cout << ans << endl;
return 0;
}

重複を許さないfor文をif文にて制御するのはスマートでいいなあと思いました。次。

C Walking Takahashi

解説を見て最も感心した問題です。試験中は難しいことを考えていましたが、とても簡潔に答えが求められました。

原点からxだけ離れた点からスタートして、dだけ移動するのをk回行ったとき、座標の絶対値(距離)の最小値を求める問題。

まず、答えは絶対値を求めればいいので、入力値を全部正で考えます。こっちの方が簡単です。

試験中は色々考えましたが、答えの候補は以下の3つに分類されます。

1、移動をしたけど原点に届かない場合。
x - d * k

もし原点に到達到達できたなら、その後は原点を挟んだ2点で反復横跳びします。ということで、

2、原点の一歩手前側
x % d

3、原点の一歩奥側
(x % d - d) の絶対値

が候補となります。

これをプログラムに起こします。まず、届くかどうかの判定をします。届かなければそれが答えです。

次に届いた場合を考えます。到達時(原点の一歩手前)に移動を何回消費したかを数え、残りの移動回数を求めてあげます(x/dをkから引きます)。

あとは残りの移動回数が偶数ならその場所、奇数ならもう一歩移動した場所(奥側)という感じです。

実装です。

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
int main()
{
  ll x, k, d;
  cin >> x >> k >> d;  
  x = abs(x);
  ll ans = 0;
//0に到達しない場合
  if(x / d > k) ans =  x - d*k;
  else
  {
    ll ans_r = x % d;
    ll ans_l = abs(ans_r - d);
if((k-x/d) % 2 == 0) ans = ans_r;
else ans = ans_l;

}
  cout << ans << endl;
  return 0;
}

届くかの判定のとき、xとk*dを比較するとオーバーフローするので気を付けましょう。次。

D Moving Piece

ワープする双六で最高点を取りましょう、みたいな問題。あるマスには得点ci（負の得点もあり）と移動先のマスpiが与えられています。任意のマスからスタートし、k回以内の移動で獲得できる最高点を求めます。どこからスタートしてどこで終わりますか、が重要となります。

答えを求めるだけなら、愚直にやればできます。

sum += c[p[i]];

こんな感じで、、、ただし当然TLEです。

ここで、問題の条件に注目します。

pi ≠ i
p1, p2, ..., pnは全て異なる。

この条件より全てのマスは、自分以外のマスへの移動先と、自分マスへ移動してくるマスを一つずつ持つことがわかります。別の言葉にするのなら、マスの関係は複数のリングのようになっていて、行き止まりや分岐は起こり得ないということです。

そのため、あるリングを一周回った際の総コストが重要となります。これが正であれば可能な限り回りたいですし、負であれば早く切り上げたほうがお得です。

リングの総コストが求まったのなら、後はリングを周回して余った移動回数について考えます。最終的なスコアは

sum = 1週の得点 * 周回数 + 余った移動回数で獲得した得点

で表されるので、あとは余った移動回数を考えます。ここにきて、初めてfor文の出番です。始点と終点に関してfor文を2つ回してあげることにより、計算量を削減できます。

あとは一回も移動しないことは禁じられていることに注意をして実装します。

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
int main(){
 int n, k;
 cin >> n >> k;
 vector<int> p(n), c(n);
 rep(i,n) cin >> p[i];
 rep(i,n) cin >> c[i];
 rep(i,n) --p[i];
   
 ll ans = INT_MIN;
 
 rep(i,n){   
   vector<int> loop; //loopする順列
   int x = i; 
   ll loop_sum = 0;
   
   while(1){
     loop.emplace_back(c[x]);
     loop_sum += c[x];
     x = p[x];
     if(x == i) break;  
   }
   
   int l = loop.size();
   ll rem_sum = 0;
   ll ans_sum = 0;
   rep(st,l){
     rem_sum += loop[st];
     if(st+1 > k) break;
     ll e = (k-(st+1)) / l;
     ans_sum = rem_sum + max((ll)0, loop_sum) * e;
     ans = max(ans,ans_sum);   
   }
   
 }
 cout << ans << endl;
 return 0;
}

rep(i,n)で始点の変更、その後、周回する配列を生成した後、rep(st,l)で終点の変更をして、ansが高くなるように更新をしていきます。このときに周回するかどうかはmax(0,loop_sum)で決定しています。

E Picking Goods

碁盤目の上に無作為にアイテムが置かれていて、→と↓移動のみで、左上から右下まで移動する際に、獲得スコアを最大化する問題。また、このときに「同じ行ではアイテムは3つしか取得できない」という制約がある。

碁盤の目であるため座標はxyの2軸、かつアイテムの取得状況を考慮するため、3要素における動的計画法を用いて解きます。動的計画法に関しては、以下のページにまとめたのでもしよろしければ見てください。というページを後日作りたいと思います。

動的計画法では各状態に対して取り得る行動を一回しか行わない（重複を許さない）ので計算量を削減できます。

実際、今回の例ではR*C*4*2回の演算となります。愚直に計算をすると、(R+C)!/(R!*C!)にアイテムを取得する、しないを掛けた数になります。階乗の計算は大変なことになるので避けましょう。

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
 
int v[3000][3000];
ll dp[3000][3000][4];
int main(){
 
 int R, C, K;
 cin >> R >> C >> K;
 
 rep(i,K){
   int r, c, a;
   cin >> r >> c >> a;
   v[r-1][c-1] = a;
 }
 
 dp[0][0][1] = v[0][0];
 rep(r,R)rep(c,C)rep(k,4){
   if(r+1 < R){//縦に動く
     //拾わない
     dp[r+1][c][0] = max(dp[r+1][c][0], dp[r][c][k]);
     //拾う
     dp[r+1][c][1] 
       = max(dp[r+1][c][1], dp[r][c][k] + v[r+1][c]);
   }
   if(c+1 < C){ //横に動く
     //拾わない
     dp[r][c+1][k] = max(dp[r][c+1][k], dp[r][c][k]);
     //拾う
     if(k + 1 <= 3){
       dp[r][c+1][k+1] 
         = max(dp[r][c+1][k+1],dp[r][c][k]+v[r][c+1]);
     }
   }
 }
 
 ll ans = 0;
 rep(i,4) ans = max(ans, dp[R-1][C-1][i]);
 cout << ans << endl;
 return 0;
}

動的計画法を理解できていれば実装はそこまで重くないと思います。

F Making Palindrome

まだ、ACになっていないですが、余りにも時間がかかっているため、理解できている点を暫定的に書いていきます。

単語が複数個与えられて、それぞれにコストが設定されている。最も少ないコストで回文を作るという問題。

まず、どのように問題にとっかかるかについてです。

単語をひたすらにつなげていき、いつか回文ができると考えます。この場合、次につなげられる文字に制限がないため、無限通りの文字列を考慮する必要があります。

そのため、文字列の頭とお尻に付け加えています。適当な例を出します。
まず、「abc」という文字を頭につけます。

abc

次にお尻を考えます。お尻として来れるのは「...cba」という構造を持つ必要があります。そのため「decba」をつけてみます。

abc   de  cba

次にお尻部分の「de」が余ったので、頭に「ed」から始まる「edfg」をつけます（連続で頭、お尻が余ることもある）。

abced  fg  decba

こんな感じでやっていき

余りが出なくなる or 余りも回文

となれば終了です。

この手法の何が良いかというと、文字列のあまりに注目をするため、文字列が長くならない、また、余りは必ず、入力文字列またはその反転文字列の一部分となるため、有限個の状態で表せることです（1<=N<=50、1<=|Si|<=20）。

回文を作れるようになったので、次はどのように最小コストを求めるかです。

余りとなりうる状態を考えます。文字数がN個あり、その文字長が|Si|なのでN*|Si|。それに反転分の*2を考えるため、数値にして2000程しかありません。そのため、2000個の頂点を持つグラフをつくって、文字列を付け加える操作はコストciのノードを通り別の頂点に遷移する処理とみなすことができます。

そのように考えれば、最短経路問題のためのアルゴリズムにより解を求めることができます。

以上により以下のフローにより解いていきます。

１、グラフを作成
　・現在の状態から遷移可能な状態とそれにかかるコストの取得

２、最短経路問題のアルゴリズムを適用
　・ダイクストラ法を適用（多始点、終了条件による終点）

こんな感じです。実装でき次第、コードを加筆したいと思います。