JOI2020/2021 二次予選 参加記
結果は?
はい、だめでしたね
(2020/12/18追記:ボーダー188点で予選落ちでした)
振り返り
去年参加して0点を決めたあと、1年間でAtCoderレートを緑まであげられました。
ただ、演習量が圧倒的に足りてないのはそうで、せめて難易度6埋めとか7まで持っていければもうちょっと戦えたんじゃないかという後悔もあります。
いま高2なので今回で最後のJOIでしたが、まあ1年で頑張れるところだったのかなという感じでした。できるなら中学とかから参加してみたかった…
これからどうしよ
高3で参加できそうな大会(競プロ)だとSuperConとPCKですかね。ちょっとマラソン系に興味が出てきたのでそれに挑戦していきたい。 あと何らかの開発をしたいな
まとめ
いかがでしたか?
ガチ精進勢じゃないしほぼ0からの競プロで成長を実感できたのは良かったです. もっと早くからJOI挑戦して行きたかった…
数列の剰余の周期性がわからない
はじめに
- $\color{green}{具体的な証明、誰にでも分かる解説はこちらではありません。}$他をあたってください
これはABC179-Eで余りの周期性を使う問題があったので自らの理解のために書いたものです。正確性に関して、努力はしますが必ずしも正確とは言い切れません。また、私は数ⅠA,Ⅱのある程度の知識を持っているので、そこから理解しようとしています
鳩ノ巣原理ってなんだよ
コンテスト後のTwitterのTLを見ていると、鳩ノ巣原理というのが飛び込んできました。 細かい説明はいろいろなサイトがやっているので省いて、簡単な説明をすると $ M $の区切りの中に$ N $個($ N > M $)のものを入れると、必ずどこかの区切りで重なる
というものらしい
今わかってること
今回の問題の概要は問題文から漸化式が出てくること
そんで、基本的に$ N > M $だと考えると、あまりの取りうる値が0,1,2,... M-2,,M-1だからどこかで余りがかぶるのは理解できた
んで、今理解できてないのはx ≡ y2 mod Mのときにそれは周期性を持ってるのかというところ
本題
高校数学の美しい物語さんによると、(an,a{n+1}) と (a{n2} , a{n2+1})の組はたかだかM2しかないから鳩ノ巣原理から (an,a{n+1}) と (a{n2} , a{n2+1}) の組が等しいものが存在するということらしい。
今回の制約は N ≦ 1010 , M ≦ 105 なので成り立ちそうではある
いままで、a{n1} ≡ a{n2} mod Mのことばかり考えていたけれども、組で考えると、自明な気がしてきた
まとめ
余りの問題で、 M2 < N なら周期性が使えそうだということがわかった。
ところで、ダブリングだと何も考えずに解けるらしい(伝聞)のでこれも勉強してみたい
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ぐらいが出てるような気がしました
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の問題文に頼ってることがわかりました。
来年は受験年でどうなるかわかりませんが進捗次第では来年も挑戦するかもしれません。そのときこそは対よろです。
AtCoder緑になりました
要約
ARC級コンテストの東京海上日動コンテストで緑に上がりました!
緑!!
— Spady (@Spady_JP) 2020年6月13日
spadyさんの東京海上日動 プログラミングコンテスト2020での成績:1582位
パフォーマンス:1271相当
レーティング:752→817 (+65) :)
Highestを更新し、6 級になりました!#AtCoder #東京海上日動 プログラミングコンテスト2020 https://t.co/8obozwBHpy
目次
精進グラフ
Difficulty Pie
精進グラフ
Diff Pie
緑入りの感想
灰の期間よりも断然に短い期間で緑に上がることができた。ただ茶Diffでも解けないもの(水筒とか)があるから茶落ちしないように頑張らなければ。
最後に
やっぱギリギリのところでACを出すのはアドレナリンが出ていいねぇぇ。
なんかARC級のA,B早ときでレートを爆上げしがちである
AtCoder茶色になりました
要約
題名のとおりAtCoderBeginnerContest 162で茶色に上がりました。やったぜ!
目次
AtCoder(競プロ)をはじめたきっかけ
情報の先生にJOIのことを聞いたのが多分はじまり。 中学のときにJavaとかC#とかC++とか触ってたけど家にあった本がC++だから競プロはC++ではじめました。ただまともにやり始めたのはJOI一次予選3回目前ぐらいです。
あさかつとかよるかつで速解きが得意目になったと思います。
やったこと
- AOJ プログラミング入門 #1 ~ #10まで
- JOI 難易度3以下うめ
- 全探索(bit全探索含む)
- 1次元累積和
精進グラフ
反映前ですが
今後
PCKとかの大会も本戦までいけるぐらいの技術は身につけたい。
BFSとかDFS系の探索アルゴリズムの習得
DP(ry
灰落ちすることのないように精進、精進!w
最後に
私は最初の頃AB二完したら撤退とか変なことやってましたがそんなことせずに最後まで考え抜きましょう
ABC158参加した A-D4完
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
感想
4完 よっしゃ!!