競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

CodeChef

CodeChef April long Challenge 2015 まとめ

4/3~4/13日の十日間開催。 初めて長期開催のコンテストに参加したがすごく勉強になるアルゴリズムが多かった。 これのせいでしばらく更新できなかったのでその穴を埋めていきます。 結果は8完+部分点2つ(92.14+13)で905.14点。全体27位でした。 Broken Tel…

CodeChef April long Challenge 2015 Black-white Board Game(BWGAME)

注:この記事はCodeChef終了後に更新しています。 本番中解けませんでした。 自分なりに理解して実装してみたのですが計算量が怪しいです。 - 問題概要 N*Nマスのボードがあります。 i行について、までのマスが黒色に塗りつぶされています。 黒じゃないマス…

CodeChef April long Challenge 2015 Little Party(LPARTY)

注:この記事はCodeChef終了後に更新しています。 ACできた問題。まさか論理回路系の問題が出るとは。 全体のAC人数が最も少ない問題となっていますが絶対にBWGAMEのほうが難しいと思う、、、 - 問題概要 上手く問題文が読めなかったので上手く訳せているか…

CodeChef April long Challenge 2015 Chef and Array(FRMQ)

注:この記事はCodeChef終了後に更新しています。 RMQの手法が沢山あることを知ることができた問題です。 空間計算量O(N)の方法もあるらしいですがちょっと難しそうだったのでわかりやすいスパーステーブルに逃げました。 - 問題概要 N個の数字が与えられま…

CodeChef April long Challenge 2015 Broken Telephone(BROKPHON)

注:この記事はCodeChef終了後に更新しています。たぶん一番簡単です。正答数も一番高いです。 - 問題概要 N人で壊れた電話を使って数字の伝言ゲームをする。壊れている電話は正しく数字を伝えることができない。 ゲーム終了後にN人にインタビューをし、どの…