SRM 466 Div1 - simezi

一昨日のCodeforcesと同じくらいの時間帯だったのだけど、今回は眠気が酷かった。自分の場合コンディションはそこまで影響しないのだけど、ラウンド開始を待ってるのが辛かったｗ

できれば2問正答+250点問題200点というのが事前の目標。

Easy

250-500-1000の標準セット。
問題を読む。

番号の書かれたくじがある。くじの数字が全て0、またはくじの数字の約数が奇数個のときくじは当たりである。くじの数字を何桁か改竄して当たりくじにしたい。このとき当たりくじを作るために必要な最小の改竄する桁の数を答えよ。

日本だったら問題になりそうな問題文じゃない？ｗ
とりあえずくじの数字の約数が奇数個ってことは……小学生の頃習ったなこれ！平方数の時に約数が奇数個になる！
たしかn個の小さな正方形を長方形に並べていくとき、nが平方数なら正方形が出来るから約数が奇数個になるとかやった記憶があるぞ（平方数という言葉自体は習わなかったが）

で、幅優先でいいのか？間に合うのかなあ。状態数は10!くらい？
とりあえず書いてみる。ちゃんと動かない。あれー。

数字を一桁変える処理が間違ってるっぽい。なかなかバグが取れない。しょうがないので文字列のまま探索しよう。どうせ250だしそんなに難しいわけは（

全面的に書き直した。チェックするルーチンのとこで数字に変換する方式に。
書いた。おｋ.サンプルも通る。Submit.

Medium

やーハマった上に全部書き直した所為でめちゃくちゃ時間かかったorz170点とか早速目標時間オーバーじゃん……
まあまだ取り返しがつく範囲。問題を読む。

N行5列に1-5*Nまでの数字がかかれたくじがある。当たりの番号5つが無作為に選ばれ、くじのどこかの行に3つ以上その当たり番号が書かれていればそのくじが当たりとなる。
買ったくじの番号が無作為に並んでいるとき、それが当たりくじである確率を求めよ。

うーん、N≦100って探索？DP？いやでも何か直接求まりそうな……

紙に書いて場合わけする。
当たり番号は無作為だから12345が当たり番号としよう。
で、当たり番号の並び方は

1行に5個全部
1行に4個、他の1行に1個
1行に3個、他の1行に2個
1行に3個、他の1行に1個、他の1行に1個
1行に2個、他の1行に2個、他の1行に1個
1行に2個、他の1行に1個、他の1行に1個、他の1行に1個
5行に分散

があって、当たりのケースは上の4つだけ。
なのでそれを式立てればいい。

書いた。ん？なんか答えが一桁違う……
以下順列と組みあわせの違いをどうしたらいいのかと延々とハマる。
当たりの個数が同じ行が二つあるときはその二行は区別するのか？どうすんだっけ……コード書いて答えがそれっぽくなるやつ採用しよう←バカ

それっぽくならねえ！
まってよ何でだー。。。（20分以上はまる）

ここで気づく。1行のなかに1個だったら5通り場所あるじゃねーか！！！
早く気づけよアホorz
という訳で書き直す。おーサンプル合った！！！Submit.

Hard (unopened)

まだ20分以上残ってる。でもHardなんて自分に解ける確率は相当低いだろうしEasyとMedium見直したりチャレンジケース考えたりしたほうがよさそう。
という訳でEasyがTLEにならないかテストしてみる。
適当に数字を投げる923540531とかそんな感じの。

通った。もう一個。あ、TLE……

探索済みの局面を文字列で持たせてるから遅いのかなあ。
という訳でまた全面的に書き直し。今度は一桁入れ替える処理をバグなしで書けた。
Compile→Test
お、さっきのケースがきちんとanswer 4を返した！
もうちょっとテストしてみよう。

投げる→bad allocだと！？

なんぞこれｗｗｗｗｗメモリ超過っぽいｗｗｗｗｗ
ここにきて本質的に幅優先探索が間違っていたことに気づく。状態数は10!じゃなくて10^9じゃねーか！！何勘違いしてんの？ﾁｬﾝﾄｱﾀﾏﾂｶｯﾃﾝﾉ？

残り10分あるかないか。

閃いた、平方数を1,2,4,9,,,と生成していって、それとの相違を比較してけばいいんだ！！！！似たような問題解いたことあったし、実装も凄いシンプルじゃねーかorz
残り10分で書けるか！？

書いてやる。がりがり。

サンプル通らない。何故。あ、積がint超えてる。long long にキャストしておいて……
サンプル通った！！！！！！Submit.

残り3分。終了。

Challenge

Summaryを見る。なんだか自分は2問正答の最下層らしい。要するに↓には1問正答しか居ないのでFailしてもあんまり順位変動しない。
よし、平方数生成してなさそうなのにさっき自分のがMLEになったケースを投げてみよう。

投げた。普通に返されたorz

他に落とせそうなのもなし。チャレンジフェイズ終了。。。

Systemtest

Challengeセッション終了後に同じ部屋のイランの人からwisperが来る。

「君の250間違ってるよ」
すごい動揺。え、ていうかじゃああんた何で撃墜しなかったん？
「xxxxxxxxx（失念）のデータを投げると違う答えが返ってくるよ」
そーなのか。凹むorz
「でも俺が間違ってるかもしれない。システムテスト通るといいね」
お？いいやつじゃんこいつｗ英語よくわからないのでThank you!!って言っておいた。

ジャッジトラブルか何かでかなりテストが遅かった。
あれ？250通ってるじゃんｗｗｗｗまあよかったよかった。

Result

75.00/271.22/-/ チャレンジ1ミスで333位。
レーティングは50程上昇したようだ。

2問正答のほうの目標は何とか達成できたけど問題解くの遅すぎるなー。500だけしか解けてない人で自分より順位上の人がかなりいる。

頭悪すぎてだめだ。悔しい悔しい悔しい悔しい！！！！！！
思考の訓練でどうにかなるのか？とりあえずやれるところまではやるつもり。