2020-09-19

数列の剰余の周期性がわからない

はじめに

$\color{green}{具体的な証明、誰にでも分かる解説はこちらではありません。}$他をあたってください

これはABC179-Eで余りの周期性を使う問題があったので自らの理解のために書いたものです。正確性に関して、努力はしますが必ずしも正確とは言い切れません。また、私は数ⅠA,Ⅱのある程度の知識を持っているので、そこから理解しようとしています

鳩ノ巣原理ってなんだよ

コンテスト後のTwitterのTLを見ていると、鳩ノ巣原理というのが飛び込んできました。細かい説明はいろいろなサイトがやっているので省いて、簡単な説明をすると $ M $の区切りの中に$ N $個($ N > M $)のものを入れると、必ずどこかの区切りで重なる

というものらしい

今わかってること

今回の問題の概要は問題文から漸化式が出てくること

そんで、基本的に$ N > M $だと考えると、あまりの取りうる値が0,1,2,... M-2,,M-1だからどこかで余りがかぶるのは理解できた

んで、今理解できてないのはx ≡ y² mod Mのときにそれは周期性を持ってるのかというところ

本題

高校数学の美しい物語さんによると、(an,a{n+1}) と (a{n2} , a{n2+1})の組はたかだかM²しかないから鳩ノ巣原理から (an,a{n+1}) と (a{n2} , a{n2+1}) の組が等しいものが存在するということらしい。

今回の制約は N ≦ 10¹⁰ , M　≦ 10⁵ なので成り立ちそうではある

いままで、a{n1} ≡ a{n2} mod Mのことばかり考えていたけれども、組で考えると、自明な気がしてきた

まとめ

余りの問題で、 M² < N なら周期性が使えそうだということがわかった。

ところで、ダブリングだと何も考えずに解けるらしい(伝聞)のでこれも勉強してみたい

2020-09-19

JOI2020/2021 一次予選　一回目参加・解説

競技プログラミング情報オリンピック

はじめに

この記事の問題名、入力の情報は日本情報オリンピック委員会に帰属し、CC4.0 BY-SAで提供されています。また本記事はCC4.0 BY-SAを継承しています

A問題 (2番めに大きい整数)

このA問題ですが、まあよく見る感じな気がします。解法としては、

配列に入れてソートして出力
$ (A+B+C) - (\min({a,b,c}) + \max({a,b,c})) $を出力

などがあります

ACしたコードはこちら

//前略
//
int main() {
    cin.tie(nullptr) ;
    ios::sync_with_stdio(false) ;

    int a, b, c;
    cin >> a >> b >> c;
    cout << (a + b + c) - (max({a, b, c}) + min({a, b, c})) << "\n";
    
    return 0;
}

B問題(JOIソート)

問題名にソートって付いてますが、文字列をソートすると'I'<'J'<'O'なのでだめ。

問題から、J...JI...IO...Oの形になればいいので、各、J,O,Iの個数を数えてあげれば問題ないのがわかります。

ACコードはこちら

//前略
//
int main() {
    cin.tie(nullptr) ;
    ios::sync_with_stdio(false) ;

    int n;
    string s;
    cin >> n >> s;
    ll j = 0;
    ll o = 0;
    ll i = 0;
    for(auto c : s){
        if (c == 'J') j++;
        if (c == 'O') o++;
        if (c == 'I') i++;
    }
    cout << string(j,'J') << string(o,'O') << string(i,'I') << "\n";
    return 0;
}

C問題(共通要素)

共通要素を求めて、昇順に出力すればいいです。find()を使いましたが、count()でも問題なさそうです

ACコードはこちら

#include <bits/stdc++.h>
#define rep(i, n) for (long long i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    vector<int> a(n, 0);
    rep(i, n) cin >> a[i];
    vector<int> b(m, 0);
    rep(i, m) cin >> b[i];

    set<int> res;
    rep(i, n) {
        if (find(all(b), a[i]) != b.end()) res.insert(a[i]);
    }

    for (auto r : res) cout << r << "\n";
    return 0;
}

終わりに

一次予選は去年二次行った人は出る必要がなかったんですが、楽しそうなので出ました。

去年同様、ABC-A,ABC-Bぐらいが出てるような気がしました

2020-09-12

PCK2020予選　参加記

