けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ-ICPC250点

AOJ 1610 竹の花 (ICPC 国内予選 2016 C) (250 点)

面白い。けど問題文長い...。問題概要を短くまとめてみた。 問題へのリンク 問題概要 正の整数 が与えられる。 あなたは、 以上の整数を 個用意する ( とする)。この 個の整数のスコアを、以下の条件を満たす最小の整数 として定める。 は のいずれでも割り…

AOJ 2629 Manhattan (JAG 夏合宿 2014 day2-A) (250 点)

伝説のりんごさんセットの 1 問目 問題へのリンク 問題概要 二次元座標平面上において、 座標と 座標のうちの少なくとも一方が整数であるような点からなる集合を「道路」と呼ぶ。 道路上の 2 点 のユークリッド距離が実数 で与えられる。 点 から道路のみを…

AOJ 2600 Koto Distance (JAG 夏合宿 2013 day2-A) (250 点)

面白かった 問題へのリンク 問題概要 二次元平面上に 個の点がある。これらの各点 に対し、 を満たす点 に電波が届く。 から までの長方形区間全体に電波が届くかどうかを判定せよ。 制約 考えたこと 全体を覆っているとき、以下のいずれかは成立しているこ…

AOJ 2386 Sightseeing Tour (JAG 冬合宿 2010 day4-H) (250 点)

完全グラフはどのように向きづけしてもハミルトンパスが存在するというね!!! その証明はすごく楽しいと思う!!! 問題へのリンク 問題概要 頂点数 の完全無向グラフが与えられる。今、すべての辺に向きをつけたい。各 i, j に対して 頂点 i から頂点 j …

AOJ 1602 ICPC 計算機 (ICPC 国内予選 2015 C) (250 点)

こういうのをサッと書けるようになりたいね 問題へのリンク 問題概要 ((6 + 2) + 1) + (7 * 6) + 3 のような計算式が以下のような入力フォーマットで与えられる。これを構文解析して計算結果を出力せよ。 演算子は「+」「*」のみ 数値は 1 桁のみ 10 + .+ ..…

AOJ 1167 ポロック予想 (ICPC 国内予選 2010 C) (250 点)

いわゆる、重複ありのナップサック問題 問題へのリンク 問題概要 整数 を最小個数の四面体数 (重複あり) の和として表せ。 解法 四面体数は、mC3 の形で表される。 重複ありのナップサックも、うまくやれば、種類数の線形オーダーで効率的に解けることの練習…

AOJ 2610 Fast Division (JAG 夏合宿 2013 day3-D) (250 点)

人工的過ぎる設定であまり自然じゃない問題だけど、整数の整除についての注意点を学べる教育的良問ですね。 問題へのリンク 問題概要 整数 が与えられる。 を 回二乗した数より大きい最小の素数を とする。 を で割ったあまりを求めよ。 制約 < 1000 考えた…