buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

yukicoder No.476 No.477 No.478 No.479

No.476 No.478 No.479のwriter,No.477のtesterをしました.

人との繋がりがないのでtester集まりませんでした

yukicoder contest 155 - yukicoder

解説はyukicoderの方を参照してください.本記事では問題に絡むネタを紹介します.

もちろん,ネタバレを含みます.

No.476 正しくない平均

与えられる整数は32bitで表現できるけれども,総和は32bitで表現できない,という問題.

nが10以下なので,double解法が撃墜出来ない(仮数部を溢れさせることが出来ない).

No.477 MVP

元ネタ知らない.グラブルという噂.

No.478 一般門松列列

実は難易度強化案があって,『出力する数はL以上H以下でなければならない』というもの. ☆2なので,そこまで締め付ける必要はないし.

サンプル3がヒントになったようです.

No.479 頂点は要らない

最小頂点被覆問題.一般にはNP困難と言われている.

しかし,各頂点の重みを互いに異なる2のべき乗にすることで,線形時間で解けるようになる. 判定条件もとてもシンプルなものになる.

関係ないですが,生放送中で誰も突っ込んでくれなかった→トランプ氏、選挙資金不足を否定 「私の富は無限」 | ロイター