cafelier@SRM

KUPC11

22:50 |

おもしろかった。提出したコード無編集貼り付け。問題文はこちら。

A

数える。

int main()
{
   string s;
   getline(cin, s);
   int K = count(s.begin(), s.end(), 'K');
   int U = count(s.begin(), s.end(), 'U');
   int P = count(s.begin(), s.end(), 'P');
   int C = count(s.begin(), s.end(), 'C');
   cout << min(min(K,U),min(P,C)) << endl;
}

B

ザ・DP。

int main()
{
   int H, W;
   cin >> H >> W;
   vector<string> M(H);
   for(int y=0; y<H; ++y)
      cin >> M[y];

   vector< vector<int> > dp(H, vector<int>(W));
   for(int y=0; y<H; ++y)
      for(int x=0; x<W; ++x)
         if(y||x)
            dp[y][x] = min(y?dp[y-1][x]:99999999, x?dp[y][x-1]:99999999) + M[y][x]-'0';
   cout << dp[H-1][W-1] << endl;
}

C

「あ」攻め。

int main()
{
   char ch = 'a';
   set<string> used;
   for(int i=0 ;; ++i)
   {
      string me = string(1,ch) + char(i/26+'a') + char(i%26+'a') + 'a';
      cout << "?" << me << endl;
      used.insert(me);
      string you;
      cin >> you;
      if( used.count(you) || me[me.size()-1]!=you[0] ) {
         cout << "!OUT" << endl;
         return 0;
      }
      used.insert(you);
      ch = you[you.size()-1];
   }
}

D

すべて50%50%でランダムに0/1を決めれば、どのカードの和も期待値N/4になる。Nが大きければ[N/8, 3N/8]から逸れる確率は限りなくゼロに近い。N小さくても高い確率でこのゾーンに入るので、繰り返せば限りなく１に近い確率で入る。

bool check(const vector<int>& s, const vector< vector<int> >& card)
{
   for(int k=0; k<card.size(); ++k) {
      int sum = 0;
      for(int i=0; i<card[k].size(); ++i)
         sum += s[card[k][i]-1];
      if( sum < s.size()/8 || s.size()/8*3 < sum )
         return false;
   }
   return true;
}

int main()
{
   srand(time(0));

   int N, K;
   cin >> N >> K;
   vector< vector<int> > card(K, vector<int>(N/2));
   for(int k=0; k<K; ++k) {
      for(int i=0; i<N/2; ++i)
         cin >> card[k][i];
   }
   vector<int> s(N);
   for(;;) {
      for(int i=0; i<N; ++i)
         s[i] = rand()%2;
      if( check(s, card) ) {
         for(int i=0; i<N; ++i)
            cout << s[i];
         cout << endl;
         return 0;
      }
   }
}

I

列の交換は行の山nessに影響しないし、逆もそうなので、まず列を並べ替えて、次に行を、と別々に。O(N^3)に見えますがメモ化再帰の部分そこまで探索空間全部見尽くす入力ないような気がする。

vector<int> memo;
bool rec(const vector< vector<int> >& r, int H, int W, int L, int R)
{
   int N = max(L,R)+1;
   if( N >= W )
      return true;

   if(L>R)swap(L,R);
   int key = L*W+R;
   if(memo[key])
      return memo[key]==1;

   bool left = true;
   for(int y=0; y<H; ++y)
      if( r[L][y] >= r[N][y] )
         left = false;

   bool right = true;
   for(int y=0; y<H; ++y)
      if( r[R][y] >= r[N][y] )
         right = false;

   bool can = false;
   if( left && !can ) can = rec(r, H, W, N, R);
   if( right && !can ) can = rec(r, H, W, L, N);
   memo[key]=(can ? 1 : -1);
   return can;
}
bool ok(const vector< vector<int> >& h, int H, int W)
{
   vector< vector<int> > rank(H, vector<int>(W));
   for(int y=0; y<H; ++y) {
      vector< pair<int,int> > hi;
      for(int x=0; x<W; ++x)
         hi.push_back(make_pair(h[y][x],x));
      sort(hi.rbegin(), hi.rend());
      for(int i=0; i<W; ++i)
         rank[y][hi[i].second] = i;
   }

   vector< vector<int> > r(W);
   for(int x=0; x<W; ++x)
      for(int y=0; y<H; ++y)
         r[x].push_back(rank[y][x]);
   sort(r.begin(), r.end());

   for(int y=0; y<H; ++y)
      if( r[0][y] != 0 )
         return false;

   memo.assign(W*W, 0);
   return rec(r,H,W,0,1);
}

int main()
{
   int H, W;
   cin >> H >> W;
   vector< vector<int> > h(H, vector<int>(W));
   vector< vector<int> > htr(W, vector<int>(H));
   for(int y=0; y<H; ++y)
      for(int x=0; x<W; ++x) {
         cin >> h[y][x];
         htr[x][y] = h[y][x];
      }

   cout << (ok(h,H,W) && ok(htr,W,H) ? "YES" : "NO") << endl;
}

E

