SRM662 Div2

競技プログラミング srm

250

概要

数値が与えられるので、16進数に変換したあと、0,1をそれぞれO,Iに置換した文字列を出力する。 ただし、出力する文字列に数字が含まれる場合は代わりにError!と出力する

解法

やるだけ

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class Hexspeak:
    def decode(self, ciphertext):
        s = '%X' % ciphertext
        s = s.replace('1', 'I').replace('0', 'O')
        for i in range(2, 10):
            if str(i) in s:
                return 'Error!'
        return s

500

概要

nとmが与えられるので、n個のノードを持ち、m個の葉を持つ木を出力せよ

解法

単一の点にm個のノードを連結する。この時点で葉がm個の木ができる。

あとは、葉を増やさないように、最後に連結したノードに連結する、というのを繰り返す。

#include<bits/stdc++.h>
#define INF (1 << 30)

using namespace std;
typedef long long ll;

struct ExactTreeEasy
{
  vector<int> getTree(int n, int m)
  {
    vector<int> v;
    v.push_back(0);
    v.push_back(1);
    for(int i = 2; i < m + 1; i++)
    {
      v.push_back(1);
      v.push_back(i);
    }
    for(int i = m + 1; i < n; i++)
    {
      v.push_back(i - 1);
      v.push_back(i);
    }
    return v;
  }
};

1000

概要

監視が3点以下の点(x, y) (|x|, |y| <= 2000)に存在する。監視からできる限り遠い距離を保ったまま、(10100, 0)まで逃げたい。監視が動くことはない。

上記の時、監視と最も近づくときの距離を出力せよ。

解法

少し考えると、監視が作る図形の中に点(0, 0)が存在しない場合、監視がいない方向に逃げることができるため、点(0, 0)と監視との距離のうち最小のものが解となる。

例えば、監視が3点(1, 1), (1, 0), (1, -1)に存在するとき、(-1, 0)方向から大回りすることができる。

このパターンはsample1が該当する。監視が2点以下の時は図形を作らないため、常にこのパターンとなる。

逆に、監視が作る図形の中に点(0, 0)が存在する場合はどの方向に逃げても監視の間を通る形になるため、各監視間の距離のうち最大の場所を通れば良いことがわかる。

この場合の解は、min(各監視間の距離の最大, 各監視と(0, 0)との距離の最小値)となる。

点の内包判定には外積を使用することもできるが、ライブラリを適当に貼り付けた。

#include<bits/stdc++.h>
#define INF (1 << 30)

using namespace std;
typedef long long ll;

#define PI 3.141592

int winding_number(double x, double y, double p[][2], int n)
{
  double x1 = p[n - 1][0] - x, y1 = p[n - 1][1] - y;
  double s = 0;
  for(int i = 0; i < n; i++)
  {
    double x2 = p[i][0] - x, y2 = p[i][1] - y;
    double tx = acos((x1 * x2 + y1 * y2) / sqrt((x1 * x1 + y1 * y1) * (x2 * x2 + y2 * y2)));
    s += tx;
    x1 = x2; y1 = y2;
  }
  return (abs(s) + 0.000001) / 2 / PI;
}



struct Flee
{
  double p[3][2];
  double maximalSafetyLevel(vector<int> x, vector<int> y)
  {
    double s = 1000000000000;
    for(int i = 0; i < x.size(); i++)
    {
      p[i][0] = x[i];
      p[i][1] = y[i];
      s = min(s, sqrt(x[i] * x[i] + y[i] * y[i]));
    }
    if(x.size() < 3 || !winding_number(0, 0, p, 3))
      return s;
    double a = 0;
    for(int i = 0; i < x.size(); i++)
    {
      int i2 = (i + 1) % x.size();
      int dx = x[i] - x[i2], dy = y[i] - y[i2];
      a = max(a, sqrt(dx * dx + dy * dy) / 2);
    }
    return min(a, s);
  }
};

感想とか

余裕で全完したと思ったら1000が落とされた。