大変に下らないミスをしてけっこう時間かかった。 入力はどんなに自明な場合でも最後まで読みましょう わりとシンプルに実装できた気がする。 本選のとき通らなかったのは右いったり左いったりが複数回あるときの可能性を無視したてめという可能性が大。 #in…

今年の１月に発表されたIntelの新CPU「Sandy Bridge」から搭載された新機能に、「AVX」というものがあります。AVXを用いると、256ビットのレジスタを用いて、例えばdouble型の計算を4つ同時に行うなど高速に演算をすることができます。 AVXを使うためには、…

1914 Cramer's Rule ３元１次連立方程式を解け。解き方は書いてある。やるだけ 3257 Cow Roller Coaster ローラーコースターを作る。部品はそれぞれ置ける位置とコストと楽しさが決まっている。コストをB以下にして、楽しさを最大化せよ。DP 2376 Cleaning S…

2^10記念日

Grouped AIC への拡張 AICは、「複数マスを1つだと思う」技法によって大幅に拡張されます。そうすると普通にサイクルを見つけるのでは実装が大変なことになりそうですが、グラフを用いるとただ頂点と辺を追加するだけで統一的に解けます。 Grouped AICにおい…

昔作った数独ジェネレータで作りました。 18ヒントしかなくて、これぐらいのヒント数になると大抵簡単になるものですが、かなりどころの騒ぎでなく難しいです。数独ソフトにかけたら、かなり大変な手順になりました。

Core i7-2630QMの4コア使って15時間がんばってようやく1問できました。明らかにプログラムが悪い。あのプログラムは間違った問題を出力しないはずなので、多分解けると思いますが多分絶望的に難しいか面倒です。

3330 Dr. Podboq or: How We Became Asymmetric 木を、非対称性によってさだまる規則に従って左右入れ替えしたりせよ。まず木をidentifyするのに、文字列を使って考える。(x(xx))みたいな形は一意に木を復号できる。左の子をidentifyしたものと右の子をident…

以前、http://www.geocities.jp/master_mishichan/という数独の解法をたくさん集めたサイトを見つけました。ここにある解法を、数独ソルバーに組み込んで、ジェネレータを走らせて無理ゲーを大量生産したりしました。ここには、Simple Chain、Remote Pairs、…

3014 Cake Pieces and Plates M個のケーキをN枚の皿に分配する方法は何通りあるか。皿を並び替えると一致するものは同じと考える。DP。modをつかうとTLEするが使わないとTLEしない謎問題。 3761 Bubble Sort バブルソートにおいて、「ソートされていなければ…

3613 Cow Relays 重み付き無向グラフが与えられる。グラフ上のある2点をとったとき、その2点を結ぶちょうどN個の辺を経由するような経路のうち、最も重みの総和の小さいものを答えよ。まず入力の形が迷惑なのでidentifyする。 次に、辺が高々100本ということ…

3012 A Number from Yanghui Triangle パスカルの三角形上の数値を、桁揃えの0を入れた上で並べたものをMで割った余りを求めよ。(10K+1)N mod Mを求めるだけ。 3213 PM3 行列A,B,Cがある。Cは、計算機がA*Bを計算した値である。しかし、計算機はたまに計算ミ…

3522 Slim Span グラフがある。全域木のうち、「最大の重み−最小の重み」が最小になるものについて、その値を答えよ。Kruskalを、最初の辺を動かしてやるだけ 3027 Base equality r1 やるだけ