TCO 2018 Algorithm India Round

nico_shindannin（診断人） @nico_shindannin

いちおう３完じゃ。 Easy : たてよこ、範囲外ならぬようチェックしよう。 Medium : 偶数行のx座標だけ反転させればよい。Aを1引けばコケずらい Hard : すべての文字からすべての文字に5手で行けるっぽいので、50文字*(5手+入力の1手)=300手でおさまる。総当たりでもbfsでもdfsでも。

nmnmnmnmnmnmnm @enuemuenuemuenu

あれ？1行足しても通らないぞ。全探索したのに謎が。

きゅうり @kyuridenamida

Easy. reverse() and reverse() Medium: f(R, C, step) -> (x,y) を書く Hard: 26箇所について0番目に持ってくる方法をdpで求めておいて後はシミュレーション(復元がだるいので文字列そのもので持つと楽)。再帰関数の文字列結合順が逆になっててクソハマった。悲しい。

Dark Yoshi @dark_yoshi_math

競プロエンジョイ勢になろう。

nico_shindannin（診断人） @nico_shindannin

39人しか参加してなかったから、2つ順位落ちるの意外とでかかったかも…無理なチャレンジしなくてよかったか

nico_shindannin（診断人） @nico_shindannin

@dark_yoshi_cpp テストケースに反例が入っておらず、ちょっと不運なかんじでしたね。どんまいじゃ。

Dark Yoshi @dark_yoshi_math

@nico_shindannin 💪

M @601________

@kyuridenamida これって、26か所について0番目に最短で持ってくる方法だけで構成された方法より、速く作る方法はないのでしょうか？どうやって規定回数以内になることを見出しましたか。

きゅうり @kyuridenamida

@601________ 実際それより短い作り方はあると思います。ただそれはすごく難しそうなので問題を緩和しました。1文字ずつ独立に問題を解くという問題でも、多分高々一回あたりceil(log 26)=5くらいなんじゃないかと祈って実験したら高々5回だったのでラッキーみたいな感じでしたね。

M @601________

@kyuridenamida 直感をもとに実験されたんですね。お返事ありがとうございます。

Dark Yoshi @dark_yoshi_math

今日のSRMの全Failedから立ち直るには軽い睡眠が必要らしい。（明日06:00AMの新幹線に間に合うのか…）