Hatena::Grouptopcoder

minus9dの記録

2013-11-20

EmacsでTopCoder

| 23:46 | EmacsでTopCoder - minus9dの記録 を含むブックマーク はてなブックマーク - EmacsでTopCoder - minus9dの記録

Eclipseがどうにも使いにくいので、EclipseCoderを捨ててEmacsでコーディングすることにした。手順は以下。

  • 401 Unauthorizedに従い設定
    • ただし、これらの項目をすべて行った後、Options→Editorにて「CodeProcessor」のDefaultにチェックを入れる必要があった
  • Arenaで問題を選んだら、テストケース付きソースコードが、自分の指定したディレクトリに自動生成される。そのソースコードを、Emacsに限らず好きなエディタで編集すればよい。

自分用のC++のテンプレートは以下。

#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;


class $CLASSNAME$ {
public:
  $RC$ $METHODNAME$($METHODPARMS$) {
    $RC$ result;
    return result;
  }

  $TESTCODE$
};

// BEGIN CUT HERE
int main() {
  $CLASSNAME$ ___test;
  ___test.run_test(-1);
}
// END CUT HERE

2013-03-11

2013 TCO Algorithm Round 1C

| 23:21 | 2013 TCO Algorithm Round 1C - minus9dの記録 を含むブックマーク はてなブックマーク - 2013 TCO Algorithm Round 1C - minus9dの記録

Round1Aと1Bは都合が合わず、今回が2013年の初参加。oo-。R1324→R1353。チャレンジフェーズ終了時712位でダメかと思ったが、システムテスト終了時には456位になっておりRound1を通過できた。普段解けるはずがないDiv1のMediumがまるで解けたかのような成績になってしまい後ろめたい。

250 TheArray

問題

長さnの配列がある。配列の隣り合う要素の差は最大でもdである。配列の最初の値firstと最後の値lastとが与えられる時、この配列の要素がとりうる最大値を答える。

本番

配列arrayの最初の要素はarray[0] = firstで、次の要素array[1]は最大でもfirst + d。同様に考えるとarray[i]は最大でもfirst + d * iであることが分かる。

今度は逆向きに考える。配列arrayの最後の要素はarray[n-1] = last。その1個前の要素は最大でもlast + d。同様に考えるとarray[i]は最大でもlast + d * (n-1-i)。

各要素のとりうる最大値は、順向きの最大値と逆向きの最大値の小さい方となる。あとは各要素がとりうる最大値のうちの最大値が求める値となる。

絵で書くと、赤丸の中でもっとも値の大きい要素の値を求めることに相当する。

f:id:minus9d:20130311232015j:image

本番では汚いコードになってしまったが考え方は合っていたので気にしない。以下はSnapDragon氏の簡潔な解答を引用。引用元:http://community.topcoder.com/stat?c=problem_solution&rm=316576&rd=15585&pm=12455&cr=272072

for (int i = 0, x = first; i < n; i++, x += d) v1[i] = x; 
for (int i = n-1, x = last; i >= 0; i--, x += d) v2[i] = x; 
for (int i = 0; i < n; i++) ret = max(ret, min(v1[i], v2[i])); 

500 TheOlympiadInInformatics

問題

情報オリンピックの参加者がN個の部屋(0~N-1)に割り振られている。JohnはN番目の部屋の唯一の参加者である。Johnは各部屋に何院参加者がいるか知らないが、各部屋の参加者の得点の合計は分かる。

各部屋の参加者の得点の合計が与えられた時、Johnが少なくともk人の参加者の得点を確実に上回るために必要な最低の得点を答える。

本番

Johnがn点取ったと仮定した時、Johnが何人の参加者の得点を上回っているかの計算は容易である。2分探索をすればよさそう → とても汚いコードだったが一応正解できた。

「Johnがn点をとったときはk人を上回り、n-1点をとったときはk人を上回らない」…そんな境界となるnを明示的に求めようという意図でこのような汚いコードとなった。しかし、SnapDragon氏のコード http://community.topcoder.com/stat?c=problem_solution&rd=15585&rm=316576&cr=272072&pm=12456 を見るともっときれいにかけていた。確かにこうすると、ループを回しているうちにlo == hiとなって終了し、その時のloの値が求める値であることがはっきり分かる。

以下はそのコードの引用。

  int lo = 0, hi = 1000000001; 
  while (lo < hi) { 
    x = (lo+hi)/2; 
    long long tot = 0; 
    for (i = 0; i < sums.size(); i++) tot += sums[i]/(x+1); 
    if (tot <= k) hi = x; else lo = x+1; 
  } 

2013-03-07

SRM 572 Div2

| 23:01 | SRM 572 Div2 - minus9dの記録 を含むブックマーク はてなブックマーク - SRM 572 Div2 - minus9dの記録

2問早解きしてoo-。自己最高の6位がとれてかなり嬉しい。これで23試合目にして5回目のDiv1昇格。

500 NextOrPrev

問題

文字列に対して、Nextという操作とPrevという操作が定義されている。Nextという操作では、アルファベットを一文字選んで、文字列中に現れるすべてのそのアルファベットを次のアルファベットで置き換える。Prevでは前のアルファベットで置き換える。

NextとPrevの操作にはそれぞれコストがかかる(nextCost, prevCost)。

文字列startから文字列goalに変化させるのに必要な最小コストを求めよ。もし変化させることが不可能なら-1を出力せよ。

本番

テストケース1)で"ae"から"cb"へ変化できないというのが理解できず、問題文を読みなおす。そこで、NextとPrevは同じアルファベットすべてについて作用するということに気付いた。そこで改めて"ae"を変化させることを考えると、

  • "ae"
  • → aにNextを作用させて"be"
  • → bにNextを作用させて"ce"
  • → eにPrevを作用させて"cd"
  • → eにPrevを作用させて"cc"
  • → cにPrevを作用させて"bb" (失敗)

