No Such Blog or Diary

問題との相性がよかったので珍しく部屋内で二番目だったらしい．

250点問題：罰金って fine なんだなぁ，知らんかった．普通にシミュレーションすれば終わり．でも罰金の計算間違って時間をとられる．

500点問題：DPでいけるらしいのだけど状態空間の取り方が今一つ理解できてない．金と桁と余りのようなものとでできるらしいのだけど…ちょっと考えてよくわからなかったからパス．

1000点問題：二部グラフのマッチングで最大重みと最小重みを求めて終わり．なんとなく500点問題より簡単な気が…　とりあえず最少費用流のアルゴリズムを書くのに時間喰って点数半分くらい．

今更ながらだけど gcc4.2 で OpenMP 使えるのを試してみた．使うにはふつうに OpenMP のディレクティブ書いて -fopenmp つけてコンパイルするだけ．あとは OMP_NUM_THREADS 環境変数にスレッド数をぶち込んで動かす．

で，parallel for とか reduction(+:r) とかで並列実行されるのを確認．ただ，reduction で本来の計算以外に結構時間取られてるっぽいので要調査かな．

あと，OpenMP 2.5 の仕様をみると reduction のオペレータはオーバーロード禁止かついわゆる C or C++ の演算子しか使えないとあるのでgccでもそうなのか試してみよう．オーバーロードくらい許してくれないと何にも出来ん．

直前まで寝ててそのまま寝ぼけてた気がする…

250点:何なんだこの国内予選Ａ問題は？

500点:ソートしてから弾性マッチング．なのにおもむろに一般的な二部グラフの重みつきマッチングをやり始め…　途中で実装間違えて時間オーバー．

100点:時間なし．がんばって数えればいいのかな？

チャレンジのみの150点．でもシステム側の都合で rating は変化しない．

250点：よく考えたらいくらでも細切れにできるんだなぁ．ということで，少ない方はいつでも count まで使いきれる．多い方は，max まで連続したチャンクの集まりの上限を少ない方の count + 1 個まで作れる．ということで，この最大個数以下かつ count までが多い方の使える数なわけで…　と，ちゃんと考えるのが面倒で投げ出した．

500点：単純にやると指数時間（入力の数字の大きさに関して線形）かかるので却下．大小関係が保持される間は３周期のパタンを繰り返すことを使わないとだめ．基本的にはユークリッドの互助法みたいな進み方するので入力ビット数の線形ですむはず．でも時間なかった…

1000点：面倒そうなのでパス．正しいプログラムを見てみたいものだ．

変に時間を食って一問しか解けんかった・・・

250点問題：ベルマンフォード書いて終わり．だが，いくつか書き間違えてデバッグに時間を喰う．

500点問題：線分の交差判定のルーチンを書いて，あとは union/find で終わり．のはずだけど，判定式を書き切れなかったのでアウト．

1000点問題：アルファベットのバイナリエンコードに曖昧性があるかの判定だけど…　３つ以上のデコード列を持つ最小の文字列を探さないとならないらしい．愚直に全生成とかだとだめだよなぁ．よくわからず．

またとちった．

250点問題：BigInteger で舜殺可能．

500点問題：よくあるDPだけど微妙に形を間違え…　さらに事前のソート処理が必要なのをあとで思い出したが挿入位置を間違え…　なんてやってたら時間無くなった．

1000点問題：DAGから枝を抜いてけばいいのだけどどうやって抜いていけばよいのやら？