競技プログラミング

成績

5完

はじめに

こんにちは、Spadyです。

今年はPCK2020予に参加したのでブログの更新をしました。

反省することが殆どでしたが、JOI予前に反省できてよかったと思うことにしました。

～開始

PCKの相方を探し始めて三千里、相方が見つからなかったので1年に頼み込みました。

頼んだのがPCK受付終了(延期前)の1日前だったのでOKもらったあと校長に許可を取りに行ったりしました。

PC室でやったので環境はzipで持ち込んで、VSCode(gcc)にしました。

当日に持っていったのは、

蟻本
テンプレートとか集

を持っていきました。本当は考察用のノートを持って行きたかったんですが、忘れたのにPC室に着いてから気づきました。TLEです

開始～30min

大体8問目ぐらいの問題を印刷しました。(ただし使わなかった)

4問目までAC 、ペナ0

30min ～ 160min

5問目に130分掛けました。5WA

これすごくJOI'19-20二次のA,Posterに酷似しててすごく見に行きたくなりましたがオンライン資料見れないので無理やり頑張ろうと思ってました。が、これが沼でここだけで60minかかったと思います。クエリが大きいのについての方針は5秒で立ったのにまさかそこで沼るとは思ってませんでした。

今になってですが、VSCodeのデバッガ使ったらすぐバグとり出来たので反省です(なんで使わなかったんや)

　とはいってもこの問題だけに130min使ったわけなくて、6問目の正四面体を作ったり他の問題文を読んでたりはしてました。ただ、余計に頭が動かなかったのでこれは愚策でした。

150minで順位表が凍結され、この時点の成績としては、順位表凍結時点で151位(4完)でした。

160min~180min

さて、あと20分になったんですがもう頭は働きません、なぜなら2h30m近くしょうもないバグとりに頭の容量を割いていたからです。このときは、手っ取り早く実装できそうで方針がすぐ立ちそうな問題を探しはじめました。

その結果、問題8が n <= 50だしDFSで良さそうとか思っちゃったので書いたのですが、終わりかけなのもあったのかジャッジが遅々として進みません。これでは別解を考えるべきかさえわかりません。(まあこの時点で別解を実装する時間もありません)。そして178min時点でやっとジャッジが終わったのでみたらTLEしてました。さて、こうなった以上どうしようもありません。そろそろ警備員の方がやってきて下校を促してきます。というわけでPCK予終了しました

振り返りと反省

　そもそもこの日までに精進をしていなかったのが問題ですね。この日まではStreakつなぎしかしていなかったのがある種の反省点かもしれません。

　また、DPが苦手だとわかっていたのにろくに対策もせず、当日の朝も1問も解いてなかったので流石にもったいなかったなと感じました。

　振り返りとしては、持っていった資料で使ったのはテンプレートだけで、ほかは使いませんでした。あと、pdfの問題文見づらいですね。いつもAtCoderの問題文に頼ってることがわかりました。

　来年は受験年でどうなるかわかりませんが進捗次第では来年も挑戦するかもしれません。そのときこそは対よろです。

2020-06-13

AtCoder緑になりました

要約

ARC級コンテストの東京海上日動コンテストで緑に上がりました！

f:id:spady:20200613233903p:plain

緑！！
spadyさんの東京海上日動　プログラミングコンテスト2020での成績：1582位
パフォーマンス：1271相当
レーティング：752→817 (+65) :)
Highestを更新し、6 級になりました！#AtCoder #東京海上日動　プログラミングコンテスト2020 https://t.co/8obozwBHpy
— Spady (@Spady_JP) 2020年6月13日

AtCoder茶色になりました

Atcoder

要約

題名のとおりAtCoderBeginnerContest 162で茶色に上がりました。やったぜ！ f:id:spady:20200412231013p:plain

ABC158参加した A-D4完

AtCoderBiginnerContest

ABC158　感想(A~D)

A問題:https://atcoder.jp/contests/abc158/tasks/abc158_a

AとBがあるかどうかを判断すればいいことに終わってから気づいた。C駅あると思ってた。

まあ全列挙しておしまい。

回答コード

https://atcoder.jp/contests/abc158/submissions/10590439

B問題:https://atcoder.jp/contests/abc158/tasks/abc158_b

