Topcoder SRM 572(Div.2) 参戦記

あんまり更新していませんが、生きています。コンテストにもちょいちょい参加しています。ただ、あんまり書いていないだけです。

250-Problem:最近のSRMのDiv.2Easyはとにかく解いてもらおうという感じに思えます。初心者の人がとっつきやすくて良いです。単純に「整数配列の総積の符号を答えよ」なので、順に見ていって、マイナスなら反転、0があれば0にする、を繰り返せば終わりです。

500-Problem:解けている人が少ないのですが、これは問題文が今ひとつだったからでしょうか。折角なので訳出してみます(適当に補ったりして、問題文を通りやすくしています)。

英小文字からなる文字列に対し、次の2つの操作を施し、文字列を変換することを考える。
操作A:z以外の小文字を1文字選び、それを1文字後ろの文字に変換する。即ち、aをbに、bをcに、...、yをzに変換する。
操作B:a以外の小文字を1文字選び、それを1文字前の文字に変換する。即ち、bをaに、cをbに、...、zをyに変換する。
貴方は両方の操作を任意の回数、任意の順序で施すことが出来る。また、操作Aを一度行うためにかかるコストnextCostと操作Bを一度行うためにかかるコストprevCostが与えられるものとする。また、最初の文字列startと最後の文字列goalも与えられる。これらの文字列は全て英小文字からなっており、同じ文字は含まれないものとする。この時、startからgoalに変換するための最小コストを求めよ。なお、変換不能な場合は-1を返せ。

と、こうなるのですが、この問題文だけだと変換不能な場合は見えません(私の解釈がまずいのか？)。テストケースで"ae"から"cb"へのケースで-1を返しているので、どうやら斜体下線にした条件が変換過程においても守られなければならない、という条件なのだと思うのですが…。

私は、変換中にもこの条件を満たさなければならないという仮定の下、解答を作りました。要するに変換前後で"交わり"がなければよいので、変換前後の大小関係が推移的であればよいと言い換えて解きました。(正解したので、この解釈は合っていると思います)

得点は615.5, 順位は26位/770名. Ratingは1072->1174.でした。この出来でこの順位はどうなんだ？

Topcoder SRM 536(Div.1) 参戦記

はじめてのDiv.1でした。

250-Problem:Div.2 Hardと同じ問題でした。特に問題なく提出しましたが、やはり少し難しいように感じました。158.49点でした。

500-Problem:基本的には平均を出力すればよく、1目のサイコロがある場合だけ特別・・・と思っていたのですが、他にも特別な場合があったようです。撃墜されてしまいました。

得点は158.49, 順位は632位. Ratingは1200->1184. まだDiv.1で闘うには実力が足りません。

Topcoder SRM 535(Div.2) 参戦記

狐と鰻の仲の良さがわかる回です。

250-Problem:連立方程式の問題です。対称式なので、足したり引いたりすれば答えがでます。3つの未知数に対して4つの式がありますから、そこだけ注意しました。久しぶりなので、カンを取り戻しつつ丁寧に回答して、208.97pts.

500-Problem: m*n=GCD(m,n)*LCM(m,n)の関係を使います。これと、ユークリッドの互除法、Lの約数の全探索で書けばOKでした。しかし、Lの約数のうち、Gの倍数であるもののリストを取得して確認していったほうが手早いかもしれません。284.88pts.

問題はこちら(英語).
得点は493.85, 順位は81/1412. Ratingは1125->1200. ついに青くなりました。次からはDiv.1ですので、少し心配です。

Topcoder SRM 523(Div.2) 参戦記

始めに250点問題を解きました。まだC++に慣れていないのに忙しさにかまけて練習もしていなかったため、すごく時間がかかってしまいました。その上汚いソースです。提出して、172.29点を得ました。

次いで、500点でしたが、こちらは撃墜されてしまいました。何処が悪いのかまだ考え中です。

500点問題を解いた後大変眠くなりました。日本時間でA.M.3:00だから仕方ありません。私はそのまま眠ってしまいました。

問題はこちら(英語).
得点は172.29, 順位は487/1237. Ratingは1004->987.

Topcoder SRM 521 (Div.2) 参戦記

学校の実験が長引いたため、10分ほど遅れての参加になってしまいました。


Easy:簡単だったので208.13点で解くことが出来ました。

