裏紙

ほぼ競プロ、たまに日記

programming

素数テーブルをO(n)で構築する

からまでの数が素数であるかどうかの配列(素数テーブル)をで構築する。 はじめに まず、このような素数テーブルの構築といえばいわゆるエラトステネスのふるいが有名です。小さい方から、その倍数にバツマークを付けていくと、で構築できます。実装も素直で…

CF 631 E - Product Sum

問題 Problem - E - Codeforces 問題概要 長さの1-indexedな配列がある。この数列に対して一度だけ、数列のある要素を選び、その要素を数列内の好きな位置に移動するという操作をすることができる。 このとき、の取りうる最大値を求めよ。 アイデア 何も動か…

WUPC 2019 H - Doki Doki Programming Clubs!

問題 H - Doki Doki Programming Clubs! 問題概要 個の数列が与えられる。 番目の数列の長さはである。 クエリとは以下の通り: 数列について、をで割った余りを答える 上記のクエリが個与えられるので、各クエリについて答えよ。 アイデア まず、クエリにつ…

BAPC 2018 D - Driver Disagreement

問題 Dashboard - 2018 Benelux Algorithm Programming Contest (BAPC 18) - Codeforces 問題概要 個の交差点がある。交差点は道が二手に分かれており、左に行くと交差点に、右に行くと交差点に辿り着くことが分かっている。また、交差点からピサの斜塔が見…

CERC 2016 D - Dancing Disks

問題 gym 問題文 問題概要 ハノイの塔のような、いくつかの棒と、それに積み重なった輪っかを考える。 棒は6行、6列の36本の棒が立っている(上から行目、左から行目の列の棒を棒と呼ぶことにする)。 輪っかは全部で個あり、大きさはすべて異なる。輪っかには…

2018/9 solved(1)

9/1 CF 1029 F - Multicolored Markers まず、全体が長方形にならないといけないので面積がa+bの長方形ができる必要があり、その全パターンは約数の個数に一致するので、まずa+bの約数を列挙し、それらが実現可能かをそれぞれチェックする。以下、h*wの長方…

2018/8 solved(2)

