SRM : challengeのコツについて思うところ

黄色になった記念に。

 

はじめに

最近 SRM で撃墜するコツを掴んできたような気がするので、「challenge とか何すればいいのか分かんねぇ…」って人向けに考えてることを書き連ねてみます。

 

意外と簡単で重要な challenge

SRM 始めたての頃の僕は、「challenge とかよく分かんないし、たかが 50 点でしょ? Div1 は easy 解けるかも怪しいし、人のコード読めないし別にいいや…」と思ってました。

ですが驚くべきことに、問題が解けなくても、人のコードをしっかり読めなくても、意外と撃墜できちゃうものです。

f:id:iwashi31:20150724114116p:plain

また、50 点を侮ってはいけません。

0 完!やってしまった!なんてときに、0 点と 50 点ではレーティングの変動もだいぶ変わってきます。

Div1 で easy を解いて 2 撃墜に成功した日には、赤い人たちと肩を並べることだって夢ではありません。

f:id:iwashi31:20150724120312p:plain

こんな素敵な challenge 、挑戦しない道理はない!

 

以下、2015/7/24の SRM663Div1 に参加した際のことを例に順を追って書いていくので、ネタバレやだ!って方は easy(≒Div2med) を解いた後読むことをおすすめします。

 

1.Coding Phase が始まる前

部屋に入って配点を確認。「300-550-1000」。

配点がいつもより高いし challenge 狙えそうだなぁとぼんやり思う。

 

2.Coding Phase 前半

問題を把握しないことには撃墜も何もないので、まずは問題を解きにかかりましょう。

SRM663Div1easy では次のような問題が出題されました。

 

  • 'A' と 'B' のみから成る2つの文字列 initial, target が与えられる。
  • 次の2つの操作を文字列 initial に適当な順で行うことで、文字列 target へと変えることができるか否かを答えよ。
  • 操作1「文字列の最後に 'A' を付け加える」
  • 操作2「文字列の最後に 'B' を付け加えた後、その文字列を反転する」
  • 1 ≦ initial の長さ < target の長さ ≦ 50

例:initial = "A", target = "BABA" → "Possible"

  "A" -(操作2)-> "BA" -(操作2)-> "BAB" -(操作1)-> "BABA"

 

target に逆の操作をして initial に変えられるかの方が楽そうだなぁという考えをもとに、何となく通りそうなアルゴリズムを思いつきました。

配点高めということで警戒しながらアルゴリズムに穴が無いかを確かめます。どうやら大丈夫そうなのでこれで提出。

今回は特にありませんでしたが、ここで何かしらの穴が見つかった場合は、challenge の手がかりとなるので覚えておきます。

 

この時点で 30 分経過、med は捨てて残りの 45 分は easy で撃墜するための作戦を立てていきます。

 

3.Coding Phase 後半 ~ Intermission

Challenge Phase に入ってただぼんやりと他人のコードを眺めるだけでは、バグを見つけるのは非常に困難です。

そこで、余った時間を用いて想定される穴や嘘解法を考え、それらを撃墜できるテストケースを準備しておきましょう。

先ほど考えた方法には穴は無さそうだったので、別の解法を考えます。

 

以下、今回の僕の思考です。

(target を削って initial にする方法だと穴は無さそうだったな)

(別の解法を考えよう)

(素直に initial から target を作ろうとする人は少なからずいそうだ)

(initial から target を作ろうとすれば…まずは target の中に initial(or反転したinitial) が含まれてるかをチェックする必要があるな)

f:id:iwashi31:20150724132128p:plain

(この target の赤い部分に黒い部分をくっつけていくんだよな)

(となると…B を後ろにくっつけるたび反転するから、赤字の前後にある黒い部分の文字列が含む B の個数は同じ(赤字が反転した initial なら手前の方が 1 個多い)でなければいけないはずだ)

f:id:iwashi31:20150724132536p:plain

(B をくっつけていく最中に A はうまいこと挟めるから、 A のことは気にしなくて良さそうな気がしてくる)(※)

→ target の中から initial(or反転したinitial) を見つけて、その前後の B の数を数えて比較することで判定ができそうだ!と考える人がいそうだ!

 

(※)の部分が間違っているのでこのアルゴリズムではダメなんですが、どうやらサンプルケースのみならこれで正答することができそうです

サンプルケースが通るそれっぽい嘘解法なら誰かが使ってしまっているはず、ということでこれを撃墜できるテストケースを考えます。

f:id:iwashi31:20150724135241p:plain

はい、できました。

これなら本当は "Impossible" なんですが、上の嘘解法では赤字前後の文字列が含む B の個数が等しい(ともに0)なので "Possible" と返します。

他に穴やら嘘解法やらを思いつかないので、今回はこのテストケース 1 つを武器に Challenge Phase へと赴くことにしましょう。

 

4.Challenge Phase 前半

Challenge Phase 前半は Coding Phase 以上にスピード勝負です。

そのため、準備したテストケースが今見ているコードに通用するかどうかを素早く判断しなければなりません。

難しそうに聞こえますが、この判断はコードの一部だけを見てさっと行えることが結構あります

 

例えば、開いたコードが次のようなものだったとしましょう。

f:id:iwashi31:20150724142945p:plain

このコードには先ほど準備したテストケースは通用しなさそうということが瞬時に分かります

なぜなら、文字列のどこかしらが 'A' だった場合に何らかの処理をしていることが伺えるからです。

先ほど想定した嘘解法は 'A' は気にしなくて良さそうというものでした。

なので、if (... == 'A') なんてものが目に入った時点で通用しないと判断して、別のコードに移っちゃいましょう。

また、すぐには判断できそうにない難解なコードに出くわした際も、さっさと読みやすいコードに移るのが吉だと思います。そんなコードはどうせ他の人にもすぐには読めないですから。

 

逆に、このコードはどうでしょうか。

f:id:iwashi31:20150724144917p:plain

for 文が何のどこからどこまでを回しているのかなどはパッと見では分かりません。

ですが、条件式や変数名などから「before や after の b を数えているっぽいこと」、また下部の return 文からは「その数えた値を比較した結果を返していること」がすぐに汲み取れます。

これ、とっても想定していた嘘解法っぽいですよね。

ここまでそれらしいならまぁ間違いないだろう、ということで用意したテストケースをささっと入力し challenge!

 

こんな調子で、今回はテストケース 1 つを武器に 2 撃墜 100pts を稼ぐことができました。

 

5.Challenge Phase 後半

じっくりバグを探すスキルはないので、優雅につよい人のコードを鑑賞します。

 

まとめ

Challenge Phase の前半は他人のコードを「何かバグあるかなー」と眺める時間ではありません。「このバグはあるかなー」と流し見していく時間です。

また、流し見しつつ判断する際も、このポイントだけ見れば割と瞬時に判断可!という部分が少なからずあります。そのあたりについても Coding Phase の余った時間を使って考えておいてもいいかもしれませんね。

それでは、良い撃墜ライフを!