cafelier@SRM

SRM442

SRM | 02:54 |

SRM442 の成績・ソース (要ログイン) : AC/WA/- : うひゃー

550開く

• 点数的に難しそうだから950に行ってみた方がいいかなーと思いながらもいつも通りに真ん中から行く
• 『1x5のタイルを横に並べて5x5とタテに並べて5x5で作ったブロックの市松模様が無限にあるときにx1,y1,x2,y2を切り取ってできる模様を作りたい。1x5タイルは何個必要か。1つの1x5を1x2と1x3に分けて使ったりして良い』

• 気合いで延々と書くしか思いつかないなあ。
• 気合いで延々と書いた。40分くらいかかった。
  • x1,y1 が一番左上エリアにくるようにmod 5的にずらしたりxとy反転したり
  • x1-x2とy1-y2の幅が広いときと狭いときの4通りで場合分け
  • しんどい
• まあサンプル通ったので適当に…出しちゃえ。
  • こんなソースぜったいコーナーケース間違えてる気もするけど、かといってコーナーになるようなケースも特にないようなするし…まあなんでもいいや…

250開く

• 『AからBまでの範囲で、素因数分解した時の項数が素数な値の個数は』
• ≦100000。

• 素数判定/素因数分解を O(log 100000) でできるから、それかける100000でも余裕
  • 素因数分解の項数数えて1だったら素数だから、ルーチンひとつで綺麗にかけるなあ
• 書いた。サンプル通った。出しちゃえ。

950開く

• 25分近く残ってる。しかもスコアボード見たら凄い数の人が解いてる！解きたい！問題文長い！
• 『長いので略』

• とりあえず、company ごとに完全に問題が独立だから、それぞれ別にconflictを最小化して足し算すればよい。
• というループだけ書いた。

• で、companyごとには？
• 同盟関係グラフ書いてagencyがあるところを塗ったり既にguardいるところに印付けたり色々しながら考えてるタイム
• どうみてもなんかグラフのマッチングかフローになりそうなんだけどなーと思って仮想頂点足したり引いたり
  • だめだなー全然そっちに落ちない
• なんかグリーディーな戦略で行けたり？
  • guard増やして改善するところに置いていってなくなるまでやる。
  • 2秒で反例が作れた。ダメだ。

• そのままタイムアップ

撃墜タイム

• いちおう550を開いてみる…みんな自分のに負けず劣らず酷いコードだ読む気がしない…
• 250を下から順に見てみる。
  • 素因数分解のループで毎回素数判定入れてる人がいる。これ大きい素数で軒並み1000000×log 100000回近いループになるはずで、そういう素数の分考えると時間ヤバいのでは
  • とりあえず保留

• いろいろ見て回る
  • なんかトチ狂って i*i<=p みたいな終了条件がiが100000くらいになるとintオーバーフローするんじゃないか自分のソース、みたいなことが心配になりだした。
  • んで同じ事をやってる人に2,100000とか投げてみてチャレンジ失敗する。寝ぼけすぎです

• うわー自分の550落とされてる！
• これはもうダメだなーダメ元でさっきの遅そうな人にチャレンジしちゃえ
  • 失敗する。

感想

• 950が解けないのは単なる実力不足だからいいとして、
• 550みたいなのどうすればいいのかな。ううむ