つーさのくーかん

新しいネトゲを始めました。
その名も、Codeforces - http://codeforces.ru/

登録したのはずいぶん前ですが、
なかなかタイミングが合わず放置しておりまして、
今日はたまたま家にいたので初参戦してみんとてすなり。

なんぞやそれ

プログラミングコンテストの一種。
ICPCやオンラインジャッジに触ったことのある人は、そんな感じ。
TopCoder SRMに触ってる人もそんな感じ。
開始と同時に問題が公開され、回答プログラムを書いて出す。
出すと、pretestという簡易ジャッジが走り、それに通れば受理。
提出時刻と誤答提出回数に応じて暫定スコアが計算される。
ICPCとは違ってここではpretestという簡易テストしか行われないのですね。
出したプログラムに自信があれば、Lock(もう出さないよ宣言)ができ
Lockした問題については、他の人の回答を見ることができる。
「ははーん、バグあるよこいつの答え」というのを見つければ、
そのバグが顕在化するテストケースを入力することで撃墜(hack)ボーナス点がもらえる。
TopCoderで言えば「問題ごとに」「自分のタイミングで」チャレンジフェーズに入れる。
撃墜された人は、その問題をLockしていなければ再提出できるけど、
Lockしちゃってたらもう出せない。hackは続行可能。

制限時間経過後に、受理されたコードについて、
コーナーケースなどを含むより大きなデータセットでテストし、
それが通ればスコアが確定、通らなければスコアは没収。
順位を決定して、レーティングをつける。

#27

Div.2ラウンドということで、まぁ、
そんなに難しい問題は出ませんでした。
せいぜいICPCの国内予選のレベル？　かな。
問題ざっと見て、これならEまで全部通せるんじゃねーの、と。

終わってみれば結果はなんか悲惨なことに……。
My Submittions - http://twitpic.com/2n2t6d

慢心ですな……。慢心……。はぁ。

最初はC++を使ってましたが、
Aが通ってからB,Cを連続で蹴られ、
心折れてC#を使い出しました。
使えるものは使わないとね！(いいわけ
……まぁ、使ってもあんまり結果は変わらなかったのですが。

A

n個<=3000 のエントリについて、それぞれ格納する位置が入力される。
全部入力し終えたところで、空いてるマスのうち一番小さい位置を返せ。

printf("%d\\n", 3001); って書いた俺爆発しろ！　そこはn+1だろう。
与えられたテストだけじゃなくて、自分でケース作ってみんといけん……。
問題が簡単だと、その分速く出さなきゃと焦ってしまいがちで。
簡単なケアレスをやらかすわけ。慢心ですな……。慢心……。はぁ。

B

n人<=50のリーグ戦。n(n-1)/2 回の試合が行われる。
参加者の強さはそれぞれ異なり、必ず強い方が勝つ。
n(n-1)/2-1 回分の試合結果から残りの1回の試合結果を答えろ。
結果がいろいろ考えられる場合はどれかでいい。

C++で書いてなんかpretest蹴られて、同じ内容をC#で書いてAccepted。
残ってる対戦が誰と誰のものかを特定するのとかめんどかった。
C#のListなら、FindIndexとか、デリゲート渡して勝手にやってくれるのに。
C++だと、vectorのソート(ユーザ定義順)の仕方もわかんないっていうのは。
ファンクタ使うんだよね。めんどくさ。
lessみたいなの、自分で作れるようになっておいた方がいいよなぁ。
ほにゃー

C

1,2,3,100 は増加数列で、3,2,1,1 は減少数列、1,3,3,1 はどっちでもない数列である。
数列のサブシーケンスとは、順番を入れ替えずにいくつかの要素を削除したものである。
与えられた数列(要素数n<=100000)のサブシーケンスのうち、もっとも短い「どっちでもない数列」を1つ構成して、その各要素のインデクスを答えろ。
作れない場合は0を答えろ。

これはpretest蹴られっぱでなんかよくわからん。
どれか1つを作れってことだし、
作れる場合は必ず長さが3になって、
数値が増えてる部分と減ってるところを見つけて、
手前にある方の前後と、後にある方の後を答えて見たんだけど。
だめなのかな？

先にE

整数n<=1000について。
n個の約数を持つ一番小さな整数を答えなさい。
結果の整数は<=10^18を保証。

思いつき。
4 -> 6(1,2,3,6)
6 -> 12(1,2,3,4,6,12)
素数表を作って、素因数分解する。 4=2*2 と 6=2*3
出てきた素因数列をひっくり返す。 2,2 と 3,2
それぞれから1引いて、1,1 と 2,1
2からの素数に割り当て、べきを取る。2^1*3^1=6 と 2^2*3^1=12
pretestはさっくり通った、けど、システムテストで落ちる。
うーん、だめなのかー。

D

n個<=100の町がリング上につながっている。
ここにm本<=100の道を作る。道はそれぞれ都市a_iとb_iを結ぶ。
リングの外側でも内側でもいいけど、交差しちゃだめ。
それぞれの道について、内側に作る場合はi外側に作る場合はoを出力せよ。
実現できない場合はImpossible.

残り11分のところから書き出した。
ちょっと間に合うか微妙だったけど。
とりあえず、道を作ってってみればいいよね。
リングの外側の世界と内側の世界と分けて、
内側で完結できなかったら外側に持ってけば。
重なっちゃうかどうかの判定もそんなに難しくないよね。
提出はしたけど、Presentation error on pretest 4 だそうで。
Impossible.の.はいらなかったらしい。わかりにくい。

でも、この方法も、今思えば吟味が足りないか。
道を作る順番によって手詰まったりうまくいったりする、かも。
.を直して送ってみたけど、やっぱりWAだった。

おわり

基本的に意地悪にできてる。
まぁいけるんじゃね？　だと落ちる。
確実にこれでいける　まで持って行く。
いかにTopCoder SRMのテストケースが親切で、
いかに自分が用意されたテストケースに頼っているか、
というのを実感する2時間だった。

222位で、最初のレーティングは1413の緑。
こっちも積極的に参加して、こういうICPCライクのスタイルに慣れておきたいなぁ。