とても久しぶりに参加。 div1:250 NotTwo 最大1000*1000の盤面に、ユークリッド距離が丁度2になるような石のペアが存在しないように可能な限り石を置いた時に最大でいくつ置けるか。 整数座標でユークリッド距離が丁度2になるのは上下左右に2マス離れた場合…

フィボナッチや階乗を計算させるような、一つの整数値が結果になるものは書いた事があったのですが、もっと複雑なものを書いてみたくなったので、チューリング完全性の証明もおまけでついてくるbrainfuckインタプリタを書いてみました。 #include <cstdio> /////////</cstdio>…

予定してませんでしたが。そして多分その2で終わりです。昨日学内の練習会でImos Judge(http://judge.imoz.jp/)を利用させて頂いて国内予選の復習をしていたのですが、そこで「Cの制限時間が厳しくて通らない」という話題で少し盛り上がっていました。 厳し…

模擬国内予選と国内予選の参加記も書くつもりですが、取り急ぎCのソースだけ！ Cは一見楽勝に見えてそのまま書き始めると実にかったるい（next_permutationを使ってしまったり）ですが、問題文を読み込めばDFSですっきり書けます。 #include <iostream> #include <set> #inc</set></iostream>…

Spaghetti Sourceの複数パターン検索 (Aho-Corasick)で紹介されているスライドを参考にして、書かれている疑似コードをほぼそのままC++で書き直してみたもの。Trieのvalues_フィールドが保持しているのは、そのノードに到達した時点でマッチしている単語の集…

KMP Algorithm - Search for Problemsに載っているのをちょこちょこ送信中。UVaは掲示板書き込みの英語率が高いのが良い。

長さ1000以下の単語が最大15000個与えられる。最大100*100の文字テーブルの中に出現する単語を全て数え上げよ。文字テーブルの読み方は、縦横斜めをそれぞれ双方向。Aho-Corasick、だけれど、細かい所で注意しないといけない微妙な問題。具体的には以下。 ci…

長さ100000以下の文字列sが与えられる。sの後ろにできるだけ少ない文字列を連結して回文にし、出力せよ。少し考えると、sをreverseした文字列をs_revとして s.substr(s.size() - N) == s_rev.substr(0, N) となるような最大のNを求めれば良い事が分かる（で…

いきなり回答編ですが。最近研究室の後ろに座ってる人がこれ（http://www.amazon.co.jp/%E3%83%8F%E3%83%8A%E3%83%A4%E3%83%9E-%E6%98%8E%E6%B2%BB%E3%83%9F%E3%83%AB%E3%82%AF%E3%83%81%E3%83%A7%E3%82%B3%E3%83%91%E3%82%BA%E3%83%AB/dp/B000BVN0AA）を持…

とても簡単に書くと、次のプログラムを実行してCtrl-Dを入力した際に -1 とだけ出力されて欲しかったのです。 #include <iostream> int main() { while (1) { int c = std::cin.get(); std::cout << c << std::endl; } } ところが実際にはこうなります。 -1 -1 -1 ...(</iostream>…

久しぶりのsrm、のはずだけど、今年からペースが落ちたので問題セット的には間は空いてない。 しかしまぁ緊張した。 div1:250 TheSwap 1 スワップを全通り試すと6C2 ^ 10になって当然終わらないけど、6桁の数字の並び替えはせいぜい6! = 720通りしかないので…

参加記の方書くの忘れてた。 本番は250で8! * 160 * 160を書いてしまって撃墜され、500でad-hocをやって撃墜されてしまって0点。うぐぐ。難し目のセットだったようであまり下がらなかった。 div1:250 MagicWords T(i) = T(0)となるiがK個存在するT(0)はK個の…