https://atcoder.jp/contests/caddi2018/tasks/caddi2018_a 解法 https://atcoder.jp/contests/caddi2018/submissions/3838129a1×a2×...×aN=Pとなっているので、Pを素因数分解をしたときの素因数をa1～aNに分配していくことになる。 よって、Pをまずは素因数…

https://atcoder.jp/contests/caddi2018b/tasks/caddi2018b_b 解法 https://atcoder.jp/contests/caddi2018b/submissions/3851731H≦A, W≦Bを満たせば目標の長方形の板を手に入れることができる。 すべての素材について、この条件を満たすものを数え上げる。 …

https://atcoder.jp/contests/caddi2018b/tasks/caddi2018b_a 解法 https://atcoder.jp/contests/caddi2018b/submissions/3851616Nを数字ではなく文字列として取り込んで'2'の個数を数える。 数のまま数えたほうが早いだろうが、競プロ的には愚直で間に合う…

https://community.topcoder.com/stat?c=problem_statement&pm=15236マス(r,c)にmax(r,c) mod 3が書かれた平面がある。 この平面の左下が(r1, c1)、右上が(r2, c2)である長方形の総和を答えよ。 解説 以下説明のため、r=x, c=yとして説明する。 問題を簡単化…

https://yukicoder.me/problems/no/756 解説 https://yukicoder.me/submissions/303546チャンパーノウン数C10を実際に作って答えよう。 1～100の数を連結すれば小数第D位は確定する。 intをstringに変換する場合は、C++ならto_string関数を使おう。 int D; /…

https://yukicoder.me/problems/no/755 前提知識 累積和とimos法 考察過程 1. これはyukicoder特有のテクだが、pypyで通るよと言っている問題は怪しい計算量だけどそれでいいよというメッセージ 2. クエリ毎に長方形を数えるような問題は過去出会ったことが…

https://yukicoder.me/problems/no/754 考察過程 1. ★2の問題に見えないので、なるべく簡単に行けそうな道を探す 2. （NTTを知っていればそれを使いたくなるが、これは★2相当のアルゴリズムではない） 3. c[0]～c[N]をバラバラに求めよという問題ではないの…

https://beta.atcoder.jp/contests/abc115/tasks/abc115_d 解説 https://beta.atcoder.jp/contests/abc115/submissions/3745333再帰的な構造を含む問題は、大体再帰関数を使って解く。 f(level, x) := レベルlevelバーガーの下からx番目まででパティが何枚あ…

https://beta.atcoder.jp/contests/abc115/tasks/abc115_c 解説 https://beta.atcoder.jp/contests/abc115/submissions/3744746パッと見ると割と難しい問題に見える。 今回は入力をソートしても解くのに問題無いので、ソートしておく。 困ったら全探索をまず…

https://beta.atcoder.jp/contests/abc115/tasks/abc115_b 解説 https://beta.atcoder.jp/contests/abc115/submissions/3744361最も高い商品以外はそのまま足して、最も高い商品は半額にして足すというのを実装する。 最も高い商品を特定するために、配列Pを…

https://beta.atcoder.jp/contests/abc115/tasks/abc115_a 解説 https://beta.atcoder.jp/contests/abc115/submissions/3744434下手に工夫するより、場合分けで4択書いてしまうのも悪くない。 ループでEveを出す実装もあり、以下はそれで解いている。 int D;…

https://www.hackerrank.com/contests/joi2018/challenges/apples-5 前提知識 動的計画法 解説 最大値で個数制限があり、10^3制約ということなので、dp[10^3][10^3]っぽさがある。 ここから考えると、 dp[i][m] := i番目までのりんごをm箱に詰めたときの美し…

https://www.hackerrank.com/contests/joi2018/challenges/blocks-3 前提知識 動的計画法 解説 地点2～Nにある積み木は地点1に置くか、置かないかで考えるだけで良い。 他の地点に一旦移動させて、一気に地点1に移動するような行為をしてもコストは変わらな…

