AGC019

AtCoder Grand Contest 019 - AtCoder Grand Contest 019 | AtCoder

AGCはレート爆上げの機会になりやすくて嬉しいとか

結果：A,B2完

感想：Bの実装量をとても少なくできたので個人的には満足

A:

DPっぽく見えたけどそんなことはない

大容量ほど容量単価が安くないとそれを選択する意味がないので、それに当てはまらないサイズはカットして、上から順にとっていけばよし

0.25とか考えたくなかったので全部4倍して整数で解決（intOFに気づかず1WA）

B:

直感が輝き8分で終了

左からk文字に対しての並び替えを考えると左からk-1文字の並べ替え＋αとなることが分かる

さらにαは左からk-1文字のうち左からk文字目と異なる文字の数と分かる（この辺は入力例１から試してみた）

上から1文字ずつバケットに読み込みながら異なる文字の数だけ足していけば解決

#include <bits/stdc++.h>
 
#define i64 long long
#define ui64 unsigned long long
#define ATCODER 1000000007
using namespace std;
 
////////////////////////

/* a */ 
int main(){
  #define INF -1
  i64 q,h,s,d,n;
  cin >> q >> h >> s >> d;
  if(q*2<h) {
    h=INF;
    // cout << 1 << endl;
  }
  if(q*4<s){ s=INF;}
  if(q*8<d){ d=INF;}
  if(h!=INF&&h*2<s){ s=INF;}
  if(h!=INF&&h*4<d){ d=INF;}
  if(s!=INF&&s*2<d){ d=INF;}
  cin >> n;
  n*=4;
  i64 res=0;
  if(d!=INF){
    res+=(i64)n/8*d;
    n%=8;
  }
  if(s!=INF){
    res+=(i64)n/4*s;
    n%=4;
  }
  if(h!=INF){
    res+=(i64)n/2*h;
    n%=2;
  }
  res+=(i64)n*q;
  // cout << q << " " << h << " " << s << " " << d << endl;
  cout << res << endl;
}

/* b */

char s[200005];
 
int main(){
  cin >> s;
  int alpha[26] = {0,};
  int t;
  i64 res = 1;
  for(int i=0;s[i]!='\0';i++){
    t = (int)s[i]-'a';
    alpha[t]+=1;
    res+=i-alpha[t]+1;
  }
  cout << res << endl;
}