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

チャンパーノウン定数 (1) [yukicoder No.756]

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

Zero-Sum Rectangle [yukicoder No.755]

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

畳み込みの和 [yukicoder No.754]

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

Christmas [AtCoder Beginner Contest 115 D]

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

Christmas Eve [AtCoder Beginner Contest 115 C]

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

Christmas Eve Eve [AtCoder Beginner Contest 115 B]

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

Christmas Eve Eve Eve [AtCoder Beginner Contest 115 A]

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

リンゴの出荷 / Apples [JOI2018 予選模試 E]

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

積み木 / Blocks [JOI2018 予選模試 D]

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

極座標の街 / Town of polar coordinates [JOI2018 予選模試 C]

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

アゼルバイジャン国民の怒り / Rage of Azerbaijan Citizens [JOI2018 予選模試 B]

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で…

JOI 君の初恋 / JOI,Fall in love [JOI2018 予選模試 A]

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

2018年ニッチな競プロ典型ネタ

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

756 [AtCoder Beginner Contest 114 D]

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

755 [AtCoder Beginner Contest 114 C]

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

754 [AtCoder Beginner Contest 114 B]

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

753 [AtCoder Beginner Contest 114 A]

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

expression [Kaspersky Industrial CTF Web 50]

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

Coins on the tree [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まで…

Union [CODE THANKS FESTIVAL 2018 E]

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提出証明みたいな所があるが、貪欲で解く。 説明のため「…

Concatenation [CODE THANKS FESTIVAL 2018 D]

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競プロでよくあるテクとして、「絶対値は扱いにくいので…

Pair Distance [CODE THANKS FESTIVAL 2018 C]

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点問題 制約もでかい という…

Colored Balls [CODE THANKS FESTIVAL 2018 B]

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問目のみ」「どちらも」「解か…

Two Problems [CODE THANKS FESTIVAL 2018 A]

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

Square Rotation [Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 D]

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

k-DMC [Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 C]

https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_b 解説 https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3660039まず、空でない連続する部分列は全列挙可能なのでやる。 本当に愚直にやるとO(N^3)掛かるが、…

Sum AND Subarrays [Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 B]

https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_a 解説 https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3659999問題で指定されていることをやる。 だが、実際に平均を出すと、誤差が怖いので、比較するとき…

Thumbnail [Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 A]

https://beta.atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_c 解説 https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3650243条件を整理しよう 数列の値は全て自然数 各チップ(i,j)にP[i]*Q[j] 各チップの値は1以上N以下 2,3番目の条…

チップ・ストーリー　～白銀編～ [DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 C]

https://beta.atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_b 解説 https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3650234ok[y][x] := 座標(x,y)が真っ黒か というのを用意して、真っ黒でない領域を消していくことを考えよう。 左…

チップ・ストーリー　～漆黒編～ [DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 B]