2014-02-15

■ SRM 609 04:02

ひたすらこわい＞＜回でした。

Easy:

JOIOIの塔やるだけじゃん... と思ったらsample3でおちた。

よくよく見ると、"""">がk個あった後に""""<がk個であると分かる。

というわけで、kを決めうちした。両端から取る解法とか難しくて思いつかない...

#line 2 "MagicalStringDiv1.cpp"
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
//これは、頭が悪く競プロが世界で一番できないHIR180が
//IOI2014日本代表になるまでのN日間の記録である。
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
//#define s second
#define rep(i,x) for(int i=0;i
class MagicalStringDiv1
{
	public:
	int getLongest(string S) 
	{
		//int tot=0,tot2=0;
		int ret=0;
		for(int i=1;i<=50;i++)
		{
			int tot=0; int tot2=0;
			bool ok=false;
			for(int j=0;jif(S[j]=='>' && totif(tot==i) ok=true;
				}
				else if(S[j]=='<' && ok)
				{
					tot2++;
				}
			}
			if(tot2>=i) ret=i*2;
		}
		return ret;
	}
};

Med:

まずvariety setがk-1個以下であることは分かるので、

variety setがi個ある時はどうなるのかな...と考えたら、

kで割った余りが1~iの物に対し-1されるということなので、

配列に持っといて順に足していけばよいと分かった。

#line 2 "PackingBallsDiv1.cpp"
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
//これは、頭が悪く競プロが世界で一番できないHIR180が
//IOI2014日本代表になるまでのN日間の記録である。
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i
ll v[100005];
int am[100005];
class PackingBallsDiv1
{
	public:
	int minPacks(int K, int A, int B, int C, int D) 
	{
		v[0]=1LL*A;
		for(int i=1;i1]*B+1LL*C)%D+1LL;
		}
		int ret=0;
		for(int i=0;iint)v[i]%K]++;
			ret+=(v[i]+K-1LL)/K;
		}
		int cur=ret;
		for(int i=1;ireturn ret;
	}
};

hard:

知らない。こわい。

このあとはEasy Medのチャレンジ対策をした。(結局+0/-0だったが。)

challenge 絶望

systest 通った。

28位　Rating 1998->2118(+120)

とうとうRedCoderまであと100を切りました。

ツイートする

■ 階乗の逆元をO(N+log N)で求める 06:29

inv[i]=i! mod Nの逆元とすると

(i+1)!*inv[i+1] mod N=i!*inv[i] mod N

<=>

i!*(inv[i+1]*(i+1)) mod N=i!*inv[i] mod N

よってinv[i]=(inv[i+1]*(i+1)) mod Nであるので

inv[N-1]だけO(log N)で計算しとくとあとはO(1)でできます。

...普通にO(N)のやり方のほうが優秀ですね...(絶望)

ツイートする