ICPC
問題 数直線状にn個の点が並んでいる。 一番左側の点のx座標は0である。 各二点間の距離を表す行列(の上半分)が、要素だけを大きい順に並べた形で与えられる。 このときもとの行列を復元せよ。 制約条件 n≦18 d[i]≦400
問題 空から風船が落ちてくるので、それを台車で回収したい。 それぞれの風船は、時間t[i]にx座標x[i]の地点に落ちる。 このとき台車はちょうどx[i]の位置にいる必要がある。 台車は回収した風船を、x座標が0の地点の小屋に入れることができる。 台車には風…
E,Fがどっちも通せそうで通せず、チームの順位は実力を微妙に出し切れなかったものになってしまったなという感じ。 A,D,Fをkohyatohが担当、B,C,Eをおぎえさんが担当。 自分は雑用を担当。Fの解法だけ出したけど、ほとんど貢献してない気がする。 以下個人の…
練習会復習。 問題概要 nxmマスのグリッドがある。 '.'は何もないマスで、'*'は石のあるマスである。 i行j列に爆弾を落とすと、同じ行の石全ておよび同じ列の石全てが破壊される。 全ての石を破壊するのに必要な爆弾の最小の数を求めよ。 n,m≦25
問題概要 n件の家がm本の道によりつながっている町がある。(直接または間接的につながっていない家もある) この町にサンタがl個のプレゼントを配る。 サンタは最初町のどの家にも降りることができる。また、サンタが家から家に移動するのにかかる時間はそ…
問題概要 日本語なので本文参照。(http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1157&lang=jp)線分に沿って大玉を転がす。 平面上には直方体が、辺が各座標軸に平行なように、いくつか配置されている。 直方体にぶつからない大玉…
問題概要 日本語なので本文参照。(http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1161&lang=jp) ACM + IBM = ICPC のような覆面算の答えの総数を求めよ。 一つのアルファベットには0〜9の一つの数字が対応する 異なるアルファベッ…
問題概要 辺に英小文字からなる呪文が書かれた有向グラフがある。 スタートからゴールまでグラフを辿ったときに得られる、「それまでにたどった辺の呪文を並べた」文字列のうち、辞書順で最も先頭に来るものを最強の呪文と呼ぶ。 最強の呪文が一意に決まる場…
問題概要 テトリスのようにピースを積み重ねてオブジェを作るとき、そのオブジェが安定かどうかを判定せよ。 ただしオブジェが安定であるとは、全てのピースに対して、 そのピースおよびそのピースが支える全てのピースをあわせた重心が、そのピースと、それ…
問題概要 n番目の正四面体数はn(n+1)(n+2)/6で表される。 10^6未満の整数Nが与えられたとき、Nを正四面体数の和で表すのに必要な、最小の正四面体数の個数を求めよ。 また、Nを「奇数の正四面体数」で表すのに必要な、最小の「奇数の正四面体数」の個数を求…
問題概要 グリッド上に描かれた迷路が与えられる。このとき、ゴールまでの最短の道のりを求めよ。 迷路は各グリッドの壁の情報によって与えられる。
まさかの参加記より先に解説記事。参加記が永久に書かれない気がしてきた。 問題概要 正方形を座標平面状に、軸に平行に、かつ新しく並べる正方形は、既に並べた正方形のどれかと一辺がちょうど重なるように並べる。 2番目の正方形から、「(それまでに並べ…
圧倒的敗北感…… というか何だろう。モチベーション下がりまくり。 チームメイトさんは授業以外で3週間全く問題解かないどころかチームwikiすら見ないし。 大体、学習ブログ最後に更新したの4月じゃねえかよ。 何か言ってくれないと僕もどうしたらいいのか判…
今日は25:00からCodeforcesのラウンド。起きてられるかなあ。 No. Title 分類・解法 1488 TEX Quotes String manipulation 2366 Sacrament of the sum Straight forward 2552 Assistance Required Straight forward 2509 Peter's smokes Straight forward 26…
ICPC 2009 東京予選 Problem J 問題概要 n×n(n≦5)セルのライフゲームのセル全て死滅させるのにかかる最小ターン数を求める。ライフゲームのルールは通常と同じである。すなわち、 ターン開始時に、生物のセルについて、周囲8セルのうち、2つまたは3つが生…