解法 やるだけ。実は入力は正なのでもうちょっと省略できる。

解法 Codeforces Beta Round #24-E: Berland colliderと同じで二分探索。終点で一致するときはEPSを使う必要があるけど、二分探索の中でEPSを使ってはいけない。というかこれは二分探索の基本ですから。 感想 問題文を解釈するのに一番時間がかかった。問題…

問題概要 4桁の数字列が与えられる。各数字を1桁以下書き換えて、下界が1000、上界が2011の単調非減少数列を作る問題。 解法 どう考えてもGreedy。書くだけの問題だけど、書き換える場合と書き換えない場合の処理を分けてやろうとした結果バグを埋め込んで落…

問題概要 X,Y,Zの3つの物質がある。X aグラムからbグラムのYが得られる。Y cグラムからdグラムのZが得られる。Z eグラムからfグラムのXが得られる。有限量のXから無限にZが得られるかどうか判定する問題。 解法 POJ-2240:Arbitrageに似た問題な気がして、同…

解法 典型的なライツアウト。サイズが小さいのでBruteForceで。

解法 ライブラリがそれなりにあれば後はやるだけ。円は凸なので、線分が円の内部に含まれるかどうかは端点だけを見ればよい。

keyword 整数 BruteForce Java 問題概要 整数N(三角錐数(i*(i+1)*(i*2)/6で表せる数)の和で、Nを越えない最大のものを求める問題。テストケースは10^3個以下。 解法 N以下の立方数と三角錐数をたくさん作ってその組み合わせを全部試す。一つのテストケースに…

問題概要 N( 解法 Stirlingの近似公式を使う。小さい部分ではΓ関数を使った。

解法 ゲームと言いつつプレイヤーに選択の余地が無い。

解法 やるだけ。

問題概要 ブロックがいくつも積まれている。重心を計算して安定であるかどうか判定する問題。 解法 実装するだけ。処理が微妙に面倒くさい。重心はx座標だけ計算すればよい。あと、適当にEPSとか使ってるけど境界ギリギリの所を狙われた場合大丈夫かどうかの…

問題概要=解法 (a+b,a)=a+bとなるのはa=1 or b=1のときのみ。

解法 動的計画法の練習問題というか入門問題。

解法 入力読み取るのが面倒。問題自体はやるだけ。

keyword 動的計画法 Java 問題概要 1~Nまでの数のうち、a*x + b*y(x>=0 and y>=0)で表せない数がいくつあるか求める問題。N,a,bは全て10^6以下。 解法 典型的な動的計画法。表し方が何通りあるかも(modの形で)求めることができる。

解法 縦を固定して数え上げるだけ。

解法 mod 10の世界でやるだけ。

解法 どんな方法でやっても通ると思う。

解法 やるだけ。ただし入力は馬鹿みたいに大きい。

keyword 動的計画法 Java 問題概要 腹を空かせた少年がいる。少年は前日に弁当を買えなかったならば、必ず弁当を買える。前日に弁当を買えていたら、その日弁当を買える確率は前日の半分になる。N( 解法 連続して弁当を買える確率は指数的に減少する(もう少…

解法 どう見てもやるだけ。

解法 ホーナー法で。別に普通にやっても通るはず。

解法 再帰で処理する。

解法 UnionFindするだけ。

keyword ゲーム C++ 問題概要 特殊な形をしたボード上にいくつか石が置いてある。プレイヤー二人は連続する石を1個以上取り除くことができる。最後の石をとったものが勝ち。最善を尽くしたとき先手と後手のどちらが勝つか判定する問題。 解法 盤面の状態が2^…

keyword Greedy C++ 問題概要 図のような区画を連続するx[1], x[2], ..., x[n]個のブロック(4近傍でつながってる塊)に分割できるならその分割を出力する問題。 解法 もちろんいつでも分割できる。境界の部分が連続するようにくねくね曲げて置いていく。 実装…

問題概要 いわゆるhit and blow。 解法 絶対過去に解いたことあるはずだと思っていたけど意外とそうでもなかった。とりあえず候補が10^4個以下しかないんだから全て試す。BruteForceは素晴らしい。

解法 やるだけ。コンテスト中に書いたコードはキャリーを配列で持っているけど、ランクの高いやつから処理すればそれもいらない。

解法 やるだけ。適当にコンパレータを定義してstable_sortしてもよさげ。