2020-02-04

ABC108のCで詰まった話

問題

ABC108のCの解説がモロ載っているのでまだ解いていない方は注意してください。

問題文

整数 N,K が与えられます。N 以下の正の整数の組 (a,b,c) であって、a+b,b+c,c+a がすべて K の倍数であるようなものの個数を求めてください。ただし、a,b,c の順番を入れ替えただけの組も異なるものとして数えます。また、a,b,c の中に同じものがあっても構いません。

制約

1≤N,K≤2×105

N,K

は整数である

解説を読んでも理解するまで時間がかかったので、どうやって解けばいいのかを書いていきます。分からない方への解説となれればうれしいです。

そもそもの解説文

C: Triangular Relationship

Kが奇数の時、a; b; cをKで割ったあまりはすべて0である必要があります。Kが偶数の時、a; b; cをKで割ったあまりはすべて0であるか、あるいはすべてK/2である必要があります。このような組の個数は、N以下でKで割って0あまるものの個数とK=2あまるものの個数から求めることができるので、この問題を解くことができました。

なんで？？？？？？？？？？？？？？？？？？？

わからん。「多分整数問題で式変形して簡単に求める方法があるんだろうな」って思って色々変形してわからんかったから解説見たんだけど何もわからん。整数問題に弱すぎる。

以下解法です。

modを使った解法

$a+b,b+c,c+a$ がすべて $K$ の倍数になるってどういう時かを考えると、

$a \equiv 0 \pmod K$ and $b \equiv 0 \pmod K$ and $c \equiv 0 \pmod K$ または、

$a \equiv K/2 \pmod K$ and $b \equiv K/2 \pmod K$ and $c \equiv K/2 \pmod K$

しかありません。

（他の分数形のあまりだと $a+b,b+c,c+a$ のどれかが $K$ の倍数にならない）

よって、Kが奇数だとあまりが0のときのみ（K/2が整数にならないので）、偶数だとあまりが0とK/2のときとなります。

これこの記事書いている途中に気付きました あ～～～～～～、なるほどね、そりゃそうだって感じだ。ずっと、次に示す解法で解こうとしていたので時間がかかりました…。

式変形から求める解法

整数問題にありがちな（本当にそうか？）方程式の片側が整数だからもう片側も整数っていうやつを利用します。

$p, q, r \in \mathbb{N}$
$a + b = pK$
$b + c = qK$
$c + a = rK$
とします。

この時

$2a + 2b + 2c = (p + q + r) K$

$2(a + b + c) = (p + q + r)K$

$\displaystyle{\frac{2(a + b + c)}K = p + q + r}$

だから、

$p, q, r \in \mathbb{N}$

より、

$p + q + r$ も整数、よって

$\displaystyle{\frac{2(a + b + c)}K}$

も整数となります。

ここで、 $K$ の偶奇について考えます。

$K$ が奇数の時

$\displaystyle{\frac{2(a + b + c)}K}$

を整数にするためには、 $2$ は偶数なので $a + b + c$ が $K$ の倍数になる必要があります。

ここで、

$b + c = qK$ でしたから、 $a + b + c = a + qK$ となります。これが $K$ の倍数になるためには $a$ が $K$ の倍数になればいいです。よって、 $a$ は $K$ の倍数です。

$b, c$ についても同じように言えるので、 $a, b, c$ は $K$ の倍数となります。

つまり、

a; b; cをKで割ったあまりはすべて0

です。

$K$ が偶数の時

奇数の時と同様に

a; b; cをKで割ったあまりはすべて0

に加えて、

あるいはすべてK/2

が許されます。

これは、 $K$ 偶数より、 $K = 2m; m \in\mathbb{N}$ と置くと、

$\displaystyle{\frac{2(a + b + c)}K = \frac{a + b + c}m}$

となるからです。（ $K$ 奇数の時は分子の $2$ と割れませんでした。）

よって $a + b + c$ は $m$ の倍数となればよく、 $b + c = qK$ より、 $a + b + c = a + qK = a + 2mK$ だから、 $a$ は $m$ の倍数です。

つまり、 $a = ms = Ks/2; s \in \mathbb{N}$ と表せます。ここで $s$ が偶数なら $K$ で割った余りは0、奇数なら割った余りが $K/2$ になります。

同様に、 $b, c$ も求められます。

また、

