柳に燕

2019-01-04 あけましておめでとうございます。 このエントリーを含むブックマーク

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dfs(string s, ll ans){  
  ll q = ans;
  if(s.size() == 1)
    return ans + stoll(s);
  
  for(int i=1; i<s.size(); i++)
    q += dfs(s.substr(i), ans + stoll(s.substr(0,i)));
  
  q += stoll(s);  
  return q;
}

int main(){
  string s;
  cin >> s;
  
  ll ans = 0;
  
  cout << dfs(s, ans) << endl;
}

C - たくさんの数式 / Many Formulas
dfsで全探索。はじめqの更新のところq += dfs(s.substr(i), ans + stoll(s.substr(0,i)))をq += stoll(s.substr(0,i)) + dfs(s.substr(i), ans)としたせいでテストが通らずハマり。各ブランチで上の階層の値をちゃんと考慮しないといけない。

トラックバック - http://d.hatena.ne.jp/ttrr/20190104

2018-12-18

00:56 | ■を含むブックマーク

常識かのように出てくるので、手持ちの手法に追加。覚えとこ。
https://ja.wikipedia.org/wiki/ワーシャル–フロイド法:title]

トラックバック - http://d.hatena.ne.jp/ttrr/20181218

2018-12-14 このエントリーを含むブックマーク

トラックバック - http://d.hatena.ne.jp/ttrr/20181214

2018-12-13 このエントリーを含むブックマーク

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int check(ll p){
  int flag3 = 0, flag5 = 0, flag7 = 0;
  while(p > 0){
    if(p%10 == 3) flag3 = 1;
    else if(p%10 == 5) flag5 = 1;
    else if(p%10 == 7) flag7 = 1;
    p /= 10;
  }
  return flag3 * flag5 * flag7;
}

int main(){
  int x;
  cin >> x;
  
  vector<ll> ans;
  ans.push_back(3);
  ans.push_back(5);
  ans.push_back(7);
  
  int l=0;
  int r=3;
  
  for(int i=0; i<9; i++){
    for(int j=l; j<r; j++){
      ans.push_back(ans[j] * 10 + 3);
      ans.push_back(ans[j] * 10 + 5);
      ans.push_back(ans[j] * 10 + 7);
    }
    l=r;
    r = ans.size();
  }
  
  int cnt = 0;
  for(int i:ans){
    if(check(i) && i <= x){
      cnt++;
    }
  }
  cout << cnt << endl;
}

コーナーケースでつまらぬミス(等号つき不等号をただの不等号にしていた)があり、WAを重ねてしまった。
それにしても融通のきかないコードだな。

https://beta.atcoder.jp/contests/abc114/tasks/abc114_c

トラックバック - http://d.hatena.ne.jp/ttrr/20181213

2018-12-10 このエントリーを含むブックマーク

今日のプログラミング練習

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
  int n;
  cin >> n;
  
  map<int, int> mp;
  
  //n!の約数をmp[約数][個数]に記憶。
  for(int i=1; i<=n; i++){
    int k = i;
    for(int j=2; j<=i; j++){
      while((k % j == 0) && k >= j){
        mp[j]++;
        k /= j;
      }
      if(k == 1) break;
    }
  }
    
  int mt74 = 0;
  int mt24 = 0;
  int mt14 = 0;
  int mt4 = 0;
  int mt2 = 0;

  for(int i=1; i<=n; i++){
    if(mp[i] >= 74) mt74++;
    else if(mp[i] >= 24) mt24++;
    else if(mp[i] >= 14) mt14++;
    else if(mp[i] >= 4)  mt4++;
    else if(mp[i] >= 2) mt2++;
  }
  
  int ans = mt74 + (mt74 + mt24) * (max(mt74+mt24-1, 0) + mt14 + mt4 + mt2) + (mt74+mt24+mt14) * (max(mt74+mt24+mt14-1,0) + mt4) + (mt74 + mt24 + mt14 + mt4) * max(mt74 + mt24 + mt14 + mt4 - 1, 0) / 2 * (max(mt74 + mt24 + mt14 + mt4 - 2, 0) + mt2);
  cout << ans << endl;
}

https://beta.atcoder.jp/contests/abc114/tasks/abc114_d
美意識のかけらもなし。各約数に対して登場回数を求めるところまではすんなりできたが、最後の数え上げで混乱。最後は気合い。

トラックバック - http://d.hatena.ne.jp/ttrr/20181210