水色プログラミング

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

競技プログラミング

AtCoder Regular Contest 103

結果 C - /\/\/\/ D - Robot Arms E - Tr/ee 結果 1完+部分点(1 WA, 53:25),978 位中 451 位,パフォーマンス 1647,レート 1542 (+12, Highest).C 問題で WA をし,正解するのが遅くなってしまったのが痛かった.また,もう少し早い段階で D 問題の部…

AtCoder Regular Contest 103:C - /\/\/\/

問題 解法 解答 問題 C - /\/\/\/ 解法 数列の奇数個目と偶数個目で新しく数列を2つつくり,それぞれの中で最も多く登場する要素の数を N / 2 から引いたものが答えになるが,これだと,それぞれ同じ数字が当てはまってしまう場合が考えうる.そのため,「…

AtCoder Beginner Contest 110

結果 C - String Transformation D - Factorization 結果 D 問題を解き1完,1932 位中 940 位.400 点であった D 問題を解けたのはよかったが,C 問題が難しく解けなかった.D 問題より C 問題の方が難しいと感じた. C - String Transformation コンテスト…

CODE FESTIVAL 2018 qual A

結果 A - 配点 B - みかん C - 半分 結果 2完,1136 位中 250 位.A, B 問題をスムーズに解けたのは良かったが,目標であった3完に届かなかったのが残念. A - 配点 Submission #3241070 - CODE FESTIVAL 2018 qual A B - みかん Submission #3241714 - CO…

AtCoder Beginner Contest 110:D - Factorization