https://www.hackerrank.com/contests/joi2018/challenges/challenge-1716 解説 (x,y)から(a,b)への移動の最短ルートを考えてみよう。x=0のとき (0,0)からの移動は中央から一直線で行けるので、aだけかかる a=0のとき (0,0)への移動は中央へ一直線で行けるの…

https://www.hackerrank.com/contests/joi2018/challenges/rage-of-azerbaijan-citizens 解説 Xの城がYの城を攻撃するのも、Yの城がXの城を攻撃するのも変わらないので、 D=2のときは、DkとPkを入れ替えて、全てD=1のようにして処理する。 あとは、ルールに…

https://www.hackerrank.com/contests/joi2018/challenges/joi-joi-fall-in-love-1 解法 ゲームの手順を分数を使って、誤差なく計算する。 分子をup, 分母をdwnとして、計算していく。 x足す up += x*dwn x引く up -= x*dwn x/y倍する up *= x dwn *= y xで…

この記事は Competitive Programming (2) Advent Calendar 2018 の 8 日目の記事です。 前日はたたもさんの「コマンドラインツールatcoder-cliを公開しました」です。あまり見る機会は多くないけど、典型化できそうなニッチなネタを書いていきます。 対象は…

https://beta.atcoder.jp/contests/abc114/tasks/abc114_d 解説 https://beta.atcoder.jp/contests/abc114/submissions/3708229まずは、素因数分解のやり方である。（O(sqrt(N))のやり方） ある数を素因数分解するには平方数までで割れれば割って数えていけ…

https://beta.atcoder.jp/contests/abc114/tasks/abc114_c 解説 https://beta.atcoder.jp/contests/abc114/submissions/3708011全探索をしよう。 10^9以下の七五三数というのは実はそんなに多くない。 9桁で各桁357のいずれかになる組み合わせは3^9通りある…

https://beta.atcoder.jp/contests/abc114/tasks/abc114_b 解法 https://beta.atcoder.jp/contests/abc114/submissions/3707865すべてのXを全探索しよう。 文字を数字に変換する場合はc-'0'とすればいい。 string S; //------------------------------------…

https://beta.atcoder.jp/contests/abc114/tasks/abc114_a 解説 https://beta.atcoder.jp/contests/abc114/submissions/3707809Xの値で場合分けをすればいいが、3,5,7のいずれかを満たせばいいので、orでつなげてやればいい。 nt X; //---------------------…

https://ctftime.org/task/7103これはコマンドインジェクションと呼んでいいの？ 強いCTFerに教えてほしい。 解説 参考にした解説 1 2 3「1+2」とやると、Tokenが出てくる。 Token: TzoxMDoiRXhwcmVzc2lvbiI6Mzp7czoxNDoiAEV4cHJlc3Npb24Ab3AiO3M6Mzoic3VtIj…

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_f 前提知識 構築問題テク『「条件を満たす辞書順最小」頭から貪欲に整合性が保たれるように決めていく』 （部分永続のやり方 ←これは実装をうまくやれば…

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_e 前提知識 動的計画法 解説 https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3664663DPをする。 dp[i][j] := 整数iまで…

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_d 解説 https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3664721提出証明みたいな所があるが、貪欲で解く。 説明のため「…

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_c 解説 https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3664421競プロでよくあるテクとして、「絶対値は扱いにくいので…

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_b 解説 https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3664345 結構難しい問題に見える 200点問題 制約もでかい という…

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_a 解説 https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3664295選択肢が「1問目のみ」「2問目のみ」「どちらも」「解か…

https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_d 解説 https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3665682公式解説 公式解説放送公式放送、公式解説通りに実装した解法を紹介する。 ただ、時間が結構…

https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_c 前提知識 しゃくとり法 考察過程 1. 制約を見るとO(QN)な感じがする 2. O(N)でアルゴリズムを考えたときに運良くしゃくとり法がしゅっとでた 3. その方針で考えるとAC 解説 h…