以前書いた、Python対応してるTopCoderプラグインを発見してめちゃくちゃテンション上がってる - ぴよぴよ.py
の記事の通り、TopCoderのPythonプラグイン発見したので、 PythonでSRM595の問題を解いてみました。
いつもどおり1000点問題には挑戦してません。
SRM595 Div2 250
Little Elephant from the Zoo of Lviv likes balls. He has some balls arranged in a row. Each of those balls has one of three possible colors: red, green, or blue. You are given a string S. This string represents all the balls that are initially in the row (in the order from left to right). Red, green, and blue balls are represented by characters 'R', 'G', and 'B', respectively. In one turn Little Elephant can remove either the first ball in the row, or the last one.
RRGGBBとかあって、いくつ消したら一色(一文字)だけになるか。 一番長く連続してる部分みつけて全体からその数を引くだけ。
250は焦らずちゃんとコーナーケース考えましょう。
SRM595 Div2 500
Little Elephant from the Zoo of Lviv has some balls arranged in a row. Each ball can be painted in one of two possible colors: black or white. Initially all the balls are painted white. You are given an integer M, which represents the number of balls in the row. The balls are numbered from left to right, starting from 1. You are also given two tuple (integer)s L and R. To repaint balls, Little Elephant wants to use a robot. The robot will paint the balls in several consecutive stages. For each i, the i-th stage (1-based index) will look as follows: First, the robot will choose one of the two colors: white or black. Then, the robot will paint the balls with indices from L[i-1] to R[i-1], inclusive, using the chosen color. (Painting a ball covers all previous layers of paint.)
これは本番中に全く意味が理解できなかった。
問題の意味がわかれば全然難しい問題じゃない。 英語力、読解力、、。
一列に並んでる玉を左i番目から右i番目までを、白か黒に塗るんだけど、 最後まで塗った結果は何通りありえるか?みたいな問題。
L,Rのリストの後ろから見ていって、一つでも前までのリストと被らない玉があれば、 count+=1して、最後にpow(2, count)するだけ。
5行目、for i in reversed(xrange(0, len(L))): は
enumerateとか使ったら綺麗に書けるんでしょうか。
Pythonで競技プログラミングに挑戦するのは初めてだったので、
わかんないことだらけです。