（｀ェ´）ぴゃ〜 Div1に残りたいororogの日記 http://d.hatena.ne.jp/ororog/

卒論に書いた文章より日記＋PKUのほうが長いんじゃないか疑惑…

概要 ホーン節とは，(n1&n2&... => p) という形をした論理式．(niもpも否定がつかない) ホーン節の論理積が与えられ，それを充足するような真理値割り当てを求める． 式の長さは，20000文字以内． 解法 構文解析をして，ホーン節の集合を求める． 右辺に変数…

概要 5x5のフィールドが与えられて，7つの連続するマスを選ぶ． マスにはHかJが書いてあって，7こ選んだとき，Jの方が多くなる選び方は何とおりあるか． 解法 まず，ダメだった解法は，25C7 = 480700 なので，全部生成して，それが条件を満たしているか，Uni…

概要 1 乳搾りをすると病原菌が混ざり合うが，Kまでは混ざってもOK． 最大何匹までokか？ 解法 DこのうちK個，混ざってもいい病原体を選んで，全部チェック． bit combinationの列挙が役に立った． // bit combination // comb(N, K) int N, K; for(int comb…

解法 変数がN a op b = c 1 と言う式が1000000個与えられる． これらの式を充足出来るか答える． 解法 2-satになる．

概要 n この数列は，1〜nの順列になっている． この数列を，任意の場所との交換だけでソートする． 最低何回交換操作をしないといけないか． 解法 順列になっているので，ある数字がどこにあるか，と言うのがすぐに分かる． そのため，1番目から順番に正しい…

概要 K個の搾乳機とC匹の牛がいる． 搾乳機はそれぞれ，1日につきM匹まで搾乳できる． それぞれの搾乳機と牛のあいだに距離が設定されている． すべての牛を搾乳するために，動かなければいけない牛の距離の，最小値を求める． 解法 ウォーシャルフロイド＋2…

概要 2進数の符号が与えられる． それらの符号が瞬時符号か答える． 解法 trieとかをつくって，ある符号が他の符号の途中の場所で終わらないか確かめる．

概要 n 海岸線から一番遠い点は，海岸線からどれだけ離れているかもとめる． 解法 コンベックスカットという，凸多角形を直線で2つに分ける操作がO(n)でできる． ある直線から距離がd離れた直線は簡単に求められるから，距離に関して2分探索すればいい．

概要 多項式2つが与えられるので，それらが恒等式か判定する． 式は，足し算引き算掛け算，変数のべき乗で，べき乗は10乗まで． 解法 いくつか値の割り当てを試して，いつでも等しい値かチェックするといいが， 10乗とか出てくるので，BigInteger必須． 本当…

卒論発表も終わったのですが，あまりにひどい卒論だったため，卒業資格が与えられるのか非常にビクビクしながら日々を過ごしています． これで卒業できたの？（´・ω・｀）卒論中にこっそりやった問題がいっぱい溜まっているので，覚えてるのをごっそり書きま…