はまやんはまやんはまやん

hamayanhamayan's blog

2020-03-01から1ヶ月間の記事一覧

Traveling Salesman around Lake [AtCoder Beginner Contest 160 C]

https://atcoder.jp/contests/abc160/tasks/abc160_c 解説 https://atcoder.jp/contests/abc160/submissions/11325671 ある家iから出発してすべての家を回る最短経路はi -> i+1 -> i+2 -> ... -> N -> 1 -> 2 -> ... -> i-1という感じになる。 つまり、1パタ…

RankingStudents [SRM 782 Div1 Med]

解法 簡単に書いておく。 貪欲法で解ける。 先頭から埋めていくことを考えると使える要素がどんどん少なくなっていく。 だが、末尾から埋めていくことを考えると使える要素がどんどん多くなっていく。 多くなる方がうまくいく場合が多いので、そっちでまず考…

EmptyTheBox [SRM 782 Div1 Easy]

前提知識 O(3N)のbitDP 解説 簡単にまとめておく。 サイコロで出せる合計の目の上限は2Dなので、Tが2Dを超えていたら、その部分は絶対余る。 なので、Tは2Dまでを考えればいい。 すると、bitDPができることに気が付く。 dp[msk] := 残っているペナルティトー…

Distributing Integers [AtCoder Beginner Contest 160 F]

https://atcoder.jp/contests/abc160/tasks/abc160_f 前提知識 全方位木DP 解説 https://atcoder.jp/contests/abc160/submissions/11325358 全方位木DPが分かっていないと解けない。 この問題で全方位木DPを学ぶには少し問題がややこしい。 入門問題としては…

Red and Green Apples [AtCoder Beginner Contest 160 E]

https://atcoder.jp/contests/abc160/tasks/abc160_e 解説 https://atcoder.jp/contests/abc160/submissions/11320313 今回の問題では、2種類の取り組み方をブレンドして解く。 C個の無色のリンゴの中で使う個数を「全探索」し、そのパターンで「貪欲」にリ…

Line++ [AtCoder Beginner Contest 160 D]

https://atcoder.jp/contests/abc160/tasks/abc160_d 解説 https://atcoder.jp/contests/abc160/submissions/11318810 今回の問題で最も重要なのは、制約に気が付くところにある。 Nは最大2000なので、O(N2)が通る。 計算量は107くらいを上限にしてとりあえ…

Japan Tech News #013 2020/03/28

hamayanhamayanがインターネットを巡回して得た情報まとめ。 "Japan"と言うには主語が大きすぎる。 Hottest Good Job!(グッジョブ) | Nintendo Switch | 任天堂 これの紹介動画に面白い工夫を見た 2人プレイで場所が離れたときに、最初は引きのカメラ1つだ…

ångstromCTF 2020 ( angstromCTF 2020 ) Web問題 ほぼ解説

CTFtime.org / ångstromCTF 2020 まだサーバが生きてたので、復習がてら、解法まとめ。 と思ったら教育的で昔の年もできるのね。 20点 The Magic Word The Magic Word [AngstromCTF 2020 Web] - はまやんはまやんはまやん htmlはChromeとかを使うと簡単に修…

Banned K [AtCoder Beginner Contest 159 D]

https://atcoder.jp/contests/abc159/tasks/abc159_d 解説 https://atcoder.jp/contests/abc159/submissions/11139315 今回のようなクエリ問題に対する対処はあまりパターンがない。 各クエリについて高速に計算 全部前計算してしまう 差分を計算することで…

Knapsack for All Segments [AtCoder Beginner Contest 159 F]

https://atcoder.jp/contests/abc159/tasks/abc159_f 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc159/submissions/11138847 DPを使ってまとめて数え上げることができる。 思いつく仮定としては、DPで解くんだろうと考え始めることと、N,S≦300…

Dividing Chocolate [AtCoder Beginner Contest 159 E]

https://atcoder.jp/contests/abc159/tasks/abc159_e 解説 https://atcoder.jp/contests/abc159/submissions/11137460 どう見てもHの制約の小ささが気になるので、2Hを中心に考えてみる。 チョコレートを横に切る操作は2H-1通りあるので、全探索できる。 横…

Japan Tech News #012 2020/03/22

