この必要条件が満たされる場合、「文字列の先頭部からiとなる部分文字列が取れ、かつ、文字列の末尾部からkとなる文字列が取れる」ならば、残りの真ん中の部分は必ずjとなる、と分かる。問題は、文字列の先頭部と末尾部を何文字分見ればいいかということ。クオータニオンは16個の状態しか持たないので、なんとなくL*16個分見れば十分な気がしたけど、正当化できていません。ハマったのが、文字列の末尾部を順番に見ていく部分。交換則が成り立たないことを忘れていました。引数の異なるinitializerを二つ持てないらしく、対策に難儀しました。endendmain()以下はC#。Largeファイルダウンロード後に、int型では足りないことに気付いて、提出はぎりぎりでした。OminoX個のブロックからなるX-ominoの集合がある。Gabrielは、指定盤面R*Cを、任意のX-ominoで敷き詰められば勝ち。敷き詰めなければRichardの勝ち。Gabrielは、Richardが選んだX-ominoを必ず使わなければならない。丁寧に場合分け...だと思う。Largeを落としたので後で復習。常套手段として、常にR<=CとなるようにRとCをswapしておくと便利。以下はCで書いたSmallを通過するコード。0;}(追記)Largeのバグを修正したPerlのコードです。短辺=3のときにバグがありました。このときは長辺が8以上のときに盤を埋めるチャンスがあります。8ならチャンスがある。予選Aに参加しました。自分は47位で、なんとか予選突破圏内でした(社会人なので資格がありませんが)。自分が経験する初めてのタイプのコンテストで新鮮だったので、簡単にメモしておきます。問題AからDからなる50文字の文字列を作って高得点を目指す戦略ランダムな長さ50の文字列をたくさん作って投げる点数の高かった上位n件について、長さ8の部分文字列を抽出して点数を調べる長さ8の文字列のうち点数の高い上位m件から、ランダムに6つ選び、ランダムな2文字をランダムに挿入して50文字の文字列を生成。文字列と点数の組を辞書として持ち、適宜pickleで保存。|Round1AはA-smallしか解けず2471位で敗退。本番ではSmallを優先して解く戦略を取った。A-smallをブルートフォースで解き、B-smallに集中するも、手も足も出ずそのまま時間切れ。AとBを両方解いても解答時間によっては敗退してしまうような難易度では勝ち目はまったくなかったと言える。LayCurseさんのとても教育的な解説を読んで復習した。以下のコードは、Aを除いて、LayCurseさんのコードをほぼ丸々下敷きにしている。Chaosコンセントと電化製品とのマッチングについて、ビットで制限を加えつつ総当り的なことをしないといけないと勘違いをしていた。実際は、ある一つの組み合わせさえ決めればよいのであった。これは本番中に気づかなければいけない問題だった。Treeループしていることも考慮すると大変だぞ、と思いあれこれ考えるが、よく問題文を読むと、エッジの数はノードの数-1なのでループはありえないのであった。グラフに関する問題だというだけで必要以上に身構えてしまう悪い傾向がある。LayCurseさんの解説コードではdpの要素は使っていなかったようなので、以下のコードではdpテーブルは省いてある。再帰関数にて親側のノードを誤って数えないようにする工夫が勉強になった。befは、i番目のノードの親。ShuffleBAD法で生成したランダム配列はGOOD法で生成したランダム配列に比べて悪い癖があるはずで、それをシミュレーションによって明らかにすればよかった。|2013年のまとめ2013年の年初に立てたTopCoderの目標はまずまず達成できた。2回に1回くらいは復習する→未達成Div1にいる時間の方がDiv2にいる時間よりも長くなるように→達成。9割以上の時間Div1に留まれたあわよくば黄色に一瞬だけだが達成。Max15672012年末のレート1189から、2013年末には1496まで上昇。Easyを、速度はともかく高確率で正解できたことが大きかった。GCJはRound1で敗退。復習もしていない...CodeforcesはDiv1とDiv2を行ったり来たりでDiv1に定着できず。Codeforces。