練習ログ (001)
練習で解いた問題を気が向いたらメモしてみることにした。
AOJ2155: Infected Computer
Source
- JAG Summer Camp Day 2, 2009 [problem]
Description
- n台のコンピュータが互いにパケットを送る。ウィルスに感染しているコンピュータからパケットを受け取ったコンピュータはウィルスに感染する。パケットの送信ログが与えられるので、感染しているコンピュータの数を答えよ。
Solution
- やるだけ。ソートと単純なシミュレーション。
Code
// テンプレートは省略 struct data{ int src,dst,time; }; bool cmp(const data& a, const data& b){ return a.time < b.time; } int main(){ int n,m; while(cin >> n >> m && n|m){ vint v(n,0); v[0]=1; vector<data> u(m); REP(i,m) cin >> u[i].time >> u[i].src >> u[i].dst; sort(ALL(u),cmp); REP(i,m) v[u[i].dst-1]=v[u[i].dst-1]||v[u[i].src-1]; cout << count(ALL(v),1) << endl;; } }
AOJ2156: Magic Slayer
Source
- JAG Summer Camp Day 2, 2009 [problem]
Description
- n体のモンスターのHPと、m種類の魔法が与えられる。それぞれの魔法はモンスター1体または全体に指定されたダメージを与え、指定された量のMPを消費する。敵を全滅させるための最小のMPはいくらか。
Solution
- DP + simple search.
- 単体魔法だけを使って全ての敵のHPを p 以下に減らし、全体魔法だけを使って p ダメージを与えればよい。
- どの魔法をどれだけ使うかは、硬貨両替問題のようなDPで計算できる。
- p は分からないので全探索する。
- HPの上限 100,000 に比べて魔法の威力の上限 999,999 がずっと大きいのが引っ掛けポイント。
- 100,000 ぐらいの配列を取ってDPすると、そのような魔法が配列の範囲チェックに弾かれて使われないということが起きたりするかも。
Code
// テンプレートは(ry struct magic{ int m,d; }; typedef vector<magic> vmagic; const int L=200000, inf=1<<20; vint DP(vmagic &v){ REP(i,v.size()) ls(v[i].d,100000); vint ans(L,inf); ans[0]=0; REP(i,v.size()) REP(j,L-v[i].d) ls(ans[j+v[i].d],ans[j]+v[i].m); for(int i=L-2;i--;) ls(ans[i],ans[i+1]); return ans; } int main(){ int n,m; while(cin >> n && n){ vint hp(n); REP(i,n) cin >> hp[i]; vmagic single,all; cin >> m; REP(i,m){ string t; int m,d; cin >> t >> m >> t >> d; if(t=="Single") single.push_back((magic){m,d}); else all. push_back((magic){m,d}); } vint ms=DP(single), ma=DP(all); int ans=inf; REP(i,L){ int res=0; REP(j,n) res+=ms[max(0,hp[j]-i)]; ls(ans,res+ma[i]); } cout << ans << endl; } }
AOJ2157: Dial Lock
Source
- JAG Summer Camp Day 2, 2009 [problem]
Description
- 10桁以下で同じ桁数の2つの数 A, B が与えられる。最小回数の操作でAをBにせよ。
- 1回の操作で、連続する任意長の桁を +n (ただし、9の次は0) することができる。
Solution
- まず、適切に数字を読みかえれば、Aは全ての桁が 0 とすることができる。
- 1回の操作で少なくとも1つの数字を合わせることにしても問題ない。
- 一番左の桁から1桁ずつ合わせていくことにして、同時に右何桁を一緒に回すかを全探索。O(n! * n).
- 他の人に比べて遅いのは、枝狩りを全くしていないせいだろうか。
Code
// テンｐ(ry const int L=10; int rec(int v[],int n,int l){ if(n==l) return 0; int d=v[l]; int res=1<<20; FOR(i,l,n){ v[i]=(v[i]-d+10)%10; ls(res,rec(v,n,l+1)+(d?1:0)); } FOR(i,l,n) v[i]+=d, v[i]%=10; return res; } int main(){ int n; while(cin >> n && n){ string src,dst; cin >> src >> dst; int v[L]; REP(i,n) v[i]=(src[i]-dst[i]+20)%10; cout << rec(v,n,0) << endl; } }
テンプレート
- ついでにテンプレートそのものも晒し上げ。
#include <iostream> #include <sstream> #include <queue> #include <map> #include <set> #include <vector> #include <numeric> #include <algorithm> #include <string> #include <cassert> #include <cstdlib> #include <cmath> #include <cstdio> #include <cstring> #define REP(i,e) for(int i=0;i<(int)(e);i++) #define FOR(i,b,e) for(int i=(int)(b);i<(int)(e);i++) #define FORC(i,b,e,c) for(int i=(int)(b);i<(int)(e)&&(c);i++) #define ALL(c) (c).begin(), (c).end() #define EACH(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it) using namespace std; typedef long long ll; typedef vector<int> vint; typedef vector<long long> vll; typedef vector<string> vstring; typedef vector<double> vdouble; template<class T>void pp(T v,int n){ REP(i,n)cout<<v[i]<< ' ' ; cout << endl;} template<class T>void pp(T v){ EACH(it,v) cout << *it << ' ' ; cout << endl; } template<class T>T& ls(T& a,T b){ if(b<a) a=b; return a;} template<class T>T& gs(T& a,T b){ if(b>a) a=b; return a;}
- 簡単に説明してみる。
#include
- ただのインクルード。
#define
typedef
- ll と vint は無いと結構面倒。
- それ以外はあれば便利だけど、持ち込み禁止のコンテストでは特に書かない。