問題 解法 解答 問題 D - Factorization 解法 M を素因数分解する.M の各素因数を N 個の箱に分けていくと考えればよい.このとき,単純に N ^ (各素因数の個数) を掛け合わせたものを答えにしてしまうと,重複が生まれてしまう.なので,重複組み合わせ H(…

AtCoder Beginner Contest 110:C - String Transformation

問題 解法 解答 問題 C - String Transformation 解法 S -> T になるように各文字を置き換えるとき,S_i が T_i に対応するように1対1の関係になれば一致させることが出来る.逆に,1対1にならなければ一致させることは出来ない(1つのアルファベットを…

CODE FESTIVAL 2018 qual A : C - 半分

問題 解法 解答 問題 C - 半分 解法 「dp(i, j, f) := i 番目までで j 回操作するときの通り数(f := 今までの要素を 0 にしたかどうか)」で DP をする.f が true のとき,操作の回数が余ったとしても,どこか 0 である要素で余った回数を消費すれば良いの…

AtCoder Regular Contest 033:D - 見たことのない多項式

問題 解法 解答 問題 D - 見たことのない多項式 N 次多項式 P(x) があり,P(0), P(1), ... , P(N) が分かっているとき,P(T) を求める問題. 解法 さっぱり分からないので解説を読んだところ,ラグランジュ補間というものを使うらしいと分かった.これは,P(…

AtCoder Regular Contest 032 : D - アットコーダーモンスターズ

問題 解法 解答 問題 D - アットコーダーモンスターズ N 匹のモンスターには攻撃値と防御値がそれぞれ決まっていて,この中から K 匹選んでチームを作りたい.このチームの「不安定度」はチーム内のモンスター同士の攻撃値の差と防御値の差の min の max で…

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

AtCoder Regular Contest 035:C - アットコーダー王国の交通事情

問題 解法 解答 問題 C - アットコーダー王国の交通事情 全ての頂点が連結であるグラフがあり,この全頂点間の最短距離の和を S とする.「頂点 X と Y の間にコスト Z の辺を追加」というクエリが K 回与えられるので,K 回それぞれに対して S を求める問題…

AtCoder Regular Contest 032:C - 仕事計画

問題 解法 解答 問題 C - 仕事計画 a_i と b_i を始点・終点とする区間が N 個あり,それらからいくつか両端以外で重ならないように選ぶとき,最大でいくつ選べるかを求め,辞書順最小の組み合わせを求める問題. 解法 区間をソートし,時間を後ろから見てい…

AtCoder Regular Contest 101:D - Median of Medians

問題 解法 解答 問題 D - Median of Medians 長さ N の数列 a の全ての連続する部分列の中央値を集めた数列の中央値を求める問題. 解法 以下の2つの条件を満たす x は数列の中央値になる: 数列の中に x 以上の要素が半分以上含まれる x は 1. を満たす整…

AtCoder Regular Contest 101

結果 C 問題 結果 1完(18:19, 1 WA),796 位中 443 位,パフォーマンス 1530,レート 1530 (+-0).C 問題の早解きに失敗してしまったのが痛かった.レートが落ちなかったので助かった. C 問題 babcs2035.hateblo.jp

AtCoder Regular Contest 101:C - Candles

問題 解法 解答 問題 N 本のろうそくが x 軸上に並んでいて,K 本のろうそくをつけたい.最初,座標 0 にいるとき,移動するための最小コストはいくつか求める問題. 解法 x 座標が正のろうそくを i 本,負のろうそくを N - i 本つけると考えて,0 <= i <= N…

Summer Festival Contest 2018 (Division 2)

結果 A 問題 B 問題 結果 2完(92:29, 14 WA),77 位中 59 位.予想以上に問題がみな難しかった.時間が圧倒的に足りなかった. A 問題 babcs2035.hateblo.jp B 問題 babcs2035.hateblo.jp

Summer Festival Contest 2018 (Division 2):B - 太鼓の名人 (Taiko Expert)

問題 解法 解答 問題 B - 太鼓の名人 (Taiko Expert) 何回か D が続き,その後 K が何回か続く長さ N の文字列がある.この文字列が壊れてしまい,一部は ? となってしまっている.このとき,何通り元の文字列は考えられるか,という問題. 解法 一番右にあ…

Summer Festival Contest 2018 (Division 2):A - 夏祭り会議 (Summer Festival Meeting)

問題 解法 解答 問題 A - 夏祭り会議 (Summer Festival Meeting) 3人はそれぞれ X, Y, Z 分会議に遅れてくる.次回の会議では Y - Z, Z - X, X - Y 分遅れてくる.このとき,10^100 回目までの会議に誰かひとりが時間通り来るか,また,それは何回目の会議…

AtCoder Beginner Contest 105:C - Base -2 Number

問題 解法 解答 問題 C - Base -2 Number 整数 N を -2 進数に変換した結果を求める問題. 解法 2^(2k) (0 <= k <= 16) の位は +,2^(2k+1) の位は - になるので,それぞれ独立して考える(bit を1こ飛ばし).前者と後者で考えられる 10 進数表記を全列挙…

AtCoder Beginner Contest 105:D - Candy Distribution

問題 解法 解答 問題 D - Candy Distribution N 個の箱があり,それぞれ A_i (1 <= i <= N) 個キャンディーが入っている.ここで,任意の個数の連続する箱を選び,それらの箱に入っているキャンディーの合計が M で割り切れるようにしたい.連続する箱の選び…

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

AtCoder Beginner Contest 106 : D - AtCoder Express 2

問題 解法 解答 問題 D - AtCoder Express 2 東西に伸びる線路に都市が N 個あり,M 本の列車が都市 L_i と R_i の間を走っている.以下のクエリが Q 個与えられるので,それらに答える問題:都市 p_i と q_i の区間に走る区間が完全に含まれる列車の数. N …

AtCoder Beginner Contest 106

結果 解答 A - Garden B - 105 C - To Infinity D - AtCoder Express 2 結果 JOI 夏季セミナーに参加しているため,途中参加しました. 全完(2WA, 82:40),1981 位中 378 位.D 問題を普通に解くことができたので安心した.しかし,C 問題において実装ミス…