$p, q, r \in \mathbb{N}$
$a + b = pK$
$b + c = qK$
$c + a = rK$

を考えれば

Kが偶数の時、a; b; cをKで割ったあまりはすべて0であるか、あるいはすべてK/2である必要があります。

です。

これで、Kの偶奇により条件が違うことがわかり、それぞれで条件を満たす個数を数えればよくました。

組み合わせの個数

組み合わせは何を選ぶかなので、 $(条件に合う数字の個数)^ 3$ してやればいいです。

$K$ 偶数の時の数え方に注意しましょう。

提出したコード

以下のようなコードを書けばいいです。

#include<bits/stdc++.h>
using namespace std;

int main(void){
    int n, k; cin >> n >> k;
    int cnt = 0, ans;
    for(int i = 1; i <= n; i++){
        if(i % k == 0) cnt++;
    }
    ans = pow(cnt, 3);
    if(k % 2 == 0){// k偶数
        cnt = 0;
        for(int i = 1; i <= n; i++){
            if(i % k == (k / 2)) cnt++;
        }
        ans += pow(cnt, 3);
    }
    cout << ans << endl;
}

まとめ

競プロの整数問題はmodで考えたらわかりやすいことが多い気がします。

というか普通の式変形はしんどい……

modで考えよう！！！！！！！！！！！！！！！！！！！！！！！！！！！

あと、pow使うとたまに手元と、提出先のものとで計算結果が違うことがあるんですが同じような人いますかね…（丸め誤差？）

2019-08-17

Djangoでブログを作った

最近テスト週間で競プロを放置していました。語彙力の著しい低下も感じています、せーりつです。

タイトルの通りですがDjangoでブログを作りました。ブログのURLは貼りません。

Django Girlsというサイトのチュートリアルに沿って作成しましたが楽しかったです。（小学生）

tutorial.djangogirls.org

そもそも、自分で何かを作った経験がなかったためGitをいじるのも初めてでなかなか苦戦しましたが、初めてデプロイした時の感動は素晴らしいものがありました。

まず、自分はWindowsしかもっていないため、Power Shellを使わなければいけないのですが、Power Shellの背景の青がめっちゃ嫌いなので、最初はWSLをつかってどうにかしようと試行錯誤していました（丸一日ぐらい）。が、Pythonの仮想環境を立ち上げる時にpip周りがどうも上手くいかず結局Power Shellを使うことにしました。

チュートリアルは懇切丁寧に書いてあったため、楽々ブログを作成することができました。フレームワーク自体触ることが初めてだったので、チュートリアルに沿って作業していると、「いろいろ楽にできてすごいなあ…」と何度も感じました。

Ruby on railsとかLaravelとか他のフレームワークがあるのも知っていたのですが、大学の授業でPythonを習ったというだけでDjangoを選びました。ProgateにRuby on railsのコースがあったと思うので時間があれば挑戦したいですね。（Progateをやらずに2か月放置していた）

こんな内容もクソもないエントリーになってしまいましたが、Djangoで何か作るのは興味が続く限り引き続きやっていきたいですね、それではまた。

2019-06-22

ABC131に参加しました

はじめに

今回は特にDまでしか解けない自分には速解きの回でした

速く解くのはタイピング速度とか心配症とかもろもろの理由で苦手なので、早解きの一つ上の問題を解けるようにしたいですね

4完、以下解法

A

stringで受けて

s[ i ] == s[i + 1] だったら"Bad"出せばいいです

atcoder.jp

B

絶対値が最小であるものを引けばいいので、「L <= 0 and L + N - 1 >= 0」、「 L < 0 and L + N - 1 < 0」、「L > 0」の３つに場合分けしましょう

atcoder.jp

C

「AからBの範囲にある、CでもDでもわりきれない数」の個数を言い換えて、「AからBの範囲にある、CまたはDでわりきれる数を全体から引いた数」にします

これは中学とかの数学でやったと思うんですが、ベン図を考えてやるとC∧Dの部分が重なるのでそこの部分を引いてやる必要があります

atcoder.jp

D

蟻本にもうちょい難しい問題が載っていました

貪欲の問題で、これは締切日でソートしてやって、ある仕事をやった結果その仕事の締切日を過ぎていたら"No"ということでいいです

atcoder.jp

おわりに

レートが上がってくれているのでうれしいです

毎週のようにABCありますがそのうち1回ぐらい休みたいです

（今回休むつもりだったけど）

