水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

PCK 過去問

PCK 2016 本選:6 - 実数既約分数化

問題 解法 解答 問題 Aizu Online Judge 解法 循環小数を分数に変換する計算を実装するのみ.O(|str|). 解答 Aizu Online Judge 実装ミスにより 2 WA してしまった.

PCK 2016 本選:5 - 環状すごろく

問題 解法 解答 問題 Aizu Online Judge 解法 あるマスから飛ぶ先のマスに辺を張り,各マスから同じマスを2度まで通る DFS をする.一回一回の DFS ごとに,1回しか通らなかったマスを答えから除外していく.これを全てのマスについて計算すればよい.O(N)…

PCK 2016 本選:3 - 有理式最大化

問題 解法 解答 問題 Aizu Online Judge 解法 割られる数を出来るだけ大きく,割る数を出来るだけ小さくすることを考えればよい.割る数 C - D の C, D を全通り試し,余ったもののうち大きいもの2つを A, B に充てればよい.O(N^2). 解答 Aizu Online Jud…

PCK 2017 本選:5 - 朝昼晩ごはん

問題 解法 解答 問題 Aizu Online Judge 解法 朝・昼・晩の時間の決め方は,単純に考えると (24*60)^3 通り.これを全て計算していては間に合わない.時間の決め方は N 人の3つの時間の区間の始点と終点の数だけに抑えることが出来るので N^3 通りになる.…

PCK 2017 本選:4 - 電子メトロノーム

問題 解法 解答 問題 Aizu Online Judge 解法 t_i それぞれを t_i の最大値(M とおく)の約数にすることを考える.M の約数は O(MlogM) で列挙出来るので,各 t_i について t_i 以上で最も小さい約数にすることを考えればよい.O(MlogM). 解答 Aizu Online…

PCK 2014 予選:3 - 残り物には福がある

問題 解法 解答 問題 Aizu Online Judge 解法 やるだけ. 解答 Aizu Online Judge // gist.github.com

PCK 2014 予選:2 - お財布メタボ診断

問題 解法 解答 問題 Aizu Online Judge 解法 やるだけ. 解答 Aizu Online Judge // gist.github.com

PCK 2014 予選:1 - 椅子の総数

問題 解法 解答 問題 Aizu Online Judge 解法 答えは d * c. 解答 Aizu Online Judge // gist.github.com

PCK 2015 予選:6 - 品質管理

問題 解法 解答 問題 Aizu Online Judge 解法 愚直に処理をすると O(C * N^2) になり間に合わない.ここで,前のコースターとの差分と前のコースターが左右対称になっているかだけがこのコースターが左右対称になっているかどうかを決めると考える. 実装時…

PCK 2015 予選:5 - プログラミングコンテスト

問題 解法 解答 問題 Aizu Online Judge 解法 得点は 0 以上 100 以下なので全ての得点に対してスコアを計算する.このとき,二分探索を使うと便利. 解答 Aizu Online Judge // gist.github.com

PCK 2015 予選:4 - AZAS

問題 解法 解答 問題 Aizu Online Judge 解法 愚直に O(N^2) で実装した.添え字や配列のミスがあり 2 WA ほどしてしまったのが反省. 実は(先輩に教えて頂いたが),要素ごとに,A に属するものに +1,B に属するものに +2,C に属するものに +4 すると,…

PCK 2015 予選:3 - カエルはまっすぐ帰る

問題 解法 解答 問題 Aizu Online Judge 解法 巣穴を通りこさない限界まで大ジャンプをし,その後は1センチずつ進んでいくのが最適.O(1). 解答 Aizu Online Judge // gist.github.com

PCK 2015 予選:2 - 魚釣り競争

問題 解法 解答 問題 Aizu Online Judge 解法 四則演算をするだけ.追加でボーナスが加算される点に注意. 解答 Aizu Online Judge // gist.github.com

PCK 2015 予選:1 - 参加者数

問題 解法 解答 問題 Aizu Online Judge 解法 3つの和を求める. 解答 Aizu Online Judge // gist.github.com