参加〜
二完で22位だった。ICPC練習コンテスト系はこの順位安定する。
G
よく考えたらただの順列だった。
回文恐怖症克服したい
#include <cstdio> #include <iostream> #include <map> #include <algorithm> using namespace std; typedef long long ll; ll C(int c) { ll r=1; for (int i=2; i<=c; i++) r*=i; return r; } int main() { string s; cin>>s; map<char, int> cnt; for (int i=0; i<s.length(); i++) { if (cnt.find(s[i])!=cnt.end()) { cnt[s[i]]++; } else { cnt[s[i]]=1; } } int c=0, odd=0; for (map<char, int>::iterator it=cnt.begin(); it!=cnt.end(); it++) { if ((*it).second%2!=0) { odd++; } } if (odd>1) { puts("0"); } else { ll res=C(s.length()/2); for (map<char, int>::iterator it=cnt.begin(); it!=cnt.end(); it++) { res/=C((*it).second/2); } printf("%lld\n",res); } }
A
気づくのにおそろしく時間かかった。
よく考えてみるとただの全探索・・・って昨日のMedとおんなじや(T_T)
#include <cstdio> #include <iostream> #include <queue> #include <map> #include <algorithm> using namespace std; typedef pair<int, int> P; typedef pair<P, pair<int,string> > PP; string a, b, c; int k; int br[1000]; int main() { cin>>a>>b; scanf("%d",&k); c=""; int n=a.length(); for (int i=0; i<n; i++) c+='0'; while (b.length()<n) b="0"+b; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); queue<PP> que; que.push(make_pair(P(0,k),make_pair(0,""))); while (!que.empty()) { PP p=que.front(); que.pop(); int i=p.first.first; int x=p.first.second; int br=p.second.first; string s=p.second.second; if (s.length()==n) { if (c<s) c=s; continue; } if (a[i]-br>=b[i]) { string temp=""; temp+=a[i]-br-b[i]+'0'; que.push(make_pair(P(i+1,x),make_pair(0,(temp+s)))); } else { string temp=""; temp+=a[i]-br+10-b[i]+'0'; if (x>0) que.push(make_pair(P(i+1,x-1),make_pair(0,(temp+s)))); que.push(make_pair(P(i+1,x),make_pair(1,(temp+s)))); } } bool flag=false; for (int i=0; i<c.length(); i++) { if (c[i]!='0') { flag=true; putchar(c[i]); } else if (flag) { putchar(c[i]); } } puts(""); }
D
鬼畜問で通せてませんが僕の検討をちょこっと。
最初単純に書いてWAくらってもれてるのかなとおもいこんな感じに書いて見ました
#include <cstdio> typedef long long ll; ll gcd(ll a, ll b) { return b?gcd(b,a%b):a; } int main() { ll mx=0, bunbo=1; int n; scanf("%d",&n); for (int i=0; i<n; i++) { int o, y; scanf("%d%d",&o,&y); if (o==1) mx+=y*bunbo; if (o==2) mx-=y*bunbo; if (o==3) mx*=y; if (o==4) bunbo*=y; ll x=gcd(mx,bunbo); mx/=x; bunbo/=x; } printf("%lld\n",mx/bunbo); }
ただしこれでもWA。もれですかね?
BigIntegerとか非道を使ってみると・・・
import java.util.*; import java.math.*; public class Main { public static void main(String[] args) { Scanner stdIn=new Scanner(System.in); int n=stdIn.nextInt(); BigInteger x=BigInteger.valueOf(0); BigInteger bunbo=BigInteger.valueOf(1); for (int i=0; i<n; i++) { int o=stdIn.nextInt(), y=stdIn.nextInt(); BigInteger j=BigInteger.valueOf(y); if (o==1) x=x.add(j.multiply(bunbo)); if (o==2) x=x.subtract(j.multiply(bunbo)); if (o==3) x=x.multiply(j); if (o==4) bunbo=bunbo.multiply(j); } // System.out.println(x); // System.out.println(bunbo); System.out.println(x.divide(bunbo)); } };
TLEしました。
まぁなんでこんな無駄なことに紙面さいたかというと・・・・
解法教えてorz