20:52最初bit-dpかと思って苦労した。実際は20の分割数があまり大きくないことをつかうパターン。その意味で、TCO11WildCardのHardと似ている。http://topcoder.g.hatena.ne.jp/hirosegolf/20120612#1339488542。実行時間は適当に組んでも最悪ケースで100m程でかなり余裕がある。19:11まず、最初に16以下の素数で割りまくる。この過程で既に計算量が2500^2を超えるので、定数倍に気をつけて実装しなくてはいけない問題だと気づく。この手の問題は16以下の素数にどんなものが存在するかきちんと調べることが必要。最悪ケースのテストを作りにくいので、定数倍に細心の注意を払いながら実装する。11:14各マスを中心に両側探索を行う。最悪計算量の見積もりが難しい。441*3^10なので時間的に結構ぎりぎり。このようなタイプの問題だと、最悪のケースをテストしながら高速化していくのが定石だと思っているが、最悪ケースを作るのが難しいのでとてもやっかい。12:19単に合計を最大にするだけなら、普通に貪欲法を使えばいいが、R*Bを最大化したいので工夫が必要。正の数x,yに対して、x*R+y*Bを最大化すれば、(x,y)の値によってはR*Bが最大となるようなR,Bが得られる。(x,y)の組み合わせを全て確かめるのは不可能だが、実際には(x,y)によって選択肢が分かれるような境界でだけ調べればいいので、実際に調べる必要(x,y)の組は高々50^2だけ。これ以外の問題でもR*R+B*Bを最大化したい場合とか、考え方自体は応用が広そう。11:42母関数を使って紙の上で計算すれば、計算量は相当落ちる。やってみないと解けるかどうか分からない感じの問題。pでp乗したときの振る舞いを知っていれば難しくない。本番ではバグを出して再提出になってしまった。11:25有向グラフ上で元の場所に戻る一筆書きを行うためには各頂点の入次数と出次数が等しくなくてはいけない(あと連結性)。各頂点の入次数と出次数が等しくなるように辺を取り除く行為は、出次数が多い頂点から入次数が多い頂点へフローを流す行為と対応することが分かる。最小費用流を用いれば答えが得られる。11:11本番とおした人のコードを参考に書いた。貪欲的な方法で解ける。『まずフィールド全体を爆弾で埋める。問題文からフィールドは木構造になっているので、葉のほうから順に取り除き可能な爆弾を取り除いていく。言葉で適当にいうとたったこれだけの解法。シンプルかつ実装が簡単で一般性もある、かなり強力な解法だと思う。Editorial見る限り模範解答はdpでこの解法じゃなかったのが少し驚き。11:02考え方自体はさほど難しいものではないけど、複数の要素が絡んでいて実装に苦労する。10:52時間が2ステップ進む時の様子をみると繰り返し二乗法が使えることが分かる。アイデアが殆ど全ての問題。5倍していくイメージの解法の誘惑が結構強くて正しい解法にたどり着くのに時間がかかってしまう。10:40行列冪乗タイプの問題。違う方向を向いているFoxも同等に扱えるのが実装を簡潔にする最大のポイント。次のような式をノートに書くと分かりやすいかなと思った。書くと順に0,1,2,3が入るらしい。17:09置換の状態数は分割数に一致するが、35番目の分割数が意外と小さく(20000程度)、愚直なdpでも何とかなる事に気付けるかどうかがポイント。計算を工夫しないとTLEしてしまう。このような計算量を把握しにくい解法で解く時は、普段の「要求される計算量→解法を考える」から、「計算速度をとにかく早くする」に発想を切り替えたほうがいい気がしている。この種の問題、あんまり見ないから練習が難しい。03:22複雑な感じのdp。ややこしくて、難しそうなので放置していたのを解いた。この手の問題を解く時に自分なりにポイントだと思ったこと頭の中で細部まで無理に詰めようとしない。何となく方針が出来たら、思い切ってとりあえずコーディングを始めた方がうまくいったりする。変数の意味をコメントで書く。変数名を長くしすぎない。一変数化してメモする。longにまとめるとか。変数の個数をけちらずに書く。globalに置く変数の個数を出来るだけ減らすように書いたほうが簡潔になりやすい。『使った個数』ではなく『残りの個数』を割り当てるなど。出来るだけ脳内処理をせずに、定義に忠実に書く。x==2)としてしまうバグに嵌ったので、勝手な脳内処理を出来るだけしないことが反省点。b:直前が黒かどうか。ContestAtCoder最新日記一覧yuyarinのtopcoder記れんしゅうちょう。Memo@kagamizIH19980412の日記hama_DU@TopCoderへの道kenの日記@競技プログラミングwrendの日記どせいふんとうき。kmatsjonathanasdfの日記naoya_t@topcodernullnull7の。