ARC109：リアルタイム参加
■A - Hands
O(1)でできそうだけど
面倒なので何も考えずにダイクストラ
■B - log
二部探索
これでも多分O(1)でできる。
■C - Large RPS Tournament
テンパって事故った。
そもそも初見時に問題文読み間違えてるし。
結局無駄に面倒なことして時間を消費
あとじゃんけんの勝ち負けの処理ぐらいはテンプレもっといたほうが楽。
◆結果
Cまで
◆感想
前回のARCよりかはマシだけどこれも大事故
Dが解けないことではなく
Cに時間を溶かしすぎなのが大反省。
来週のARCもがんばります。。。
以下コンテスト外にやったもの
■D - く
向きを変更してからゴールまで持ってけばいいんじゃ？とか思ったけど
実装が面倒＋あってる気がしないので諦め。
コンテスト終了後解説をチラ見してみる。
実験エスパー？っぽことが書いていたので
BFSして実験エスパーしてみる。
実験エスパーして、それが帰納法で成り立つっぽいことを確認して実装。
実験コード書くのもまあまあ時間かかったので
やっぱりCで時間かかってる時点でダメダメ。
■E - 1D Reversi Builder
twitterで流れてた解説をチラ見した限り割となんとかなりそうじゃ？
と思ったのでトライ。
とりあえずマスの黒白を入れ替えると結果がほとんど入れ替わるので
基本的にはN/2になることがわかる。
結果が変わるのは
(BBBBBB)(W.........B)(WWWWWWW)
みたいな中間ゾーンの超ど真ん中にsがあるときのみ。
なので長さが(2 * i + 1)なる2 ^ (2 * i - 1)通りだけ
差分がでるので
N/2 + 1/2^N*Σ2 ^ (2 * i - 1)*(2 * i + 1)を計算する
◆感想２
実験エスパーという手法を学んだ。
でも結局実験コードを実装する時間が必要なので
実装スピードを頑張らないと！
