しるびあの競プロ精進記

silviaseが競プロの精進を騙って戯れ言を垂れ流す場所です。

ABC084-D 2017-like Number

問題

 N \frac{(N+1) }{2}素数である数を2017に似た数と定義する. Q個の各クエリは区間 l _ {i} ,r _ {i}を与える。それぞれに対して区間内に含まれる2017に似た数の個数を求めよ。

制約

  •  1 \leqq Q \leqq 10 ^ {5} , 1 \leqq l _ {i} \leqq r _ {i} \leqq 10 ^ {5}
  • 入力は全て整数

各クエリに対していちいち求めていくのは面倒くさいし二度手間になると考えるとまず思いつくのは累積和です。 関数 f(i)を、区間 1 \leqq x \leqq iに含まれる2017に似た数の個数と定義します。これを求めていく中で、 1 \leqq iなる iについて、  f(i) = \begin{cases} f(i-1)+1  \text{…iが2017に似た数} \\  f(i-1)\text{…else}    \end{cases}

という関係に気づきます。

さて、 i2017に似た数になる判定ですが、愚直に素数判定をします。より正確に言えば、 \sqrt {i}まで割って確かめてしまいます。本当はエラトステネスの篩などで素数を列挙してしまえばよいのですが、僕には如何せんそんなことは思いつきませんでした。

というのも、計算量が間に合う範囲だからです。 素数判定一回に \sqrt{N}かかったとして、 f(i)を全て下準備として求めるのに、 O(N \sqrt{N})しかかかりません。これは N = 10 ^ 5では 10 ^ 7スケールなので十分間に合いそうです。

ここまで下準備をすればあとはやるだけです。 各クエリ l _ i , r _ iについて、 f(r _ i) - f( l _ i - 1)を出力してやればよいわけです。 D問題にしてはやけに簡単でした。

この感触は正しく、D問題の正答者/A問題の提出者が 50 % を超えています。なるほどやはり簡単なはやときコンテストだったようです。1時間で全完が及第点、といったところでしょうか。Cが結構(読むのが)大変なので僕は果たして間に合うのでしょうか…?自信が無いです。

