スピードテストの途中でキーの押し間違いがある ＝ ⼊⼒値 A と問題⽂ T は異なる⽂字列 • 求める答え • ⼊⼒した⽂字列 A から何⽂字削除すれば正しい回答 T になるか ＝ ⼊⼒値 A を T にするためには何⽂字削除すればよいか • T にならないときは IMPOSSIBLE どの⽂字が押し間違いか、 どの⽂字を修正すればいいか、は聞かれていない！
T の⻑さを調べる A の中に T の 1⽂字⽬がいくつ 含まれているか 数える IMPOSSIBLE と出⼒（回答） T の⻑さと同じか それより多い T の⻑さより少ない 次はこれをプログラムに落とし込みたい ・A を T にするためには 何⽂字削除すればよいか を出⼒する ・T にならないときは IMPOSSIBLE と出⼒する
c の数を n とし、 a = 1⽂字⽬、n = 0⽂字とする A の a 番⽬の⽂字と c を⽐べる a と A の⻑さを⽐べる T の1⽂字⽬を c とする n を +1 する a > A の⻑さ 同じ⽂字 違う⽂字 a を +1 する IMPOSSIBLE と出⼒（回答） n と T の⻑さを⽐べる A の⻑さ – T の⻑さ を出⼒（回答） n ≧ T の⻑さ n < T の⻑さ A を調べきった まだ調べていない⽂字がある T の⻑さと同じか それより多い c がある プログラムっぽく：問題⽂ T に同じ⽂字しか含まれていないとき ・A を T にするためには 何⽂字削除すればよいか を出⼒する ・T にならないときは IMPOSSIBLE と出⼒する
から⽂字を削除して T になるのはどんなとき？ • 何⽂字削除すればいい？ を考えないといけない。 少なくとも A の⻑さが T の⻑さと同じか それ以上ないといけない T の⽂字が A の中に すべて含まれて いないといけない T の⽂字が順番通りに A の中にすべて含まれて いないといけない それだけでなく もっと⾔えば 【⽅針】 T と A をそれぞれ先頭から順に１⽂字ずつ調べ、 T を構成する⽂字がすべて A の中に含まれているかを確認する
難しいケース：問題⽂ T にさまざまな⽂字が含まれているとき T の何⽂字⽬を調べているかを t 、 A の何⽂字⽬を調べているかを a とし、 t = a = 1⽂字⽬とする T の t 番⽬の⽂字と A の a 番⽬の⽂字を⽐べる t と T の⻑さを⽐べる t を +1、a も +1 する （T と A を次の⽂字に進める） A の⻑さ – T の⻑さ を出⼒（回答） t ≦ T の⻑さ t > T の⻑さ 同じ⽂字 T を調べきった まだ調べていない⽂字がある
A の⻑さを⽐べる a を +1 する （A だけ次の⽂字に進める） t を +1、a も +1 する （T と A を次の⽂字に進める） a > A の⻑さ IMPOSSIBLE と出⼒（回答） A の⻑さ – T の⻑さ を出⼒（回答） a ≦ A の⻑さ t ≦ T の⻑さ 同じ⽂字 違う⽂字 まだ調べていない⽂字がある A を調べきった t と T の⻑さを⽐べる まだ調べていない⽂字がある 難しいケース：問題⽂ T にさまざまな⽂字が含まれているとき t > T の⻑さ T を調べきった T の何⽂字⽬を調べているかを t 、 A の何⽂字⽬を調べているかを a とし、 t = a = 1⽂字⽬とする ・A を T にするためには 何⽂字削除すればよいか を出⼒する ・T にならないときは IMPOSSIBLE と出⼒する
≦ パンケーキの枚数 ひっくり返した回数を c で表す c = 0（0回）から始める 端から x 枚⽬のパンケーキが 表か裏か調べる x + N - 1 とパンケーキの枚数を⽐べる 端から何枚⽬のパンケーキに 注⽬しているかを x で表す x = 1（端から1枚⽬）から始める x 枚⽬からN枚のパンケーキを ひっくり返して c を +1 する x + N - 1 > パンケーキの枚数 Blank side Happy side x を +1 する c（ひっくり返した回数） を出⼒（回答） すべてのパンケーキを 調べきった まだ調べていない パンケーキがある Nとパンキーキの枚数を⽐べる N ≦ パンケーキの枚数 N > パンケーキの枚数 IMPOSSIBLE と出⼒（回答） Blank side のパンケーキがある Blank side のパンケーキはない ・何回ひっくり返せばすべての パンケーキが Happy side を 向くかを出⼒する ・すべて Happy side にできない ときは IMPOSSIBLE と出⼒する x を含めて N枚返せるコテを 使うので、⼀度に返せるのは x（+ 0）枚⽬、x + 1枚⽬、 x + 2枚⽬、… x + N - 1枚⽬のN枚。 このとき終端にある x + N - 1 が パンケーキの枚数を 超えてはいけない 2ページ前の N=1 のケースと どこが変わっているか ⾒⽐べてみてください このフローは N=1 のときも 動くので、N=1 を代⼊すると 2ページ前と同じ フローになるはず… x 枚⽬以降のパンケーキ ＝「残りのパンケーキ」
side 第２問の「端から1枚ずつ順番に⾒ていく」を思い出す ・この問題における「端」とは ⼀番上のパンケーキのこと ・⼀番下ではダメなのか それより上に載っているパンケーキが すべてひっくり返す対象になってしまうので コントロールしづらい どうやって揃えるか 【⽅針】 上から順に⾒ていき、⾯（向き）が変わるところで それより上のパンケーキをひっくり返す ⇒ これによりパンケーキの⾯（向き）が揃う Blank side Blank side Blank side Happy side Blank side Happy side Happy side Happy side Happy side Blank side Blank side Blank side Blank side Blank side Blank side ② ③ ④ ⑤ ① Happy side Happy side Happy side Happy side Happy side
Oversized Pancake Flipper（Code Jam 2017 QR） • 第３問： Revenge of the Pancakes（Code Jam 2016 QR） • Code Jam には Infinite House of Pancakes シリーズ（勝⼿にこう 呼んでる）の作品(?)たちがこんなにも • Infinite House of Pancakes（Code Jam 2015 QR） • Revenge of the Pancakes（Code Jam 2016 QR） • Oversized Pancake Flipper（Code Jam 2017 QR） • Ample Syrup（Code Jam 2017 Round 1C） • Waffle Choppers（Code Jam 2018 Round 1A） • Pancake Pyramid（Code Jam 2019 Round 3） • Oversized Pancake Choppers（Code Jam 2020 Round 1C） • Pancake Deque（Code Jam 2022 Round 1B）
tamacjp
gr2m
techseoconnect
soudai
mfonobong
mraible
uxyall
inesmontani
michielstock
sstephenson
bethany
trishagee
rkendrick25