それでは

f:id:seiritsu:20190622234311p:plain

2019-06-16

ABC130に参加しました

はじめに

今回は計算量改善と考え方に努めた回でした。

問題の発想自体は簡単なものばかり（僕が解ける点数の範囲では）だったのですが、D問題はそのままだとTLEがでてしまったので計算量をいかに減らすかを考えました。

最終的に４完ができたのでいいできだったと思います。

A

特にないです。

しいて言うなら「未満」とか「以上」の意味知っていますか？？

atcoder.jp

B

Di <= x を満たす分だけカウントしてください。

全てのDiがx以下だった時にループを抜け出す処理をしていなかったので1ペナくらいました。

atcoder.jp

C

実際にグラフ用紙に書いていろいろやってみたらわかると思います。

長方形の中心と、任意の点の２点を通る直線は長方形を２等分してくれて、結局この時が求めたい最大値なので、(W * H) / 2で答えが出ます。

与えられた点が中心以外の時は２点を通る直線はただ１つ存在するので0、中心の時は無限通り存在するので1を出力します。

これ高校受験を思い出しませんか？

atcoder.jp

D

見てすぐに累積和だと思って書いて出したらTLEくらったのでいろいろ考えました。

解説では累積和＋二分探索や尺取り法使っているんですが、自分は区間和の計算の始めどころを絞り、区間の片側を固定した時、ある区間の和がK以上ならそれよりも区間が大きくなれば必ずカウントされるじゃんって考えて、書いて出してみたら通ってしまいました……。

二分探索から逃げている節があるので、知らなかった尺取り法と一緒に勉強しようと思います……。

計算量改善と、あと単純にlong longにし忘れていたのもあって4ペナくらいました。

atcoder.jp

おわりに

今回もD問題を解くことが出来たのでよかったです。

昨日と相まってたくさんレートが伸びてくれました。

うれしい。

f:id:seiritsu:20190616232546p:plain

2019-05-25

ABC127に参加しました

はじめに

最近累積和を覚えて、その有能さに感動しているせーりつです

今回のABCは勉強の成果が出たんじゃないかという回でした

結果はABCDの4完です

初めて4完したのでとても嬉しかったです

それぞれについて解説していこうと思います

A問題

問題文を読んで以上・以下について理解していればできる問題です

最初、「6歳以上」を「5歳以上」と見間違えたまま提出しようとしたのは内緒です

B問題

これも問題通りにやれば解くことができます

配列で値をいちいち保持しておかなくてもx = x * r - Dを出力しながらループを回していくことで答えがでます

C問題

全てのゲートを通ることが条件でありL,RはN以下が保障されているので、Lはできるだけ大きくRはできるだけ小さくしてR - L + 1を出すことで答えが出ます

R - L + 1が0未満の時は答えは0です

D問題

上から大きいのをもっていってやるだけなんですが、Cの最大値未満のものが全て置き換わるわけではないので注意します

この問題、初めはCの最大値未満のものを全て置き換えていたのですが、これだとうまくいかないし、置き換えるものと換えないものの判定が面倒だったので没に

次に考えたのは、結局上から取っていくのでCiの分BiをAに追加してやり、降順にsortして上から取っていく方法でした

これは確かに正しい値が求まるのですが、配列の数が多すぎて実行時エラーになってしまいました

次に、実行時エラーになるならいらない奴は消してあげればいいじゃないかと考え、毎回追加するたびにsortして、後ろから追加した分抜いてやるというようにしたら予想通りTLEになってしまいました

最後に思いついたのが、pairで同じ数値のカードの枚数を保持する方法でした

vector<pair<ll, ll>> pairsに対して(Ai, 1)、(Bi, Ci)でpairを作り、1番目の要素について降順sortをしてpairs[i].secondの和がnになるまでpairs[i].first * pairs[i].secondをしたものを足せば答えとなります

ちなみに、priority queueというものを使えばもっと楽にできるみたいです

僕は名前しか知らなかったので思いつきもしませんでした

終わりに

ABが5分で終わり、Cが終わった時点で15分ぐらいだったので大分成長を感じました

さらに残り10分でDの解答を思いつくことが出来たため優勝できました

f:id:seiritsu:20190525233312p:plain — +71

レートが順調に伸びてくれているので、この勢いをなくさないようにしていきたいところです

明日のABCも頑張ります

2019-05-19

ABC126に参加しました