hamayanhamayanがインターネットを巡回して得た情報まとめ。 "Japan"と言うには主語が大きすぎる。 Hottest 競技プログラミング なんだかなぁ 小山高専プロコン fizzbuzz [OyamaC] rot and rot [OyamaC] storage [OyamaC] sumsumsum [OyamaC] tiktak [OyamaC…

123 Triangle [AtCoder Grand Contest 043 B]

https://atcoder.jp/contests/agc043/tasks/agc043_b 解説 https://atcoder.jp/contests/agc043/submissions/11065208 まず、答えは0,1,2の3択になる。 このどれが答えになるかを求めていこう。 これは実験すると分かるし、操作を見てみるとそうなりそうなこ…

Range Flip Find Route [AtCoder Grand Contest 043 A]

https://atcoder.jp/contests/agc043/tasks/agc043_a 解説 https://atcoder.jp/contests/agc043/submissions/11063628 左上から右下へのとある経路を考える。 この経路で移動しようと考えたときの必要な最小操作回数は「白→黒」となった回数である。 (スタ…

Prefix-Suffix Palindrome (Hard version) [Codeforces Global Round 7 D2]

https://codeforces.com/contest/1326/problem/D2 前提知識 Manacher 解説 https://codeforces.com/contest/1326/submission/73898734 高速にクエリをさばいていこう。 文字列のprefixとsuffixで回文となる最大長を計算しておく。 この最大長以下であれば、…

Permutation Partitions [Codeforces Global Round 7 C]

https://codeforces.com/contest/1326/problem/C 解説 https://codeforces.com/contest/1326/submission/73896496 最善の答えは、最も大きいK個の総和であり、これはうまく分割することで達成できる。 そのような分割にするには、最も大きいK個の間に分割の…

Maximums [Codeforces Global Round 7 B]

https://codeforces.com/contest/1326/problem/B 解説 https://codeforces.com/contest/1326/submission/73896052 実は順番に構築していけばいい。 x[0]は0で固定。 b[i]=a[i]-x[i]なので、a[i]=b[i]+x[i]である。 なので、a[0]=b[0]+x[0]を使って、a[0]を計…

Bad Ugly Numbers [Codeforces Global Round 7 A]

https://codeforces.com/contest/1326/problem/A 解説 https://codeforces.com/contest/1326/submission/73895303 n=1のときは、その桁で必ず割り切れるので答えがない。 2以上のときは必ず答えが存在する。 自分は222222....222223を作って、全体が3で割り…

文字列集合 [Kyoto University Programming Contest 2020 Spring M]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/M 解説 根性構築。 N=1,2のときはサンプルにあるやつを答えればいい。 3≦Nのときは、00, 010, 0110, 01110, ...と構築していけばN-1個を達成できる。 なぜN-1が上限(最適解)であ…

トーナメント [Kyoto University Programming Contest 2020 Spring K]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/K 前提知識 ダブリングDP 解説 どこから手を付けるかと言うと、まずは1クエリでの計算である。 クエリ問題での方針は、「毎回高速に計算」「一気に前計算しておく」「差分だけ計算…

数列ゲーム [Kyoto University Programming Contest 2020 Spring E]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/E 前提知識 grundy数 解説 ゲーム問題は実験せよと古事記に書いてあるのでやる。 正確には勝ち負けだけ分かればいいので、grundy数が0になる規則性を探してくる。 ひたすら実験し…

Xor Array [Kyoto University Programming Contest 2020 Spring D]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/D 前提知識 累積和による動的計画法高速化 前提知識 DPの作り方で運命が変わる。 dp[i][xo][lst] := 数列のi個目まで確定していて、総XORがxoで、最後の要素がlstであるときの組み…

サイコロを転がさないで [Kyoto University Programming Contest 2020 Spring B]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/B 解説 到達可能性といえばBFS。BFSだろうなぁと思って考えていくと解ける。 状態は(x座標, y座標, サイコロの下の面の数字, サイコロの右の面の数字)で表現する。 遷移は4方向な…

チーム分け [Kyoto University Programming Contest 2020 Spring A]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/A 解説 チームの組み合わせはC(4,2)/2通りしかないので、全通り試して実力差が最も小さいものを答えよう。 実装では、1234の順列を全列挙して、前半2人と後半2任でグループを作る…

Many Quotients hard [灘校75回生中学卒業記念コンテスト]

https://www.hackerrank.com/contests/75th/challenges/many-quotients 解説 https://www.hackerrank.com/contests/75th/challenges/many-quotients/submissions/code/1321983454 死ぬほどバグった。 分母を1からNまで増やして商を見てみると、途中から5,4,3…

I want to be a high achiever [灘校75回生中学卒業記念コンテスト]

https://www.hackerrank.com/contests/75th/challenges/i-want-to-be-a-high-achiever 前提知識 動的計画法 解説 重要なテクがあり、これが適用できれば、ACにだいぶ近づく。 「A[i]の平均がX以上 <=> A[i]-Xの総和が0以上」 平均を実際に求めようと思うと、…

Sashiming String [灘校75回生中学卒業記念コンテスト]

https://www.hackerrank.com/contests/75th/challenges/sashiming-string 解説 https://www.hackerrank.com/contests/75th/challenges/sashiming-string/submissions/code/1321979741 まず、何かしらの全探索対象を探す。 特徴的なのは、Sとingの位置なので…

Nada Picnic [灘校75回生中学卒業記念コンテスト]

https://www.hackerrank.com/contests/75th/challenges/nada-picnic 解説 https://www.hackerrank.com/contests/75th/challenges/nada-picnic/submissions/code/1321979520 良い問題。 なんとなくセンチメンタルになる。 答えは三択であるが、問題文からワー…

Nada Picnic 2 [灘校75回生中学卒業記念コンテスト]

https://www.hackerrank.com/contests/75th/challenges/nada-picnic-2 解説 https://www.hackerrank.com/contests/75th/challenges/nada-picnic-2/submissions/code/1321979536 手で計算してみたが、全然わからん。 ズルをすると、以下のサイトが見つかる。 …

Many Quotients easy [灘校75回生中学卒業記念コンテスト]

https://www.hackerrank.com/contests/75th/challenges/many-quotients-easy 解説 https://www.hackerrank.com/contests/75th/challenges/many-quotients-easy/submissions/code/1321979577 Nが小さいので、全探索しよう。 要素の重複を除くには、setを使う…