TopCoder SRM 464 - simezi

参加。
250-550-1000のセット。

Easy

各桁が0-9からなるある文字列が「カラフルである」とは、
その文字列のどんな連続する各桁の積も、全て異なることである。
このときn桁のカラフルな文字列のうちk番目に小さなものを求めよ。

あれ、250だけどパッと方針が立たないぞ……
nが50以下、kは10億以下らしい。とすると探索でもなく性質から直接求まるのだろうか。
よくわからないので何個か具体例を作る。

同じ数は２つ使えないし、２桁以上の場合0,1も入れられない。
じゃあそんなに多くもないから全列挙してみよう。
→書く→サンプル合わない

あれえこれずいぶん難しいなあ。
Summary覗くとやはりみんな苦戦気味のよう。

かなり色々とprintデバッグ→判定関数が間違ってる！→修正
→最初の生成が間違ってる！→修正→サンプル合う→submit（約40分）

Medium

これはもうやってる時間なさげ。
とりあえず読んでみる。

色のついた正方形の紙をn枚、座標平面上に座標軸に辺が平行になるよう置きたい。
i枚目の正方形の中心は(xa[i],ya[i])もしくは(xb[i],yb[i]）でなくてはならず、正方形同士は重なってはいけない。
各正方形の大きさを自由に決められるとき、最小の正方形が最大になるような紙の置き方をしたときの、最小の正方形の大きさを求めよ。

……なんか二分探索っぽい？でもn=50だと二分探索してDFSとか無理っぽい。
グリーディーでいけるのかと思ってコードを書き始める。
書いてるうちに気のせいだったことに気づく。あきらめてEasyを見直す。

あ、これn=1の場合って0,1も正解の文字列になるじゃん。
→修正してResubmit
これでおｋのはず……

残り時間5分。撃墜ケースでも考えよう。

Challenge

Easyは

n=1の場合わけをしてないやつ
n=8以上で全列挙しようとしてるやつ

を狙うことに。

n=1の場合分け漏れを一個見つけた。撃墜。
Summaryみると一回ミスってもそんなに順位さがらなそう。
なので全列挙してるっぽいのにTLE狙いででかい数入れてみる。
→あれ、普通に時間内に終わってる

これ以上ミスると0点になって順位が100番くらい下がるので今度は確実に落とせそうなのを探す。ない。終了。

Result

0完1撃墜1ミスで25点。

Challengeで損をしないという目標だけは達成。
にしてもちょっと複雑なプログラムになるとまともにコーディングできないなあ。
バグを出さない思考＆コーディングする訓練がんばろう。

たぶんコーディング力強化で1800の壁は超えられる。まずはそこを目標に。