Codeforces Round #176 div 2

久しぶりに(一年ぐらい)Codeforcesに出ました。
正解したのはA問題のみというひどい結果でした。
B問題はコーナーケースで落ち、C問題以降は
手も足も出ませんでした。
もう一度初心に帰って勉強する必要性を感じました。

A. IQ Test

  問題概要
    4x4の升目が与えられます。各升には"."または"#"が書かれています。
    16個の升のどれか一つを書き換えることによって同じ記号が書かれた
    2x2の正方形を得ることができるなら"YES"、できないなら"NO"と出力しなさい。
    ただし、何も書き換えない状態で条件を満たすなら"YES"と出力しなさい。
  解法
    16個の升のそれぞれについて書き換えて正方形が得られるかどうかを調べるだけです。
  ソースコード

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool check(vector<string> &vs){
     for(int i=0;i<3;i++)
	  for(int j=0;j<3;j++)
	       if(vs[i][j]==vs[i+1][j]&&vs[i][j]==vs[i][j+1]&&vs[i][j]==vs[i+1][j+1])
		    return true;
     return false;
}

char opposite(char c){
     if(c=='#')return '.';
     else return '#';
}

int main(){
     vector<string> vs;
     for(int i=0;i<4;i++){
	  string s;
	  cin>>s;
	  vs.push_back(s);
     }
     string ans="NO";
     if(check(vs))
	  ans="YES";
     for(int i=0;i<4;i++)
	  for(int j=0;j<4;j++){
	       vs[i][j]=opposite(vs[i][j]);
	       if(check(vs))
		    ans="YES";
	       vs[i][j]=opposite(vs[i][j]);
	  }
     cout<<ans<<endl;
     return 0;
}

B. Pipeline

  問題概要
    自然数nとkが与えられます。
    k以下の互いに異なる自然数l_1,l_2,l_3,...,l_mが
    l_1-1+l_2-1+l_3-1+...+l_m-1=n-1
    を満たすときmの最小値を求めなさい。
    ただし、n=1のときはm=0です。
    (これは問題から主要な部分を抽出したものであり
     実際の問題文の日本語訳とはかなり異なります。)
  解法
    l_1-1+l_2-1+l_3-1+...+l_m-1>=n-1
    となるmを見つければ良いので(勘)
    l_1=k,l_2=k-1,l-3=k-2,...,l-m=k-m+1とします。
    このとき
    l_1-1+l_2-1+l_3-1+...+l_m-1=(k+k-m+1)*(k-k+m-1+1)/2-m であるので
    mの値を二分探索すれば良いです。
  ソースコード

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;

int main(){
     LL n,k;
     cin>>n>>k;
     if(n==1){
	  cout<<0<<endl;
	  return 0;
     }
     if(n<=k){
	  cout<<1<<endl;
	  return 0;
     }
     LL u=k-1,d=0;
     for(int i=0;i<100;i++){
	  LL m=(u+d)/2;
	  LL a=(k-m)*(k+m-1)/2;
	  if(n-1<=a)
	       d=m;
	  else
	       u=m;
     }
     // cout<<"u="<<u<<" d="<<d<<endl;
     if(n-1<=(k-u)*(k+u-1)/2)
	  cout<<k-u<<endl;
     else if(n-1<=(k-d)*(k+d-1)/2)
	  cout<<k-d<<endl;
     else
	  cout<<-1<<endl;
     return 0;
}