8/17 8/18 CF 980 C - Posterized 辞書順最小→貪欲(submission)。 CF 980 D - Perfect Groups 同じグループにできるのは、正負が一致かつ素因数の個数の偶奇が一致するものが同じグループにすることができる。ただし、0だけは特別扱いする必要があり(0はどの…

2018/8 solved(1)

8/1 CF 992 A - Nastya and an Array 8/2 CF 992 B - Nastya Studies Informatics まず、lcmとgcdの関係から、xy = abが成り立ってないといけないが、これを満たすようなaの個数は約数の個数で抑えられており、それはlogで抑えられていると考えれば、xとyを…

2018/7 solved(2)

7/17 imulan.hatenablog.jp 7/18 CF 1009 A - Game Shopping CF 1009 B - Minimum Ternary String 1が自由に動けて、0と2の順序はどう頑張っても入れ替えられないことに注目すれば、2の後に来る0を境目として0...01...12...2のような文字列が繰り返されるこ…

CF 1004 F - Sonya and Bitwise OR

問題 Problem - F - Codeforces 問題概要 はじめ、長さの数列と整数が与えられる。次のようなクエリを考える: クエリ1 : をに変更する。 クエリ2 : を満たすpairについて、数列における区間のすべての要素のbitwise ORを取ったときの値が以上になるようにに…

2018/7 solved(1)

7/1 JAG 国内模擬 に参加 6完だった。Gも考察はできてて、サンプルも合ったんだけど、間に合わせられず...国内予選のリハーサルをできて動きを確認した(両面印刷はやめよう)。 ARC 100 に参加 久々に参加した。もっと時間作って参加したいんだけど、どうして…

2018/6 solved(2)

6/16 AOJ 1238 - True Liars V(=T+L)人いるときに、頂点数2Vのグラフを作る(各頂点は、i番目の人がdivine/devilに対応)。すると、与えられる情報から、2本の辺を貼ることができる。x,y,"yes"なら、xのdivineとyのdivine、xのdevilとyのdevilの間に辺をはり、…

BAPC 2017 J - Jumping Choreography

問題 http://codeforces.com/gym/101666/attachments/download/6490/2017-benelux-algorithm-programming-contest-bapc-17-en.pdf 問題概要 はじめ、数直線上に匹のカエルがいる。番目のカエルの位置はである。 カエルはジャンプによって移動することができ…

2018/6 solved(1)

6/1 6/2 6/3 AOJ 2729 - Delete Files 長さが短い方から注目して消していくことを考えると、残ってる中で一番短いのを消すことを考えるときには、矩形の左側はそれを含むように取れる必要がある。あとは、それを上下にどれくらい伸ばせるかをチェックして、…

2018/5 solved(2)

5/17 AOJ 1281 - The Morning after Halloween 今3体がどこにいるかをkeyにしてBFS/DPをする。一見間に合わなさそうに見えるが、壁が多いのでなんだかんだ探索範囲は狭くなる。(submission)。 5/18 AOJ 2596 - Points and Lines 区間に対して、再帰的に計算…

2018/5 solved(1)

5/1 AOJ 1360 - Bringing Order to Disorder 和と積と大小関係を情報に持ちながら桁dpする。積の部分は、大きい値になりうるけどsparseなのでmapで管理する(submission)。 AOJ 1331 - Let There Be Light 各光源に対して、光を到達させるために取り除くべき…

2018/4 solved(2)

4/16 AOJ 1312 - Where's Wally 2次元ロリハのverify(submission)。 CF 938 A - Word Correction 4/17 CF 938 B - Run For Your Prize CF 938 C - Constructing Tests 4/18 CF 938 D - Buy a Ticket 初めに初期値を全部突っ込んでおいてdijkstraする。dijkst…

CF 938 F - Erasing Substrings

問題 Problem - F - Codeforces 問題概要 英小文字のみで構成された長さの文字列がある。これに対して、回目の操作では長さのの連続する部分列を切り取り、残った部分を連結してとする、ということをがなくなってしまう直前まで行う(つまり回数をとすると、)…

2018/4 solved(1)

4/1 AOJ 2326 - Number Sorting dp[i] := iがsubsetの中で最大になるような適切な選び方は何通りあるかを計算する。このとき、文字列でソートされた順でiを処理していくと、i未満の部分のdpの和を取ることでdp[i]の値を得ることが出来るので、部分和を高速に…

CF 958 E3 - Guard Duty (hard)

問題 Problem - E3 - Codeforces 問題概要 個の白い点と個の黒い点の座標が与えられるので、完全二部マッチングをつくりたい。マッチングさせた者同士を線分で結ぶ時に、その線分が交差しないような割り当て方を答えよ。 2点が同じ位置にある・3点が同じ直線…

AOJ 2720 - Identity Function

問題 Identity Function | Aizu Online Judge 問題概要 1より大きい整数が与えられる。次のような関数を考える: この時、のについてが成り立つような最小のを求めよ。このようなが存在しない時は、-1を出力せよ。 アイデア まず、考察したこととしては、が…

2018/3 solved(2)

3/16 yukicoder No.235 - めぐるはめぐる (5) HL分解を使って解く。そこよりもどういうSegmentTreeを作るかに時間がかかった。区間Addをするが、そのAddに頂点ごとに異なる係数がかかるので、一様にAddできない、どうしようってなった。ただ、区間sumを求め…

CF 822 E - Liar

問題 Problem - E - Codeforces 問題概要 長さの文字列と長さの文字列が与えられる。をいくつかの部分文字列に分解して、その中から任意の個数を選んで順序を崩さないように結合させる。その結合させた文字列をと一致させるために、できるだけ結合の数減らし…

2018/3 solved(1)

3/1 CF #411(Div.1) Virtual ABCの3完。Cの解釈に時間掛けすぎたけど、木という条件を利用することでクリークがそれ以上大きくならないというふうに考えることができ、色は貪欲に決まる。Dも途中までは考察できてたので、Dは解説見ずに通したい。 3/2 3/3 3/…

2018/2 solved(2)

2/15 imulan.hatenablog.jp CF #416(Div.2) Virtual ABCDの4完。Bはちゃんと愚直ソートを殺すケースが入っていた(ひっかかった)。 2/16 imulan.hatenablog.jp CF 895 D - String Mark それぞれの文字列a,bに対して、strictlyに辞書順で小さいaのpermutation…

CF 809 C - Find a car

問題 Problem - C - Codeforces 問題概要 のグリッドがある。上から行目、左から列目のセルをと表す()。各グリッドには、条件に従って数字が書き込まれている。その条件とは、 に書き込むのは、このマスより左側一直線()と上側一直線()の中に現れていない正…

CF 813 E - Army Creation

問題 Problem - E - Codeforces 問題概要 長さの数列と整数が与えられる。次のようなクエリが個与えられるので、それに答えよ: クエリ : 区間 について、同じ値は個までしか選べない時に、最大で何個まで選べるか (問題を読んでもらうと分かるが、オンライ…

CF 712 E - Memory and Casinos

問題 Problem - E - Codeforces 問題概要 個のカジノが一列に並んでいる(左から番目のカジノをカジノと呼ぶ)。カジノで遊んだ時に、勝つと1つ右に移動する。このときに勝つ確率はである。負けると1つ左に移動する(勝率は)。番目の左側と番目の右側は出口であ…

CF 811 E - Vladik and Entertaining Flags

問題 Problem - E - Codeforces 問題概要 のグリッドがあり、各セルに数字がかかれている。グリッドの美しさを、連結成分の個数と定義する(同じ数字かつ上下左右のいずれかで触れていれば連結とする)。 クエリ: グリッドの左端を、右端をで切った時に残る部…

CF 835 F - Roads in the Kingdom

問題 Problem - F - Codeforces 問題概要 頂点辺の無向グラフが与えられる。辺は頂点とを結ぶ長さの辺である。 このグラフのinconvenienceを、「全ての頂点対の最短路のmax」と定義することにする。 このグラフから連結性を保ちつつ1つだけ辺を取り除く時の…