競技プログラミング

【競プロ】ABC18D
+1

【競プロ】ABC18D

ABC18Dを解きました。 制約がP、Qいずれも<=18なのでbit全探索を考えましたが、さすがにPもQも全探索すると間に合いそうにありません。(2^18=262144) Pを固定してQの方は条件の合うものを足しこんだ上、貪欲に多い方からとれば間に合いそうです。 古い問題ですが青difを自力で解けて嬉しかったです。 #include <bits/stdc++.h>using namespace std;#define rep(i,n) for(int i=0;i<

スキ
2
(動画インタビュー)教育にプロコンを導入してみて|北海道大学|札幌の長期インターンシップインタビュー

(動画インタビュー)教育にプロコンを導入してみて|北海道大学|札幌の長期インターンシップインタビュー

プロフィール・自己紹介北海道大学 工学部 情報エレクトロニクス学科 3年 熊谷 拓 参加期間:2020年7月~2021年9月21日(継続中) 参加中のインターンシッププログラム「6. その他」に参加しています。 社内のプログラミングコンテンツの運営、新卒研修でのプログラミングコンテスト課題へのチューター、内定者研修で利用しているMoodleの設定など、教育関係に携わっています。 インタビュープログラミングコンテストを社内に導入した感想と、得られた効果をインタビューしま

スキ
4
ABC217参戦記
+3

ABC217参戦記

はじめに2021年9月4日21:00-22:40ABC217に参戦しました。結果は9分07秒ABCの3完で3831位/8543人中パフォーマン698でレーティングは前回922から-20の902になりました。 A問題文字列S、Tの辞書順での大小を比較する問題。A問題らしい簡単な問題で一安心。 #include <bits/stdc++.h>using namespace std;int main(){string s,t; cin>>s>>t; if(s<t) cout<<

スキ
4
Python データ構造整理[heapq][deque]
+1

Python データ構造整理[heapq][deque]

■本記事について  今回の記事ではいつもAtcoder中にpythonの普通のリストだと計算量的に間に合わないけどなんかデータ型使えば上手く行けたはず,,,ってのを記事にしてまとめておきます. ■リスト型の計算量について  リスト型については上の記事を大変参考にさせて頂きました.下の図は上の記事より引用させて頂いております.要素の挿入や,削除,要素の探索,特定範囲のリストの取り出しはO(n)掛かってしまうことが分かります. ■優先度付きキュー(Priprity que

スキ
1
ABC217 D問題
+1

ABC217 D問題

■要約  切っていく場所を順番付きのリストに保存して,c=1のときも2のときも何番目にxがあるか知ればよいから二分探索でその場所を見つければO(NlogN)でイケルと思った.しかし,pythonには順番付きリストというものが存在しないらしい(C++などはあるみたい).平衡二分探索木というものを使えば良いらしいが本番中にはACできなかった.平衡二分探索木の中のAVL木というものを使うと, 上図のような計算量で要素の挿入が可能になる. なおこの表と実装には以下のサイトを参考

スキ
1
[AtCoder Begineer Contest 217] 参加備忘録
+3

[AtCoder Begineer Contest 217] 参加備忘録

こんばんは~! 表題にもある通り、今日は土曜日ということで、21:00からAtCoder Beginner Contest217に参加してきました。 今回で3回目?かな。まだまだ競技プログラミングに慣れていないので、A問題8割くらいの確率で完答+B問題2,3割って感じですね(C問題以降はまだ手も足もでないです笑) 本日の結果はこちらでした。 A問題については1発でクリア。(所要時間:4分程度) B問題については個人的にこれ正解でも良いんでは??というところまでは書け

スキ
2
ABC216参戦記
+2

ABC216参戦記

はじめに2021年8月29日21:00-22:40に開催されたABC216に参戦しました。 結果は96:09 ABCEの4完で1777th/7377人中,パフォーマンスは1122でレーティングは前回898から+24の922となりました。 A問題 最近はA問題から骨のある問題であることが多いと思います。見るからに誤差が怖そうな見かけなので文字列で受けて数字に変換して丁寧に判定する実装にしました。7:29はA問題としてはかけ過ぎか。なお、作問者のツイートによるとdoub

スキ
6
夏休みの終わりに

夏休みの終わりに

今朝方、ひと月余りの夏休みを終えて高校生の息子が帰寮していきました。いつもながら休みが終わって息子がいなくなると寂しくなります。一昨年までと違って、コロナ禍のため、長期の休み以外には帰省できず、こちらからも行かないので、冬休みまでの3か月ほど顔を見られないことになります。 昨年の正月ころから競技プログラミングを一緒にやっています。今年の春ころまではリードしていたけれど、春休みにレーティングを抜かれ、この夏休みにも差を広げられました。レーティングで400差ぐらいになっています

スキ
6
Atcoder 典型90問 076★3[二分探索][累積和]

Atcoder 典型90問 076★3[二分探索][累積和]

■要約  問題の流れは理解していたが,実装が難しかったことと,二分探索で条件を満たすRを見つけるという考え方が浮かばなかった.確かに二分探索ならO(logN)で見つけることができるので,こういう使い方もできるかのと勉強になった.  簡単に問題を解く流れを書くと以下のよう. ①連続するピースを表せるように,ケーキ2周分に配列を拡張する.▶ N番目から数える連続するケーキの組み合わせを表現できる ②累積和Bを求める. ③Br - Bl = Bn/10 となるrを探す旅に

Atcoder典型90問 069★3[繰り返し2乗法]

Atcoder典型90問 069★3[繰り返し2乗法]

■要約 N=1以外の時は,総数がK*(K-1)*(K-2)^(N-2)になることはすぐに分かったが,累乗の計算量はO(N)なのでどうしようかと考えていた.調べたら,繰り返し2乗法というものがあり,計算量をO(logN)に減らせる. 説明は他の方々がとてもわかり易いものを記載しているので割愛する. pythonだとわざわざ実装しなくても pow(x,y,n)でx^yをnで割ったあまりをO(logN)で計算してくれるらしい.鬼便利 N, K = map(int, inp