Medium:UTPC2011に似たような問題があったように思います。自分のソースのカッコの対応を調べるときの手法をそのまま打ちました。462.62点

Challenge:Mediumにおいて、")("というケースで一つ撃墜しました。もうひとつ撃墜し損なったので、25点です。

695.75,順位は102/1273でした。レートは結構上昇して、907->1004.

Only Source(ソースだけ)

This article is Only Source! I'm too busy now, so I can't write report.
本記事はソースのみです。忙しくて、レポートを書いている暇がないのでご了承ください。

There are sources which I made at the next contest.
次のコンテストで作成したソースです。

・Codechef September Long/Short
・Codeforces #87 (Div.2) / #88
・Topcoder SRM 518(Div.2)
・UVa The Seventh Hunan Collegiate Programming Contest Semilive
・UAPC 7th

Topcoder SRM 517(Div.2) 参戦記

Intermissionで自分のミスに気づき、それを応用したため多く撃墜できました。

Easy: Javaは得意ではないので、時間がかかってしまいました。C++のstringとvectorをさっさと修得すればこんな事言わなくて済むので、修得したいところです。163.5点でした。

Medium: 400.26の時に提出したのですが、前述のとおり、ミスを発見してしまいました。 そのミスというのは、pを素数、kを2より大きい自然数とするとき、N=p^kかつtarget=p^2 であるようなケースを考慮に入れていなかったことです。システムテストを通るはずはありませんが、このケースを片端から試したので、撃墜ラウンド+3/-3でした。全部で75点！

Hard:Greedyと思ったんですが、違うようです。解けませんでした。

スコアは218.5で、順位(Div.2)は241/1462、Rateは823->900でした。ようやく緑に戻りました。はぁ。

Topcoder SRM 515(Div.2) 参戦記

JAVAとC++を両方使った珍しいコンテストでした。


250点問題はJAVAで解きました。七面倒臭いプログラムになってしまったのは、私が　JAVAやC++にまだ十分習熟していないためです。そのため、時間もかかってしまい、解けたのは176.96点でした。

続いて、500点問題をC++で解きました。この問題は楽しめたのですが、システムテストで落とされてしまいました。冷静に考えて後から再度書くとおりましたので、つまらないミスをしていたのでしょう。本記事に書いてあるのは通った方の正しいソースです。

500点問題について、試してみるという人が多かったのですが、私の解法を説明します。なお、Div.1の250点問題と同じです。
hourHand%30*2を計算することにより、分を求めることができます。これで、12時の方向からの回転角度を求め、時計を正しい方向に向けます。これがありえない角度になっていなければ、時計を読んでOKです。

問題はこちら.
得点は176.96、順位は694/1093、Rateは866->823でした。ちょっと最近不調でしょうか。もっとJAVAやC++のソースを書かないといけません。

Topcoder SRM 514(Div.2) 参戦記

結局解けたのは250だけでした。

250：C++の練習として解きました。慣れないのでコンパイルを通すまでに苦労しましたが、191.66点で解きました。

500：BFSか？と思いましたが、あまりよいアルゴリズムとは思わず、時間も間に合いそうになかったので、解きませんでした。終了後、rng_58さんやchokudaiさんのコードを見ましたがすごくシンプルでした。

191.66,436/996でした。

Topcoder SRM512(Div.2) 参戦記

お世辞にもいい出来とは言えませんでした。

256点に正解したのですが、他は解くことができませんでした。

512点は問題を読んでも方針が立ちませんでした。

1024点はひと通り組み終わったと思った後に、読み間違いに気が付きました。気がついたときには後10分でしたので、ギブアップしました。

問題はこちら。1495人中553位で231.55点でした。

Topcoder SRM511(Div.2) 参戦記

Javaしか使えないのを含めて、TopcoderはCodeforcesやCodechefに比べて苦手です。勝つために、JavaやC++をもっと練習すべきかもしれません。

開始後、慣れないJavaに苦戦しながら、250点問題を解きます。非常に時間がかかり、約30分かけてSubmit.155.83点です。

その後、やはりいろいろ考えながら、一見難しそうな500点問題に取り組みます。これにも約30分かかり、281.23点。そのままCoding Phaseは終了しました。

Challenge Phaseも、遅くて0点。自分のソースが撃墜されてしまいました(TT)。

結果、741位でScore=155.83でした。