yukicoder No.333〜335

yukicoder

RMQのセグメントツリー実装でバグが合ったらしく、かなりの時間悩んだ。

まだ336解いてませんが、取り敢えずここでコード載せておきます。

No.333 門松列を数え上げ

問題概要

左端、真ん中の門松の長さが与えられるので、右の門松で門松列を満たす長さの数を答えよ。

No.333 門松列を数え上げ - yukicoder

続きを読む

Codeforces Round #339 (Div. 2)

Codeforces

誤読が酷い。

A. Link/Cut Tree

問題概要

l〜rの間のk^n(nは整数)を満たすものを全て出力せよ。

Problem - A - Codeforces

解法

普通に実装すればいいんじゃ？と思って提出→WA。

JavaのBigintegerやPython使えば普通に通る。

C++で通すなら、普通に解くのではなく、lとrを割っていき、l≦1≦rを満たすものを数える。 最初に1度も割らずにチェックして、以降は割りながら配列に何回割ったのかを記録。 その後、k^a[i]を出力すればOK。

続きを読む

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)から値を下げるようループを回してあげる。

続きを読む