10^6までの素数をエラトステネスの篩で作りながら、目標区間[A-B,A+B]の数字をその素数で割っていく。何回割れたか覚えておいて（last_e）増えてたらアウト。

int main()
{
   LL A, B;
   cin >> A >> B;
   vector<LL> cand;
   LL start = max(2LL, A-B);
   for(LL x=start; x<=A+B; ++x)
      cand.push_back(x);
   vector<int> last_e(A+B-start+1, 0x7fffffff);
   int cnt = last_e.size();

   static const int PM = 1000000;
   vector<bool> is_prime(PM+1, true);
   for(int p=2; p<=PM; ++p)
      if( is_prime[p] ) {
         for(int q=p+p; q<=PM; q+=p)
            is_prime[q] = false;

         for(int i=(p-start%p)%p; i<cand.size(); i+=p)
            if( last_e[i] )
            {
               int e = 0;
               LL c = cand[i];
               while( c%p == 0 ) {
                  c /= p;
                  ++e;
               }
               if( last_e[i] >= e )
                  last_e[i] = e;
               else
                  last_e[i] = 0, cnt--;
            }
      }

   cout << cnt << endl;
}

H

二分探索で焼け具合Vまで焼けるか探索。Vが決まれば、各鉄板では

• 1秒でVまで焼き尽くす地獄の業火 V*C[i]
• このまま残り時間いっぱい動かないとギリギリ焼き尽くす低温火傷作戦 V*C[i]/残り時間

のどっちかだけやってみる、というのを嘘解法のつもりでsubmitしたら通ってしまったがこれでよい理由がわかっていない。最初内側のループでも２分探索していて、さすがに 10^5 * log(10^10)^2 はTLEだったのですが誤差と２分探索の回数のベストバランスを探るメタレベル２分探索などをやって6WA出したりしていました。

template<typename Ite>
double minEneFor(Ite s, Ite e, double V)
{
   double curE = 0;
   double best = 1e+300;
   for(; s!=e; ++s) {
      best = min(best, curE+V**s);
      double heatForS = V / (e-s);
      double eneForS = heatForS * *s;
      curE += eneForS;
      V    -= heatForS;
   }
   return best;
}

bool canHeat(int T, double E, const vector<double>& C, double V)
{
   double heatFor0 = V / (T+1);
   double eneFor0 = heatFor0 * C[T];
   return eneFor0
      + minEneFor(C.begin()+T+1, C.end(), V-heatFor0)
      + minEneFor(C.rbegin()+T+1, C.rend(), V-heatFor0) <= E;
}

int main()
{
   int T;
   double E;
   cin >> T >> E;
   vector<double> C(2*T+1);
   for(int i=0; i<C.size(); ++i)
      cin >> C[i];

   double L = E / C[T];
   double R = (E / *min_element(C.begin(), C.end())) * (T+1) + 0.000001;
   for(int _=0; _<100; ++_) {
      double Ce = (L+R)/2;
      (canHeat(T,E,C,Ce) ? L : R) = Ce;
   }

   cout << setiosflags(ios::fixed) << setprecision(9) << L << endl;
}

※追記：そうか、V/残り時間ちょうどギリギリ焼き切れるよりも強めに炙った方が良いという可能性があるとしたら、それは、その鉄板より先がすべてその鉄板より熱効率悪い場合しかなくて、その場合はその鉄板で目一杯焼き尽くすのがよい。よってこの２通りのどちらか、でいいのかな？

G

ランダムに0/1決めれば50%の確率で答えが1になる。1になれば、そのとき入力につかっていたビット集合を二つに分けたらどちらかは1になるので、これを繰り返すと最終的に1になるところが決まる。これをK≦10繰り返す。めんどうだったので二つに分ける部分もランダムに分けた…。

map<vector<int>, int> memo;
int ask(const vector<int>& b)
{
   if(memo.count(b))
      return memo[b];

   cout << "?";
   for(int i=0; i<b.size(); ++i)
      cout << b[i];
   cout << endl;

   int res;
   cin >> res;
   return memo[b] = res;
}

int main()
{
   srand(time(0));
   int N, K;
   cin >> N >> K;

   set<int> done;
   while( done.size() < K )
   {
      vector<int> b, cand;
      for(int i=0; i<N; ++i) {
         b.push_back( done.count(i) ? 0 : rand()%2 );
         if(b.back())
            cand.push_back(i);
      }

      int res = ask(b);
      if(res)
      {
         while(cand.size() > 1) {
            vector<int> bb(N);
            vector<int> cX, cY;
            for(int i=0; i<cand.size(); ++i)
               if(rand()%2) {
                  bb[cand[i]] = 1;
                  cX.push_back(cand[i]);
               } else {
                  cY.push_back(cand[i]);
               }
            int r = ask(bb);
            swap(cand, r ? cX : cY);
         }
         done.insert(cand[0]);
      }
   }

   cout << "!";
   for(set<int>::iterator it=done.begin(); it!=done.end(); ++it)
      cout << (it==done.begin() ? "" : " ") << (1 + *it);
   cout << endl;
}

100000C10 ≦ 2^200 なので適切にバランスよい戦略をとれば決定的なアルゴリズムでも確定できるのだろうか。