keyword 平面幾何 反射 C++ 概要 ビリヤード台の幅と高さが与えられる(穴は無い)。中心からショットして、s秒後に縦横の壁にそれぞれm,n回衝突して中心に戻ってくる(衝突は全て弾性衝突)。このときのショットの角度と速度を求める問題。 セオリー通り反射は…

keyword 組合せ C++ 概要 n( 硬貨の支払い方の問題だと思うとDPが思い浮かぶ。素朴にやるとdp[n][平方数の個数][一番大きな硬貨]で、計算量は(2^15*4*2^8)*2^8となって解けない。DPではなく、各クエリに対して丁寧に場合分けして数え上げる。4枚で4つとも異…

keyword 尺取り法 C++ 概要 正整数Sと正整数の数列が与えられる(長さは100000以下)。和がS以上になる連続した部分列の最小の長さを求める問題。 プログラミングコンテストチャレンジブックを参考にして解いた。 それとreadint()を自作してみた。やっぱりscan…

keyword シミュレーション C++ 概要 100*100以下のボードがあり、どれかのセルが当たりである。正方形の辺の長さと位置と、その正方形に当たりが入っているかどうかという情報がK( 各情報に対してシミュレーションを100*100の計算量で行えるので、愚直にシミ…

keyword C++ 概要 ほとんど完成している数独が与えられる。空升を埋める問題。 なにせほとんど完成しているので、単に実装するだけの問題。

keyword 2分木 C++ 概要 ノード数26以下の2分木がある。(root, left subtree, right subtree)、(left subtree, root, right subtree)の順にノードを出力した文字列がそれぞれ与えられるので、(left subtree, right subtree, root)の順にノードを出力する問題…

keyword Warshall-Floyd C++ 概要 様々な通貨の為替レートが与えられる。ただし、A->BとB->Aのレートは独立である。このとき、為替によって利益を上げることができるかどうか判定する問題。 グラフの問題だと思うと、自分自身に帰る倍率1以上のルートが存在…

keyword 平面幾何 多角形 面積 C++ 概要 角柱の底面と体積が与えられたとき、高さを求める問題。 底面積を計算するだけ。いつもの様に符号付き面積で三角形をhogehogeする。