はじめに

今回からratedの範囲が広がって問題数も増えましたね！！

参加人数もとても多くなって嬉しいですが、それだけに競争相手も増えるので頑張っていきたいところです

モンハンワールドをアイスボーンが出る前に装備を整えておこうと思っていたらいつの間にかABCまでにご飯を食べる時間が無くなっていました……

そんなことはさておき結果はABCの3完でした

ですので解説もCまでです

A問題

大文字小文字の変換です

問題文をよく読んでいなかったクソ雑魚だったので与えられる文字が'A''B''C'の3つのみということに気が付きませんでした

気付かなかったのでtransfromを使って一度他のところにtolowerした文字列をコピーしていました

うーん…

B問題

if elseの使い方と文字列から数字への変換をすればいけます

問題だけ見たら大学のプログラミング言語の課題みたいですね

問題を初めて見たとき、どうやって条件分けるかとても悩んでしまい結果時間がかかってしまいました

文字列から数字への変換はs[0]-'0'みたいな感じにしてやるとできます

C問題

C問題だったので計算量について考えないといけないかなあと思いましたが素直にすればいけます

問題は桁数ですが、自分は初め10^-9「以上」の誤差を許容するとかいうわけわからん読み間違えをしていたのでそのまま2回ほど提出してしまいました

問題文はちゃんと読もう

小学生の時からさんざん言われています

浮動小数点の精度を設定する方法をしらなかったのでグーグル先生に聞いたらsetprecisionという関数を使ってやればできるらしいという調査結果が返ってきたのでおとなしく使いました

この記事を書いているときにはまだ7/7でWJなんですが多分通っていることでしょう

終わりに

今回は文字列や出力に関する操作を復習することができました

GW中にABCのAB埋めをしたときに文字列から数字への変換や大文字から小文字への変換はさんざんしたので、その成果がでてよかったと思います

あと銀髪赤眼の後輩と競プロする本も買って読んでました

booth.pm

本当に競プロに入門したてで例の三冊（チーター、螺旋、蟻）が難しいという人におすすめです

これで多分C問題に入門するまでは行けると思います（自分がC問題入門したてなので）

今回はここまでです

ありがとうございました

ratedでさらにrateもあがってるといいなあ

2019-04-28

ABC125に参加しました

はじめに

結果はABDの3完でした

C問題が難しくてTLEが取れませんでした

Twitter見てると累積和の応用で解けるらしいのでその辺をよく勉強していなかったことが悔やまれます

以下僕の解法です

A問題

0.5のことは考えてやらなくてもいいです

[T/A] * Bで答えが出ます

B問題

V - C < 0の時は宝石を買っても損してしまうので選ばないと考えます

後は選んだやつを全部足してやればX - Yの最大値が得られます

inputの仕方を間違えないようにしましょう

C問題

問題を見てすぐに、「ははーん、書き換えるやつは他の入力された数字にすればいいから、結局抜いてしまえばいいわけだな」と思って意気揚々と考え始めましたが、考えても考えてもO(N^2)から小さくすることが出来ずTLE

解答はないです

すみません

累積和に関する知識が不足しているので勉強します

D問題

あるパネルをひっくり返すとそれに隣接するパネルもひっくり返るようなミニゲームしたことありませんか？

今回は正が表、負が裏と考えて、右隣のやつが連動すると考えて実験していくと、負の数または０が偶数個入力されたときは全ての値を正の数または０にすることが出来ます

また奇数個の場合はどれかが負の数または０を取るので絶対値が小さい奴を引いてやればいいです

結局解答は

偶数個の時

|A1|+|A2|+......+|An|

奇数個の時

|A1|+|A2|+......+|An| - 2 * min(|A1|, |A2|, ......,|An|)

となります

32bit整数型に収まらないこともあるらしいのでlong long型にしましょう

終わりに

f:id:seiritsu:20190428001908p:plain — ABC125

緑パフォ、やったぜ。

初の時間中D問題ACでした、うれしい

最近は解ける問題が増えてきたので参加するのが楽しいです

今回の競技時間中、順位表から見てD問題をACしてる人の数がとても多く、問題文を見てみたら簡単だったので解きましたが、そもそもDも見ておく癖をつけておくべきだったと思います

今後の戦略に生かしていくことが多く見つかったABCでした

GW頑張って精進してゆきます

ここまで読んでいただきありがとうございました