cafelier@SRM

TCO10 R2

SRM | 11:09 |

TCO10 R2 の成績・ソース (要ログイン) : AC/AC/- : さいきん書くのが億劫になってきてしまった…

500開く

• 『十進表記で全部の桁が奇数の数をtotally oddという。入力された自然数X以上の数で、totally oddな数二つの和で表される最小の数を求めよ』
  • 1≦X≦10^8

• テストケース作成
  • 最小X=1は…サンプルにあるか。
    • とりあえずX=1～10くらい手で全部作っておこう
    • って、totally odd な数は当然奇数なので、和は偶数しかない
    • 1,3,5,7,9 はダメ、逆に小さい偶数は全部作れるのか
  • 最大ケースは、えーと X は10^9だな。(※間違い)

• そもそもtotally oddの数で書けない偶数ってどんな数だろか
  • 2,4,6,8,... 順に試してみる。
  • 20! 20は？ あ、19+1 とかでできる。
  • 40だ！いや39+1ではないか。
  • これは3桁以上行かないと無理だなあ
• とりあえず馬鹿探索でパターンを見てみることに
• よくわからないけど20の倍数っぽいとこでダメになりやすい雰囲気のパターン
• でもよくわからない

• さて、どうしよう…
• X がデカいから、当然全探索みたいなのは無理なんだろうなあ
• うーむ
  • Xを上の桁からチェックして行って、totally oddで作れなそうだったらその桁をインクリメント、みたいな感じでlog X程度で最小の解が…
  • むむむ難しい

• 見当がつかないので
• とりあえず簡単なルーチンから考えてみよう
• 書いているうちに頭が整理されるかも

• つまり、与えられた数がtotally oddの和で書けるかどうかの判定ルーチンを書いてみる
  • なんかもう、for(;;++X) if(ok(X)) return X; で間に合うんじゃないか
  • 小さいゾーンを見た限りでは、書けない偶数はそんなに多くないから、意外と早く終わるはず
  • しかし自信ないなあ…

• totally odd の和で書けるかは、Xを上の桁から見ていくことでチェックする
  • 簡単のために、同じ桁数の和で書けるかのチェックを考える
  • Xの最上位桁が偶数なら、書ける。
    • たとえば4...なら、1... と 3... の和で書けるから
  • Xの最上位桁が奇数なら、下からの繰り上がりがあれば書ける
    • たとえば7...なら、1... と 5... と繰り上がりの1の和で書けるから
  • と思いきや、奇数 1 は繰り上がりをもってしても書けない
    • 0... + 0... + 繰り上がり、は許されないので
  • でも上からの繰り上がり要求がきてれば 11 は 1... + 9... + 1 で書けるよ
• というのを再帰で。
• 最初の方の桁はleading zeroが許されるので、「leading zero続行中」というフラグを用意して管理
• boolフラグ2個もって9桁くらいあるから4^9回くらいの関数呼び出しになったりする？
  • これだと何回も回すときついからメモ化しておこう。4*9で終わる。

• できた
• サンプルと答え合わない
• なんかleading zeroの扱いがおかしいっぽい
• 直った

• サンプルは通るなあ
• 時間も問題ない、と思いきや最大ケース1000000000はそれ自身totally odd和で書けちゃうのか
• それは最悪ケースではない
• えーと、あ、このサンプルは結構ジャンプ幅長いのだな。4201234→422222
  • これ42012345だと10倍ジャンプ幅長くなったり…
• した
• 手元で0.6秒かかる
• うげ、これさらに10倍すると…うぎゃー7秒。

• やっぱり for(;;++X) if(ok(X)) return X; はダメなのかー
• しかし7秒程度ならうっかりサーバでなら2秒で通ったりしないかな
• やってみよう
• 「100000000以下の値しか入れちゃダメです」って怒られた
• あれ？
• おお、10^9 ではなく 10^8 が上限か！
• じゃあ間に合うんじゃないか？
  • しかしサンプルのが最悪ケースかどうか…
  • いいや出しちゃえ！

• そして 1 から 1億まで回して最悪ケース探すルーチンを書く
• これ回しながら250解こう
  • (※ 結果、サンプルにあるケースがほぼ最悪のようでした。よかったよかった)

250開く

• スコアボード見ると結構ばらけてる
• 『N点が道路で結ばれてる道路網があります。各道路には車線が複数あるかもしれませんが、上りと下りの車線数は同じです。点0からスタートして全部の車線を１回以上通る（複数回通ってもいい）最小のルートの長さはいくつ？』
  • N≦50
  • 0から行けない道路があったら -1

• 一筆書き…？
• でも辺に向きがあるし太さもあるしよくわからんなあ…

• 250だからなにか閃けばトンチ一発で綺麗に解けるのか…

• わからない…
• うーむ、この問題設定だと常に一筆書き可能なんじゃないかなあ。
• そろそろsubmitしないとどのみち350位が危ういし、そういうことにしてしまおう。

• 書いた
• グラフが連結ならエッジコストの総和、そうでなければ-1を返す
  • 連結性はWarshall-Floydで適当に
• サンプルと合わない
• おお、道路が一本も繋がってない頂点は-1とは限らないのか
• サンプル親切だなー
• 幅優先で道路を辿って辿った道路を消していって残ったのがあったら-1、に変更
• できた
• 正しさにまったく自信がないけど出しちゃえ

1000開く

• 時間ないし、250の正しさを確認した方が良さそうだけど、一応楽しみのために1000を読んでおこう
• 『10億×10億くらいの２次元タイルに、40個くらい色つきのタイルがあります。１つのブロックに縦カットもしくは横カットを入れて切り離す、を繰り返して何個かのブロックに分けて、最終的に色つきタイルは色つきonlyブロックに乗るようにするには何回のカットが必要ですか』

• とりあえず切る可能性のある座標は40個…いや、両側あるから80個か。
• えーとこっちを先に切るとあっちが２回切る必要ができたり逆になったり…
• わからんあきらめよう

• あとは、250が0をルートにツリー状に道路を並べて、深さ優先でリーフから何往復もして車線を辿り尽くしておくようなルートで辿ればよいことを証明などしていました。

撃墜タイム

• 500がみんな賢すぎて愕然とした
  • 考える必要のある totally odd な数は 5^8 しかないので、
  • 片方全探索して、もう片方をXに近づけるよう二分探索、で 5^8 log(5^8) でいいらしい
  • あるいは尺取りメソッドで 5^8 で終わるらしい

感想

• 私が苦戦するのは単に実力不足なのでいいとして、
• 今回の 500 が多数の上位コーダーを苦しめているのは面白い現象だなーと思いました。
• どこが秘孔をついたのだろうか。分析すると面白い気がする。