数学だなーと思いながら実装を間違えて3WAしてしまった。

まさか10の100乗するはずもないのでNを割ったりして求める

回答コード

https://atcoder.jp/contests/abc158/submissions/10612301

C問題:https://atcoder.jp/contests/abc158/tasks/abc158_c

こっちのほうがBよりぱっとできた。

制約からB <= 100だから、最大でも￥1009だから全探索すると終わり。

回答コード

https://atcoder.jp/contests/abc158/submissions/10615470

D問題:https://atcoder.jp/contests/abc158/tasks/abc158_d

はじめてRatedのD通したので嬉しさで跳ねました。

最初はcharのvectorでやろうと思ったけど調べてたらDequeという便利なものがあったので使いました。

reverseは毎回やるともれなくTLEするので何回指示が来たかメモっておいて最後にreverseするか否かをやりました。

回答コード

https://atcoder.jp/contests/abc158/submissions/10632503

感想

４完　よっしゃ！！

2020-02-15

リクルート日本橋ハーフマラソン2020　予選参加記

Atcoder

リクルート 日本橋 ハーフマラソン2020　予選参加記

3行でまとめて

成績128026点（A:128026,B:0)
積:352位
マラソンって面白いね
Bどうにかしたかった

よし？337位
(積：352位)#R_procon pic.twitter.com/DI1gYcp310
— Spady＠ASAPで茶色 (@Spady_JP) 2020年2月15日

感想

　いつもはABCのDとかで詰まってる灰色コーダーのSpadyです。

　今回は初めてマラソン形式のコンテストに参加したのでどうなるかとか、どんな問題が出るかとか全くわからないまま初参加しました。

　準備としては手元（Windows10）にPython3が入ってたかどうかの確認しかしてなかったので、コンテスト始まってからC++でtxtの出力だったりとかをググり始めました。そしてファイルパスの設定で5分ぐらい悩んで結局フルパスで記述するという荒業にでてました。

振り返り

A問題

4sub,2AC,1WA,2RE

１ACめ

流れてくるものをそのまま並べていく方法(89763点)

提出ページ

int main() {//include説省略
    int n,w,k,v;
    cin >> n >> w >> k >> v;
    vector<int> c(n,0);
    vector<int> value(n,0);
    rep(i,n)cin >> c[i] >> value[i];
    rep(i,n){
        cout << i%w << endl;
    }
    return 0;
}

2ACめ

できる限り同じ色を同じ段に並べようとしてる（とおもう）

128026点

提出ページ

int main() {//include省略
    int n,w,k,v;
    cin >> n >> w >> k >> v;
    vector< vector<int>> mino(n,vector<int>(n,2));
    rep(i,n)cin >> mino.at(i).at(0) >>mino.at(i).at(1);
    vector<int> memo(k+1,0);
    int i=0;
    rep(i,n){
        if(memo.at(mino.at(i).at(0)) == 0)cout << 0 << endl,memo.at(mino.at(i).at(0))++;
        else cout << memo.at(mino.at(i).at(0)) << endl,memo.at(mino.at(i).at(0))++;
        if(memo.at(mino.at(i).at(0)) == w)memo.at(mino.at(i).at(0))= 0;
    }
    return 0;
}

はじめに

鳩ノ巣原理ってなんだよ

今わかってること

本題

まとめ

はじめに

A問題 (2番めに大きい整数)

B問題(JOIソート)

C問題(共通要素)

終わりに

成績

はじめに

～ 開始

開始～30min

30min ～ 160min

160min~180min

振り返りと反省

要約

目次

精進グラフ

Diff Pie

緑入りの感想

最後に

要約

目次

AtCoder(競プロ)をはじめたきっかけ

やったこと

精進グラフ

今後

最後に

ABC158 感想(A~D)

A問題:https://atcoder.jp/contests/abc158/tasks/abc158_a

B問題:https://atcoder.jp/contests/abc158/tasks/abc158_b

C問題:https://atcoder.jp/contests/abc158/tasks/abc158_c

D問題:https://atcoder.jp/contests/abc158/tasks/abc158_d

感想

リクルート日本橋ハーフマラソン2020 予選参加記

3行でまとめて

感想

振り返り

A問題

～開始

ABC158　感想(A~D)

リクルート日本橋ハーフマラソン2020　予選参加記