マガジン
よく使う(自分用)
comodo
- 2本
記事一覧
zone2021 B問題
B - 友好の印
この問題で必要な予備知識3つ
1. 直線の方程式は y = ax + b で表される。
2. a は変化の割合で、a = (yの増加量) / (xの増加量) と表される。
3. b は切片で、1. の式を変形すると b = y - ax と表される。
・初期値座標 (0, 0) と座標(D, H) を結ぶ直線を考えると、a = (H - 0) / (D - 0) = H
Python dequeを使ってみる
PAST第6回 - E をPythonのListを使って解いたらTLEしてしまったので、Listより速いらしいというdequeを初めて使ってみた記録です
※自分用のメモです
参考にしたページ
・まずは宣言
from collections import dequeque = deque()
・先頭と末尾への追加
# 先頭que.appendleft(1)que.appendleft(0
ABC199 C問題考察
C - IPFL
Ti = 1,2 の2種類のクエリが与えられますが、Ti = 2 の場合に毎回前後を入れ替えるという操作をすると時間がかかりすぎてしまうようです。
(具体的な計算時間については詳しくは知らないのですが)
ちなみに、前後を入れ替えるという操作はC++,Pythonでそれぞれ以下のように書けますね。
// C++// s.length() == 2*ns = s.substr(
ABC198 A,B解説
A - Div
N個のお菓子を一列に並べて、どこかに仕切りを入れて左側をAくんが貰う、右側をBくんが貰う、という図を思い浮かべます。
N=4のとき、以下の図のようになります。
今回の問題では「両者とも1個以上得る」という制約があるので「|oooo」や「oooo|」といった位置に仕切りが来ることはありません。
N個並んでいるときに、仕切りを入れる位置として考えられるのはN-1箇所なので、答え
隣接リスト(C++,Python)
入力例1行目は頂点数n,辺の本数mが与えられる。次のm行の入力で、辺Eiが頂点Aiと頂点Biを結んでいるという情報が与えられる。
C++
# include <iostream># include <list>using namespace std;int main(){ int n,m; cin >> n >> m; list<list<int>> e; for(int i=0;i<n;i
ABC195(2021/03/14) 振り返り
A - Health M Death
余りの演算子使えますか？ってだけ。
B - Many Oranges
よくわからなかったからとりあえず提出してみたけどWA。
入力例2を見ると、2種類のみかんの組み合わせを考えて解くの...？みたいに思ってしまってだいぶ時間ロスしてしまった。
Cを先に解いてから考え直したらぎりぎりACできたから、以下その説明。
例えば、入力例「A=300、B=33
ABC194(2021/03/06) 振り返り
A - I Scream
else ifで条件分岐を書き並べるだけ？思った通り書いてみた。
B - Job Assignment
入力で、min(Ai+Bi)を解として一旦保存しとく。そこから、min(Ai,Bj)(i!=j)の中で最小のものを探して解と比較したいけど、どうやって...?
って思ったけど、先週のABCで「困ったら全探索！！」ってなったのを思い出して(先週は素直に全探索してお
2021/03/03 今日の進捗
アルゴリズム実技検定の電子書籍版を買ったので、最近読み進めています。
競プロ始めたての人向けの解説が多くて、すごく読みやすいです。
全探索とか、自分がわかってる部分はスラスラ読み進めて、問題のグラフ理論へ。
隣接行列の実装方法はわかっていたけど、隣接リストの実装はしたことが無かったので、隣接リストを使いながら、テキストに載っていた、PAST第3回のE問題を実装してみた。
問題リンク
頂点
ABC193(2021/02/27)振り返り
A問題、B問題
難なく実装。
C問題
テストケースが、100000→99634だったから、a^bで表せない数を見つけるより、表せる数366個を見つけるほうが速そうだと推測(ここまでは合ってた)。
2 , 2^2 , 2^3 , ... , 3 3^2 , 3^3 , ... と数えていくが、4 , 4^2 , 4^3 , ... は 2^2 , 2^4 , 2^6 , ... と被るから除