という感じで、途中で1文字目の2文字目のアルファベットが同じになってしまい失敗することが分かる。これは、文字列startでは1文字目の方が2文字目より小さいのに対して、文字列goalでは2文字目の方が1文字目より小さい、という大小関係の逆転が存在するのが原因。

文字列startから文字列goalに変化させることができる必要十分条件は、文字列startを構成する各文字の大小関係が、文字列goalを構成する各文字の大小関係と同じでありそうなことが分かる。大小関係を確かめる方法として、私はそれぞれの文字列をソートして、ソート後の文字列の各文字がもともとの文字列の何番目の位置にあったか、がすべて一致するかどうかを調べる方法をとった。そこそこ簡潔に書けて満足。

1000 DistinctRemainders

わからん。後で。

2013-01-31

SRM 567 Div1

| 23:02 | SRM 567 Div1 - minus9dの記録 を含むブックマーク はてなブックマーク - SRM 567 Div1 - minus9dの記録

数論の前に玉砕して---。R1257→R1212となり早くも崖っぷち。

250 TheSquareRootDilemma

問題

Aは1以上N以下の整数。Bは1以上M以下の整数。(\sqrt{A}+\sqrt{B})^2が整数となるようなペア(A, B)の数を数える。

本番

(\sqrt{A}+\sqrt{B})^2が整数」 ⇔ 「\sqrt{AB}が整数」というのはすぐわかるが、この後難しく考えてしまい時間切れ。

後で

Aを固定して考える。例えばA = 42471 = 3^3 * 11^2 * 13の場合を考える。このとき\sqrt{A} = 3 * 11 * \sqrt{3 * 13}。すると、\sqrt{AB}が整数になるようなBというのは、\sqrt{B} = 1*\sqrt{3 * 13}, 2*\sqrt{3 * 13}, 3*\sqrt{3 * 13}, ...というふうに求められることがわかる。あとはAを1からNまで変えながら、\sqrt{AB}が整数となるBの数を数えていけばよい。

以下は後で通したコード。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;

class TheSquareRootDilemma {

void getFactors(map<int, int> &factors, int n){
	factors.clear();
	for(int i = 2; i * i <= n; ++i){
		while(n % i == 0){
			n /= i;
			++factors[i];
		}
	}
	if (n != 1){
		++factors[n];
	}
}

public:
	int countPairs(int N, int M){
		int ret = 0;

		for(int a = 1; a <= N; ++a){
			map<int, int> factors;
			getFactors(factors, a);
			int b_is_multiple_of = 1;
			for(map<int, int>::iterator it = factors.begin();
					it != factors.end();
					++it){
				int factor = it->first;
				int power = it->second;
				if (power % 2){
					b_is_multiple_of *= factor;
				}
			}

			for(int b = 1; b*b*b_is_multiple_of <= M; ++b){
				++ret;
			}
		}
		return ret;
	}

};
さらに後で

さっきはAを素因数分解して、Bが何の倍数になるかというのを考えた。しかしAをわざわざ素因数分解する必要はなく、Aを割り切れる最大の二乗数(上の例だと39^2)を求めれば十分。こちらのほうがミスなくコードを書ける。

2013-01-22

SRM 566 Div2

| 23:42 | SRM 566 Div2 - minus9dの記録 を含むブックマーク はてなブックマーク - SRM 566 Div2 - minus9dの記録

oo-。ずっとリーチ状態だったが、ようやくDiv1に上がれた(R1189→R1257)。

500 PenguinPals

  • 問題
    • 赤色のペンギンと青色のペンギンが輪になっている。同じ色同士のペンギン同士を結んで作れるペアの最大数を求める。
  • 解法
    • 本番では、解説されているGreedyな方法を採用して無事解けた
      • 隣り合う同じ色のペンギンから繰り返しペアを作る。すると最後に残るのはかならずRGRGRG...またはGRGRGR...のパターンになる。このパターンから作れるペアの数は、絵を描くことで簡単に考察できる。
    • C++で同じ文字列を繰り返し置換する良い方法を知らない。私は以下のコードを使っている。
string str = "aa bb cc aa bb cc";
string from = "bb";
string to = "bbbbb";

string::size_type pos = str.find(from);
while(pos != string::npos){
    str.replace(pos, from.size(), to);
    pos = str.find(from, pos + to.size());
}

cout << str << endl;  // "aa bbbbb cc aa bbbbb cc"

1000 FencingPenguinsEasy

  • 問題
    • 円状に配置されたポストの中にペンギンがいる。ポストからポストへ線を引いてペンギンが全部中に入るようにポリゴンを作る時、ポリゴンの面積の最小値を求める。
  • 解法
    • 幾何は手がかりさえつかめなかった。後で解説を読んで8割方理解できた。以下は自分が思い出すための概略メモ。解説の絵を見るとよく分かる。
  1. ペンギンの座標を極座標系から直交座標系へ変換
  2. 前処理で、すべてのポストの組(A, B)についてvalidかどうかを判断
  3. f(l, r)を、使用するポストのうち最小のものをl, 最大のものをrとしたときのポリゴンの面積の最小値と定義する
  4. ポストlの次に選ぶべきポストをnlとすると、f(l,r) = S(△r, l, nl) + f(nl, r) となる
    • 三角形の面積は、外積の絶対値の1/2になることに着目して求める。つまり、点O(原点), 点A(Ax, Ay), 点B(Bx, By)がなす三角形の面積は、1/2 * | Ax * By - Ay * Bx |
  5. 後は動的計画法で解く

右回りか左回りかを求める関数と、三角形の面積を求めるコードは保存した。