Codeforces Round #338 (Div. 2)

Codeforces

結構悲惨だったけど、Good Byeよりマシか。

A. Bulbs

問題概要

手元にいくつかのスイッチがあり、各スイッチはいくつかのランプにつながっている。最初は全部のランプが消えているとき、 手元にあるスイッチを押して全部のランプをつけることができるか判定せよ。
Problem - A - Codeforces

続きを読む

AtCoder Begginer Contest 032

AtCoder

最近、ABCの難易度の低下が激しいと思ったけど、前回よりは難しくなった？

A - 高橋君と青木君の好きな数

問題概要

n以上の整数で、aでもbでも割れる最小の整数を答えよ。
http://abc032.contest.atcoder.jp/tasks/abc032_a

解説

取り敢えずaでもbでも割れるってことは求める整数はaとbの最小公倍数の倍数。

自分は互除法を使ってLCM(a,b)=a*b/GCD(a,b)で出しましたが、aとbの制限が緩いので1から順に試して、aでもbでも割り切れた時、でもOKです。

続きを読む

yukicoder No.320 眠れない夜に

yukicoder

今年最後の問題かなぁ…（冬休みの課題の息抜きに）

問題

No.320 眠れない夜に - yukicoder

解法

まず、早めに間違えると大きな誤差を生むことが分かる。その様子を見てみる。例えばa3で間違えると、
a3=1(-1)、a4=2(-1)、a5=3(-2)、a6=5(-3)、…
と、元の値からどの位離れていくかがフィボナッチ数列になる。

よって、予めフィボナッチ数列の80項まで調べておき（ギリギリC++のlong longで収まる。不安だったのでJavaでBigInteger使って確かめた。）、どの位足りないかを見るためm=an-mとする。
a3に間違えた時から順に仮定していき、変化量がm以下ならmから引いてあげる。実際はフィボナッチ数列のa(n-2)から値を下げるようループを回してあげる。

続きを読む

Codeforces Round #337 (Div. 2)

Codeforces

Codeforcesは2回目の参加。

A. Pasha and Stick

問題概要

Pasha has a wooden stick of some positive integer length n. He wants to perform exactly three cuts to get four parts of the stick. Each part must have some positive integer length and the sum of these lengths will obviously be n.

Pasha likes rectangles but hates squares, so he wonders, how many ways are there to split a stick into four parts so that it's possible to form a rectangle using these parts, but is impossible to form a square.

Your task is to help Pasha and count the number of such ways. Two ways to cut the stick are considered distinct if there exists some integer x, such that the number of parts of length x in the first way differ from the number of parts of length x in the second way.
簡単な意訳
長さnの木の棒があります。4本に切って長方形（正方形ではない）を作るとき、出来る長方形は何通りありえるでしょう。

続きを読む

AOJ0016:Treasure Hunt

AOJ

英語の勉強で発音の問題をやっていたら、発音以前に単語が分からない。そんな辛さの中の息抜きで1問。

問題概要

(0,0)をy軸正の向きでスタートして、移動と方向転換を繰り返し、最終的にいる座標を求める問題。
Treasure Hunt | Aizu Online Judge

解法

素直にシミュレーション。角度は必ず整数で与えられるので、最初から何度回ったのかを整数で保存しておき、使う時だけ/180*M_PIしてあげればいいと思う。

#include <bits/stdc++.h>
using namespace std;
int flr(double x){
	if(x<0)	return ceil(x);
	else 	return floor(x);
}
int main(){
	double x=0,y=0;
	int arg=90;
	while(true){
		int d,a;	scanf("%d,%d",&d,&a);
		if(d==0&&a==0)	break;
		double args=(arg)/180.0*M_PI;
		x+=d*cos(args);	y+=d*sin(args);
		arg-=a;
	}
	printf("%d\n",flr(x));
	printf("%d\n",flr(y));
	return 0;
}
感想

普通に解けるんだけど、これ解いててC++は小数点以下を丸めるとき、普通では値が必ず小さくなるよう丸めることを思い出した。Pythonとかなら絶対値が小さくなるよう丸めるから特に考えることもなく通せたんだけど。
そういえば今日20:00からCodeforcesです。出ましょう。

SRM677 Round1 Div.2

TopCoder

一応SRMは今年の3月に始めたのですが、基本的に深夜に行われていたり、学校にいる最中に行われていて中々参加が難しかったのですが、冬休みになって深夜の参加に挑戦してみました。

Easy PalindromePrime

問題概要

A positive integer is called a prime if it has exactly two distinct positive integer divisors: 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, ... A positive integer is called a palindrome if its base-10 representation reads the same forwards and backwards. Some palindromes: 2, 77, 101, 33333, 12344321. A positive integer is called a palindromic prime if it is both a palindrome and a prime. You are given two ints: L and R. Compute and return the number of palindromic primes between L and R, inclusive.

簡単な意訳
1000以下の自然数L,Rが与えられる。L～R（L,Rを含む）の間の素数でかつ回文数のものの数を答えよ。

続きを読む