AGC039-A 死亡

死にました

死亡の図

任意の同レベルerが次々入水をキメてる中で相当堪えてます...

解法を記録して戒めようと思った(忘れたまま別の問題で応用できない方がもっとダメ)のでちゃんとブログに残します。

A - Connection and Disconnection(300)

問題文
文字列SをK回繰り返して連続して同じ文字が出ないようにするには最小で何回操作するかの問題。

色んなケースを含むaaabbaの文字列について考えると、
K=iのとき、 aaabba aaabba aaabba aaabba aaabba ...となる。

これを、連続する文字を被らないように#に置き換えると、
a#ab#a #a#b#a #a#b#a #a#b#a #a#b#a ...に変わる。

この#の数がK=iの時の操作回数になる。

で、どうするか。

よく見ると、文字列Sの変化は1回目と他の回数とで違いが発生していることが分かる(逆に2~n回は全部同じ変わり方)。

具体的には、a#ab#a(1回目)　と　#a#b#a(2回目)になっている。

よって、答えは、(1回目の#の数) + (2回目の#の数) * (k-1)となる。

で、提出をするとこうなる。

うく

で、少し考えると、aaaaaのとき、
a#a#a #a#a# a#a#a #a#a# a#a#a #a#a# ....と前までの例に引っ掛からなくなる。
このケースの解は(Sの長さ)*K/2で求まる。

これでようやくAC。

ソースコード

提出コード(提出 #7877772)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
  string s;
  int k;
  ll cnt1=0,cnt2=0;
  cin >> s >> k;
  if(s == string(s.size(),s[0])) {
    cout << s.size() * k / 2 << endl;
    return 0;
  }
  string t = s+s;
  rep(i,s.size()-1) if(s[i] == s[i+1]) s[i+1] = '#',cnt1++;
  rep(i,t.size()-1) if(t[i] == t[i+1]) t[i+1] = '#',cnt2++;
  cout << cnt1 + (cnt2-cnt1)*(k-1) << endl;
  return 0;
}

感想

高専プロコン、オープンキャンバス展示用作品に時間を取られすぎて全く精進をしなかった。
そりゃ競プロ力が伸びるわけなく無事死亡。
来週の高専プロコンまでデスマーチして終わり次第限界精進したいと思います(卒業研究はしらん)