Petrと7人の日本人が居る部屋。 250 なんか昨日(今日)のCodeforcesのD問題みたいに見える 2点選んで直線を決めるだけ コーナーケースとして、どの2点を選んでも条件を満たす直線にならない場合があるけど、それの答えはn-1になる 書いて提出 550 グラフ上で…

久しぶりに参加した。 A 2*2のアミュレットを回転させる問題 setに突っ込んで最後に4で割るだけでは？ よく考えると回転して重なる場合があるから4で割るのはダメで、ちゃんと今までに出てきてないアミュレットかどうかを判定してやらないといけない 書いて…

2週間くらい前にICPCアジア地区予選東京大会に参加してきました。 結果はA,B,D,E,F,Gを解いて9位でした。私が担当した問題はB,G,Hです。 BではDiv1のEasy程度の簡単なDPの問題のはずなのに解くのに非常に時間をかけてしまい、しかも3WAも出してしまいました…

Petrとかwataさんと一緒の部屋。 250 サイコロの問題 とりあえずkは全通り調べる。サイコロの対面を足した数値がkとなるような数値の個数をmとするとmC3を求めればいいだけ。 サックリ書いてサブミット。 600 trieの問題 良く分からん。文字数が最大16って所…

250 期待値の問題か 互いに素な場合は明らかに周期がn 互いに素で無い場合はgcd取ればいいんじゃないの？ 書いた、サンプルと一致、サブミットした。 550 問題文長くてめんどい しかも文字列の実装ゲーかあ TLEが心配だけどそのままstringでやる 実装中にス…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4872 問題 点がN個あるので辺が交差しないユークリッド最小全域木を求めよ。 1 解法 クラスカル法かプリム法を使って最小全域木を求めるだけ。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4871 問題 高さの違う高層ビルをN個建てる。ただし、i 解法 DP[n][pos]を考える。DP[n][pos]はn番目までのビルを置いたときにhi

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4870 問題 区間がN個あるジェットコースターがある。ある人がこのジェットコースターに乗るのだが、怖さの閾値Lを越えない範囲でなるべく楽しみたい。ある区間で目を開けているとFi楽し…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4869 問題 長さNの数列がある。そのsubstringの総和の最大値を求めよ。 1 解法 左端から見ていって、総和が負になったら0にもどす。これをしていって最大になった物が答え。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4868 問題 leading 0が許された数値がある。その数値を回文にするためには最小いくらの数値を足さなければならないか？ 2 解法 左側半分を固定してそれに合わせるように右側半分を足して…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4867 問題 すべての要素が1か0で構成されたN*M行列がある。その中の正方形で全て1で構成される最大の正方形の辺の長さを求めよ。 1 解法 ヒストグラムの長方形の最大面積を使って求めた…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4866 問題 三角形がある。AB,BC,CAからθずらした直線を考える。θを適切に設定した時にその3っつの直線は一ヶ所で交わる。その場所を求めよ。 解法 頑張って手計算するか三分探索で求める…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4865 問題 N*Mの行列がある。各成分は[0,100]の値になっているか空欄になっている。各列の和と各行の和を与えるので元の行列を復元せよ。ただし、値が一意に定まらない箇所は-1と答えよ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4864 問題 f(x):=xの2進数表記で1の個数という関数を考える。Ni=f(Ni-1)とするとこの数列は1に収束する。このとき、初めて1になったiをKとする。[LO,HI]の区間でK=Xとなるような数値は何…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4863 問題 Nチームが参加しているコンテストが開催された。各チームに風船をK個配りたいのだが、部屋Aからの距離はDA、Bからの距離はDBとなっている。各部屋には風船がA個、B個ある時、…

PetrとかEgorとかRAVEmanとかと一緒の部屋 300 Hanakoですか… 問題の意味を理解するのに結構時間がかかった 任意の3っつを選んでどんな順番でも同じものになればいいんじゃないの？ 書いた。サンプル通った。サブミット。 500 サイコロを転がす問題 部室のサ…

laycurseさんとかsky58さんとかと一緒の部屋 250 状態がループする期待値の問題か いつも通り、無限等比級数の和の公式を使えばいいんじゃないの 普通に書いた。なんか確率の合計が0.5になってるんでとりあえず2倍したらサンプルと一致 提出。もう15分以上た…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4862 問題 一部が緑、赤に塗られたn*mのボードがある。ボードの各マスには数値が書かれている。そのボードにハイパーナイトを置いて行き、ハイパーナイトが置かれているマスの数値の合計…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4859 問題 256人が戦うトーナメントが複数回ある。ある人が複数のトーナメントでw回勝って、l回負けた。その人が平均どのくらいのラウンドまで進んだかを求めよ。 0 解法 まずl=0でwが8…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4858 問題 [1,k]の数値を使ったn*nの行列A、Bがある。Aの行列の一か所を選び[1,k]の数値に変えるという操作を繰り返してBの行列にする。ただし、数値を変化させたときに対象行列となって…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4857 問題 [1,m]の整数で表現される長さnの数列がある。普通のstackでpush,pop,topを使って与えられた数列を再現することにする。最低何回のpushが必要か？ 1 解法 DPで解く。dp[use][le…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4856 問題 8*8のフィールドに障害物と2*2の4っつの箱がある。初期状態から上下左右の方向に重力をかけて箱を動かしていく。いくつの状態に遷移しえるか？ 解法 やるだけ。初期状態は(基…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4855 問題 N次元で各次元がフィボナッチ数となっている超直方体がある。あるN次元の超直方体を作るためには最低何個の超直方体が必要か？ 1 1 解法 greedyにやるだけ。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4854 問題 A-Zのおもりと天秤ばかりがある。各おもりの重さは文字をアスキードコードで表したときに1が出てくる個数*500+0が出てくる個数*250となる。(ただし、leading 0の部分は除く)。…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4853 問題 n個の数値がある。0以外の数値の個数-0の個数を答えよ。 1 解法 英語を読むだけ。

250 問題を読む。というか図を見ればだいたい何をやりたいか分かるな ちょっと考えると、あるindexを使う方法は2通りしか無いんで2SATに落ちる とりあえずdfsで書いた。サンプルも通った。 よく考えるともっと計算量減らせるなあと思いつつ、最大ケースを試…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4825 問題 s/(n+1)をせよ。 1 1 解法 英語をしっかり読むだけ。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4823 問題 n*nの行列上で二人でゲームをする。各プレイヤーは自分の手番で行列の一番右の列か一番下の行の総和が偶数の場合にその列を消すことができる。列を消せなくなったプレイヤーが…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4822 問題 木がある。葉同士の距離を与えるので葉以外の頂点が何個あるか求めよ。 3 答え 解法 大前提として葉同士の距離が決まっていると木自体が決定できる。なので、実際に木を復元し…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4821 問題 R*Cの各グリッド上にゲームセンターがある。各ゲームセンターは一つのゲームを提供し、そこをホームにしているゲーマーがいる。各ゲーマーは全ての種類のゲームをプレイしたい…