cafelier@SRM

SRM434 Div1

SRM | 03:53 |

SRM434 の成績・ソース (要ログイン) : WA/AC/- : 順調にレートが下へ参ります

500 開く

• 250はDivision Summaryの情報から瞬殺問題かどうかの心構えを得て挑む方が楽だろう、と判断して今度から最初はLevel 2問題を開くことにしました

• 『36進数の数n個が与えられる。0-9A-Z のうち k 種類選んでZに置き換えたときの総和の最大値は』

• 36Ck 全探索は…36C18 を計算してみると大きすぎるな。無理。

• もっと賢い方法を考えよう。えーと
  • 0をZに変えたときに増える量
  • 1をZに変えたときに増える量
  • ...
  • の大きい方k個を取ってきて元々の総和に足すだけ

• まあ36進数の比較と加算の実装がめんどい
  • 最大50桁らしいので60桁の固定長で実装
  • 比較はvectorの比較演算子で済むような桁順で格納
  • 足し算は頑張る

• 固定長にしたときに0をZで置き換えるときにLeading Zeroまで全部Zに置き換えてて一瞬誤答がでたけど
• できた。通った。はい次

250 開く

• 瞬殺してる人もいるけどそんなに多くない。たぶん簡単だけど実装微妙に手間かかる系？
• 『N×M の盤面に数字が入ってるので等間隔に拾って繋げて作れる平方数のうち最大なものを返せ』

• 9×9が最大らしいので、始点9×9通り、方向17×17通り全部試せば余裕
• 実装した
  • for(y in [0,9])for(x in [0,9])for(dy in [-8,+8])for(dx in [-8,+8])for(k in [0,...])
  • dy==dx==0 のとき無限ループなさっておられる
  • そりゃそうだ。
  • for(y in [0,9])for(x in [0,9])for(dy in [-8,+8])for(dx in [-8,+8])if(dx|dy)for(k in [0,...])

• サンプル通った。submit

• ところで、撃墜フェーズ始まった瞬間に気づいたけど、
• 1×1 の入力 ("1" とか) 来たときにimpossibleと判定しますねこれだと！
  • 1×1でなければ1歩で外に飛び出す方向ベクトルを試すときに1文字パターンは判定できているはず
• 死亡

1000開く

• 『[0-9,\?]*な入力文字列がくるので、?を[0-9,]に置き換えてコンマ区切り昇順正整列になるようにしてください』
  • 複数可能性がある場合は辞書順最小のもの

• なんかDPかな－。昇順列になるように?を埋める探索をメモ化してみるとどうだろう。
  • 直前のコンマの前の数値 × 今読んでる数値 × index
  • どのぐらいの場合の数あるかわからない
  • まあ組んでみるか。
  • 組んでみた。
  • 遅すぎる。

• わからないー

• うーむ

• えーと

• 先にコンマの位置だけ決められないかな
  • さっきの探索でコンマの位置だけみるバージョンを書いてみる
  • 数値じゃなくてその桁数を見ればいいので、そんなにパターン数無い。メモ化とか考えず普通に再帰探索で全列挙できるはず
• 組んでみた
  • できた。
  • 動いた。"?"*50 とかでも、桁数が広義昇順になるコンマの入れ方は数万通りしかないらしい。

• これで、可能なコンマの入れ方それぞれについてO(N)くらいで数字埋める判定できれば勝ちじゃない？
  • 埋め判定は、桁数同じグループ毎に分解してできる
  • 気合いでどうにかなりそうな…

• しかし時間切れ

チャレンジフェーズ

• 1000点問題を994とかで出してる人がいたののブラインド撃墜レースに挑むもタッチの差（かどうか知らないけど）で間に合わず
• 250点問題で、盤面の端っこまでいかずに止まるパターン考えてない人いそうだなー、と思ってそういうコードがないかチェック
  • あった！
  • と思ってチャレンジしたら失敗。僕の目が悪かっただけでした。

感想

• コーナーケースをトリッキーにカバーしてるつもりになってる場合は、本当にカバーできてるかものすごく真剣にチェックしましょう。
• ていうかコーナーケースは常にテストしましょう。
• 何回目だ俺…

• あと、250/500に時間取られてない今回みたいな時は、もーちょい1000点の解の糸口くらいは見つけたいなあ