keyword 動的計画法 C++ 概要 (x,y)のペアが与えられる。(x,y)>(x',y') を x>x' and y>y'で定義する。このとき、極大な元の個数を求める問題。ペアの個数は50000以下。 (x,y)を大きい順にソートする。yの最大値を覚えながら順になめていくと、yの最大値が更…

keyword 動的計画法 φ関数 C++ 概要 0

keyword 約数 包除原理 C++ 概要 n( オイラーのφ関数使えば解けるけど包除原理使って普通に実装した。

keyword シミュレーション 素数 C++ 概要 p(

keyword シミュレーション C++ 概要 グー、チョキ、パーの３状態でセルオートマトンを動かしたときnステップ後の状態を求める問題。 さすがにこれは愚直に書くしかないと思う。

keyword シミュレーション C++ 概要 曲がN( O(n^2)までいけるので特別なデータ構造を持たなくても愚直にシミュレーションすればよい。再分配のルールを勘違いしていて2WA位もらった。

keyword Dijkstra C++ 概要 2次元平面上に石が置いてある。石から石へジャンプして初期位置から目的位置まで移動したい。このとき最低限必要なジャンプ力を求めよ。 初期位置から目的位置までの最短経路とは別の問題だけど、DPちっくに書こうと思ったらDijks…

keyword 2部グラフ マッチング C++ 概要 数列a_iとb_iが与えられる。a_iとb_jは互いに素でなければペアとして選ぶことができる。最大でいくつペアをつくることができるか求める問題。 2部グラフの例題のような問題で動作確認にありがたい問題。

keyword ピタゴラス数 2部グラフ マッチング C++ 概要 200個以下の正の数字が与えられる(重複あり)。このとき、互いに素で2乗和が平方数になるようなペアがいくつ取り出せるか求める問題。 ペアは必ず偶数と奇数からなる。何故なら偶数と偶数のペアは互いに…