SRM 616

腹が立つ。

Easy

やるだけ。

class WakingUpEasy
{
	public:
	int countAlarms(vector <int> volume, int S)
	{
		int sz=volume.size();
		int sum=0;
		for(int i=0;i<volume.size();i++)sum+=volume[i];
		int ans=0;
		ans+=(S/sum)*sz;
		S-=sum*(S/sum);
		for(int i=0;i<volume.size();i++)
		{
			if(S<=0)break;
			S-=volume[i];
			ans++;
		}
		return ans;
	}
};

Medium

最適な支払い方で各硬貨がすべて違う枚数であるようにできればいい。value[i]の硬貨をvalue[i+1]/value[i]枚以上支払う時は最適ではないので、各硬貨の枚数がすべて違うかつ、すべての硬貨を使う枚数がvalue[i+1]/value[i]未満であるようにできるか判定。

class ColorfulCoinsEasy
{
	public:
	string isPossible(vector <int> values)
	{
		string po="Possible";
		string ip="Impossible";
		vector<int> v;
		for(int i=1;i<values.size();i++)v.pb((values[i]/values[i-1])-1);
		sort(v.begin(),v.end());
		for(int i=0;i<v.size();i++)if(v[i]<i+1)return ip;
		return po;
	}
};

Hard

各gridで上と右に白い点が何個連続しているかを前計算して、L字の左下の交点をすべて試すだけ。
Hardにしてはかなり簡単だと思う。
解法すぐにわかったし40分くらいあまってたのでコレは勝ったと思ってたらなぜがgridが正方形だという勘違いをして時間を25分浪費した挙句気づいたのが終了30秒前くらいで間に合わず。
クソ。

ll t[35][35],y[35][35];
class TwoLLogo
{
	public:
	long long countWays(vector <string> grid)
	{
		int s1=grid.size();
		int s2=grid[0].size();
		ll ans=0ll;
		for(int i=0;i<s1;i++)
		{
			for(int j=s2-1;j>=0;j--)
			{
				if(grid[i][j]=='#')
				{
					t[i][j]=0;
					y[i][j]=0;
				}
				else
				{
					if(i==0)t[i][j]=1;
					else t[i][j]=t[i-1][j]+1;
					y[i][j]=y[i][j+1]+1;
				}
			}
		}
		for(int i=0;i<s1*s2;i++)
		{
			for(int j=i+1;j<s1*s2;j++)
			{
				ll a,b,c,d;
				a=i/s2;
				b=i%s2;
				c=j/s2;
				d=j%s2;
				if(t[a][b]<2||y[a][b]<2||t[c][d]<2||y[c][d]<2)continue;
				if(b>d)
				{
					ans+=(t[a][b]-1)*(y[a][b]-1)*(t[c][d]-1)*(y[c][d]-1);
				}
				else
				{
					ans+=(t[a][b]-1)*(max(min(y[a][b]-1,d-b-1),0ll))*(t[c][d]-1)*(y[c][d]-1);
					ans+=(t[a][b]-1)*(y[a][b]-1)*(max(min(t[c][d]-1,c-a-1),0ll))*(y[c][d]-1);
					ans-=(t[a][b]-1)*(max(min(y[a][b]-1,d-b-1),0ll))*(max(min(t[c][d]-1,c-a-1),0ll))*(y[c][d]-1);
				}
			}
		}
		return ans;
	}
};

oo- 691.85pts 67th
1115 -> 1197
あのさぁ…