今週末はmikit君に「ABCに出ようね(ニッコリ」と恐喝応援されているので頑張って出ようと思います。激冷えして緑の森に入らないか心配でしょうがないですけど自分の成長のために頑張ります。

ただ野球見に行った後なんだよな…はい、頑張りますよ、やってやりますよ。

おしまい

/*
* @Author Silviase(@silviasetitech)
* For ProCon
*/

import java.util.*;
import java.lang.*;
import java.math.*;

public class Main{    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int q = sc.nextInt();
        int[] l = new int[q];
        int[] r = new int[q];
        int[] ruiseki = likenum();
        for (int i = 0; i < q; i++) {
            l[i] = sc.nextInt();
            r[i] = sc.nextInt();
            System.out.println(ruiseki[r[i]] - ruiseki[l[i] - 1]);
        }
             
        
        sc.close();
    }

    public static int[] likenum() {
        int[] num = new int[100001];
        num[0] = 0;
        for (int i = 1; i < 100001; i++) {
            if (isPrime(i) && isPrime( (i+1) /2 )) {
                num[i] = num[i-1] + 1;
            }else{
                num[i] = num[i-1];
            }
        }
        return num;
    }

    public static boolean isPrime(int n) {
        if (n == 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

}

CodeFesTeamRelayをバチャした話とC - Garden

注意:この記事で使用している言語はJavaです

昨日,はじめてバチャコンでチームリレーを行いました.メンバーは僕(silviase),idaten君,tmcoder君(ここまで全員水色),あとmikit君(黄色)です.当然のようにmikit君におんぶにだっこになりそうだなあと考えていました(実際にそうなった). 僕はレートが下から2番目だったのでとりあえずということでB問題,Evergrowing Treeの考察に当たっていました(A問題はtmcoder君が担当してさっさとACしてました.安定感があってすごいなと思いました).完全N分木のLCAを求める問題で僕はとても苦手. 自分が思いついた愚直な解法として,まず深さを同じになるまで大きい番号の方の親を辿り,異なるなら双方の親をひとつずつ上っていけば N=1の場合以外は O(Q\log N)で求められそう,というとこまで行ったのですが,実装が出来ない(いつもの).という中でCを考察していたidaten君が数学っぽいから出来るんじゃね?とCを投げられます.一方でBをidaten君に投げて実装を任せます(ここで自分なりの解法を伝えればよかった).

さてC問題についてみてみます.

  • 要約 正方向に無限に伸びる x軸上に,花iが位置 w _ {i}から右向きに間隔 d _ {i}で植えられている.左から見て K番目の花の位置を求めよ.

  • 制約   1\leqq N \leqq 10 ^ 5 , 1 \leqq K,d _ i \leqq 10 ^ 9\ 1 \leqq w _ i \leqq 10 ^ {18}

idaten君が「数学っぽい」といったのは, w _ i  \leqq 10 ^ {18}であることから,劇的に計算量の少ない解法が存在しない限りダメ,みたいな感触でとらえました.僕が知っている計算量と言えば O(1),O(\log w _ i)ぐらいしか知らなかったために,まず O(1)を探しますが,いや無理だろ…ってなったために \logの解法を考えます. ここで僕は非常に冴えていて,二分探索を思いつきます.これがなぜ可能であるかを証明します.

  • 証明 任意の位置 X,Y(X\leqq Y)において,その座標以下にある花の数を f(x)で表すとすると f(X) \leqq f(Y)が成立する.よって,各 f(x) xに関して広義単調増加関数である.したがって, f(x)=Kとなるような最小の整数 xが答である.

mikit君が確認したところ秒で頷いて帰っていったので「勝てねぇ(@^ ~ ^@)」ってなりながら実装に移ります.実は僕は水色なのに二分探索をまともにACしたことがない稀有な人材でして非常に大変だったのですが無事組めました.

/*
* @Author Silviase(@silviasetitech)
* For ProCon
*/

import java.util.*;
import java.lang.*;
import java.math.*;


public class Main{

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        long k = sc.nextLong();
        long[] w = new long[n];
        long[] d = new long[n];
        long low = 0;
        long high = (long)(2e18+1);
        long answer = (low + high)/2;
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextLong();
            d[i] = sc.nextLong();
        }
        

        // nibutan 
        while (high -low > 1) {
            answer = (low + high)/2;
            if (FlowerNum(answer,w,d,n) >= k) {
                high = answer;
            }else {
                low = answer;
            }
        }

        System.out.println(high);

        sc.close();
    }

    public static long FlowerNum(long x,long[] w, long[] d, int n) {
        long ans = 0;
        for (int i = 0; i < n; i++) {
            if (x >= w[i]) {
                ans += (1 + (x-w[i])/d[i]);
            }
        }
        return ans;
    }

  • 結論 みんなで考えるのって楽しいね。

早慶戦に行った話

はじめましての方ははじめまして.

そうでない方はn度目まして.

しるびあです.

早慶戦にいったよって話です.

年中行事みたいな感じですよねもう.

僕はウェイが嫌いなのでとある理由から慶応を応援できない体なので,

早稲田を応援しに行きました.

早慶戦一回戦までで5勝6敗.まー今年というか近年は弱いんですよね早稲田.

エースは小島 和哉投手(4年 浦和学院).

f:id:silviase:20180605125957p:plain
センバツ優勝投手でもある.

左の技巧派.左の本格派って少ないですけど最速147km/hのストレートに加えスライダー,カットボール,チェンジアップ,スローカーブってところでしょうか.打てねぇだろ普通.

いい感じに抑えてくれることを期待していたんですが土曜日の一回戦は3失点完投負け.

暴投とか内野ゴロがイレギュラーしたり不運な負けやなぁと思いました.

絶対的エースは前日に敗戦.今日の先発は誰だ…?うーん…

といったところでスタメン発表!!

1 池田
2 檜村
3 福岡
4 加藤
5 岸本
6 吉澤
7 小太刀
8 山岡
9 小島

_人人人人人人_
> 小島連投 <
 ̄YYYYYY^ ̄

まさかの二日連続先発.

高校野球かよ…

滅多打ちになりそうやなぁと思いながら早稲田の後攻で試合開始.

一回,二回と慶應が得点圏にランナーを進め,何とかしのぎ切る展開.

むろん早稲田は貧打に喘いでいるので走者は出ない.

まぁいつも通りの展開としては,ここから点数を取られ,打線は沈黙.

あーあ、と.

まぁでも今回は違ったわけですよ.

ただもうめんどくさくなったので詳しいことはこんな感じで()

f:id:silviase:20180605131621p:plain
スコアです(手抜き)

9-0完封.ざまぁみろ慶應いい試合でしたね.

僕としては紺碧の空がたくさん歌えたので良いとしましょう.

あとアレですね.

一年生の徳山君(大阪桐蔭).

f:id:silviase:20180605132140p:plain
右の本格派.早稲田にいなかったので素晴らしい.

大阪桐蔭とかいう字面がヤバい.

っょそぉ.

9回満を持して登板.

いい感じに抑えてくれますね.

ヨンタマがないので見てて楽ですよね.

にゃーん(歓喜)

秋に期待したいですねぇ......

\ヨコハマユウショウ!!/ってよくありますけど.

秋季は

\ワセダユウショウ!!/ってなればいいですねぇ...

去年の秋同率最下位なので.

大阪桐蔭様様やなほんま.

See you @gain!!!

すぐ更新が止まる日記-5日目

Twitterは続くのになぁ... はじめましての方ははじめまして.

そうでない方はn度目まして.

しるびあです.

さて,期末試験真っ只中です.

現在三科目が終わりました.

力学基礎:80~?? 英語第一:85~?? 有機化学:85~??

平均的にとれてるのでまぁまぁってところでしょうかそんな訳がない

だいたい必修で1500/1700とれればいい感じかなぁと思っているので...

450/500くらいとりたいんですけど,これはもう余裕ないですね…

全体的に90乗ってくれればいいんですけど...

うーーーん…情工行けんのか…??

これ2800とか無理だろ…

ヤクザになりたいめぅ…

今Q90オーバーで占めてれば勝ち,今までの三科目が全て90切ってたら負けでしょうか…

うーん,キッツいですねぇ

勉強もっとまじめにやればよかったですね.

2Qはまじめにやります.はい.

これも日記がすでに続いてないですね…駄目だぁ()

何とか続けたい.

See you @gain.....

atcoderで†圧倒的成長†した話。

\コンニチワ/

はじめましての方ははじめまして.

そうでない方はn度目まして.

しるびあです.

さて,Atcoder Grand Contest 025 が開催されました.

はじめて僕が参加したコンテスト(なにもできずレート6になったやつ)が

"Atcoder Grand Contest 024"

なので,その続編って感じでしょうか.

今回の配点,初級者向けじゃないだろって思ったんですが,

まぁAだけ解こうと決めていたのでとりあえずAをやる.

まずスキャナーを使って読み込み,if~elseの各桁和でおしま…ん?

1000とかどうすんねん.

あ,10の倍数は10にしちゃえばいっか…よしAC!

ねよう…ん?

540とかどうすんねん.

10,100,1000,10000だけ例外処理であとは各桁和にするべきでしたね.

布団の中で気づきました.

にゃーんって感じだ.

まぁでも気づけるくらいには成長してるのかな.

レートが上昇したのとてもうれしい!

13→"35"

茶色になるにもまだまだ遠そう…()

今週末のABCは2問解くことを目標に頑張っていきたいです.

See you @gain.

すぐ更新が止まる日記-4日目

ほら途切れかけた.

はじめましての方ははじめまして.

そうでない方はn度目まして.

しるびあです.

秋葉原に行くのだけでもテンション上がるし,まして池袋までサイクリングしてから向かうというぜいたく.

楽しみです.

明日は早慶戦に行こうと思います.

年中行事みたいなものなのでまぁ試験だろうが関係ないって感じですね.

夜勉強すればいいしね.

あと月曜に勉強すればいいし.

日曜の夜に生物を完全に理解して,月曜に化学の過去問を二回分解いて復習,あとは生物の確認.

それとお祈りを欠かさずしよう.

系所属ヤクザになるためにも1Qで取れる分だけ取っておきたいしね.

戦闘力を高めることがとても大事.

月曜は志を発表するらしいです.

僕はまーたクソレジュメを生成してしまったのでとてもつらみが深くなっています.

どのぐらいksかってもう笑っちゃうレベル.

まぁプレゼンなら腐るほどやってきたのでグループ内のプレゼンなら余裕です.

東工大内では珍しい部類なのでしょうか.

教育実験校のモルモットだっただけありますね.

うーん,やることが多すぎて整理できてない気がするし,2Qからは再び整理をしていきたいと思います.

ブログにも進捗書いたりすればやる気にも警告にもなりますしね.

未来の19の人たちも反面教師参考にして頂いて.

あ,2019年度新入生は19(いちきゅー)と呼ばれます(断定).

僕らは18(いちはち).希望留年したら19の仲間入りですね,ヤッタァトモダチデキルカナ

今月の目標は90秒ドローを続けること,作品2枚がお絵描きの目標.

プはレーティング三桁ですかね()

勉強はそうですねぇ…

うーん…これと言ってモチベーションがない.

必修にウェイトを置いてやっていこうと思います.

力を出し入れしながらうまい具合にね.

夏バテに気をつけていきましょう!

受験生諸君は夏が天王山とか馬鹿なこと言ってないでね.

夏は計算ミスをなくす期間なので.

過去問解いたり楽しくやっていければいいんじゃないですかね.

実戦OPはそんなに重要じゃないです.

AOで入ってしまえばいいんですからね.うんうん.

まぁ一般の方は期間がホラ,余裕あるし.

情報理工学院受験はマジでオススメ.魔境が体験できるから.

むしろ工学院は倍率緩みそうかな.

他は再編の影響ほとんどないからそんな感じ.

僕が受験するならCS(情理)→E(工)→MS(材料)ですかね.

転院ってなんかたらい回しな感じがしますね.

だから何だよ.

生命科学は覚えるだけなので楽(点が取れるわけではない)

See you @gain....

野球観戦報告になりそうだな,次の記事.