整数配列が与えられて、任意のペアについて、1以外の公約数を持たないペアの割合を、6/(PI^2)で近似する。このときPIの値を答えよ、という問題。 printfがあると幸せになれます。Javaにもあるような気はするが...。 Javaのprintfを使って通し直した。自分で…

N個のデバイスが与えられて、使用可能な電力量が与えられる。デバイスのon/offのシーケンスが与えられるので、許容量を超えるかどうか、超えない場合は最大使用量を答えよ、という問題。 ただの実装。次の年の簡単な問題。(こういうのやることに意義は余りな…

箱が適当に積まれているので、同じ個数積むように並び替えるとき、必要な最小移動回数を答えよ、という問題。 積まないといけない個数を求めて、超過分を移動させるだけ。 何かひっかけかと思って色々考えたが、何も浮かばなかったのでそのまま投入。1997年…

ある都市からある都市への航空便の値段とその有無が与えられるので、開始都市から終了都市までK回の移動の最小コストを求めよ、という問題。 都市数が10でKが高々1000という状況なので、何も考えずにDPするだけ。 どこかに計算量的にまずいところがあってTLE…

5000個程度の長方形の座標が与えられるので、他のいずれかの中に完全に含まれるものの個数を答えよ、という問題。 自明解は5000^2で、多分間に合わないと信じる。logNを出す必要があるので、ソートか何かかなぁ、という感じ。 取り敢えず、左から順番になめ…

整数Nと使って良い数字のリストが与えられるので、使って良い数字だけからなる最小のNの倍数を答えよ、という問題。 先頭から桁を一つずつ追加しつつ、余りをメモしつつ、な感じでBFSする。状態数はNで停止するはず。BFSなので桁数が一番小さいのが出るので…

二つの文字列が与えられるので、それぞれから任意の文字を削って同じ文字列になるようにするとき、残る文字列のうち最長のものの長さを答えよ、という問題。 長さの指定がないので、適当にやっても十分間に合うんだろうか、からテスト開始。取り敢えず長さN…

商品の値段と売ることのできる期日のリストが与えられる。一つのものを売ると時間が一つ進む。売ろうとしたものがすべて売れるとして、売値の合計の最大値を答えよ、という問題。 最後から順に何を売るか割り当てていけば良く、まだ売ることのできるすべての…

N人が座っている円卓で、隣接する二人をスワップするという操作を何回やれば、両隣の人が逆転した状態にできるか答えよ、という問題。 N人をK人とN-K人に分けて、それぞれをスワップ操作で逆順にすることを考える。K人のスワップは、2K-3回のスワップとK-2人…

NxMの格子点上にある都市において、上下左右斜めの8方向のみに道がある状況で、すべての都市を一度ずつ巡る最短閉路長を求めよ、という問題。 NxM回移動する必要があり、距離1の遷移より短い遷移はない。なので、距離1の遷移のみで一筆書きできるならば、NxM…

整数要素をK個入れた状態で、I番目に小さいものを答える、という処理を、要素を入れる処理と並行して行う。出力されるものを答えよ、という問題。 要素を適宜挿入しつつ、I番目を高速に答えられますか、という問題。ただしI番目に小さいもの、というのは連続…

複数の水槽の置いてある高さとサイズが与えられる。全体に入っている水の総量が与えられたとき、水面の高さを求めよ、という問題。小数点以下2桁求める。 厳密解を求めるなら、出てくる高さ座標すべてでソートして、各区間での断面積の和を持っておけば、区…

1と0からのみなるNの倍数を答えよ、という問題。 先頭の文字は必ず1なので、それを基準に考える。次の桁がAならば余りは10倍してA足したものをNで割った余りになる。(これは高々N個の状態からなるオートマトンで書ける。)余りが0になるまでの遷移をBFSして、…

N!が何桁の数であるか答えよ、という問題。Nは10M程度まで。 クエリが複数個くるので、取り敢えずメモをしておく。桁数はlogで求めることができる。(というかそういう定義になっているはず。)intで10M個持つことはできるが、10M回logを呼ぶとTLEするので、あ…

閉路のない有向グラフが与えられる。すべてのノードは最初は印がついていない状態とする。任意のノードを開始点として印をつける。印をつけたノードから隣接する印のついていないノードへの移動が可能で、そのノードには印がつく。すべてのノードに印をつけ…

モチベーションが出なくて、楽な道に逃げたつもりが、さらに面倒なコーディングという結果に。 250 先頭が0にならないように与えられた数字の任意の異なる二桁をスワップするという操作をK回やってできる整数のうち、最大のものを答えよ、という問題。 高々7…

高々6桁の整数が二つ与えられるので、後者を任意に長さ1以上の部分に切り分ける。その合計値が前者を超えずに前者に一番近付くような切り分けを答えよ、という問題。何もない場合や、複数ある場合はその旨答える。 入力には0で開始する整数は来ない、と書い…

整数Mと分数A/Bが与えられるので、A/B素数組について、P*Qが最大になるものを答えよ、という問題。 Mが100kでAとBが1k程度なので、素数は10kくらいまで求めておけば良い。後は二重ループで全探索するのを適宜枝狩りするだけ。時間がかなりシビアなので、真面…

整数Nが与えられるので、非負整数AとBについてA^3+B*(B+1)*(B+2)/6のうちN以下で最大のものを答えよ、という問題。 AとBはいずれも高々100程度なので、全探索するだけ。もっと複雑な式で、AとBが取り得る範囲が10000個ずつくらいあるケースを考えるなら、そ…

1/Kの形の分数N個の総和が1未満の最大になるような分母列を答えよ、という問題。 できる限り大きいものをN個greedyに選択するだけ。greedyで良い理由は不明。

携帯電話のボタンの数と割り当てるキーの種類が与えられ、それぞれのキーが何回くらい入力されるかの頻度が与えられるので、最適キー配置を答えよ、という問題。 連続する任意のキー群を一つのボタンに割り当てたときのコストを事前に計算しておいて、全体と…

N!の末尾に続く0の個数を答えよ、という問題。 N!が2で割り切れる回数は5で割り切れる回数よりも圧倒的に多いので、5で割り切れる回数を数えればおしまい。

やり直し。 1050 開始点を固定して考えると分かりやすいので、それを開始点の数だけループしてみる。現在位置がiでjへ遷移するための遷移行列は、元のグラフの枝の有無から作成可能。ここでjが開始点になるものの数をカウントすればループの個数が分かる。つ…

予想通り落っこち。しかも最下位だった。チャレンジ一つ成功させるのは必須だったので、仕方ないっちゃ仕方ない。 250 木が何本か植えられている状況で、木を矩形のフェンスで囲むことを考える。木を切ることで作れるフェンスの長さと、木の位置が与えらえる…

スコアと難易度に相関関係はなさそうなセット。方針は一瞬で立つが具体的に話が進まない、というのは難しいのは間違いではないが。 250 配列を、ある要素を先頭または末尾に移動する、という処理でソートするのに必要な最小ステップ数を答えよ、という問題。…

肉を切らせて...。次回骨を断たれます。 250 NとKの偶奇は一致するとして、紙をNxNのグリッドに分け、中央のKxKの部分を切り抜く。これを残った部分に再帰的に適用する。最終的に指定された領域がどういう形状か答えよ、という問題。 指定される範囲が狭いの…

FFTはどうかと思う。代替案があればいいのだが。 250 等間隔に並んだ棒の高さが配列で与えられる。棒の頂点から見える他の棒の頂点の数の最大値を答えよ、という問題。 intが溢れるので、longで計算しましょうという問題。割り算は怖いから掛け算にして解く…

シードもらったのでここから参加。普通のDiv1レベルのはず。確かもらったシードが130番目で、結果も130番。安定しているっていうんだろうか、これ。 250 K個以上の連続する整数列で合計がNになるものを答えよ、という問題。 色々力技で解いたけれど、M個以上…

思っていた以上に間隔があいたのか、それとも2月が短かったのか。 250 整数配列が与えられる。A,B,Cの三人で、Aがまず配列を二つに分け、Bが二つの配列のうちどちらかを二つに分けるという処理を行い、C,B,Aの順番で好きな配列を選ぶ。配列の値の総計がスコ…