2010 ICPC国内予選 A.角角画伯，かく悩みき

ICPC 実装問題

まさかの参加記より先に解説記事。参加記が永久に書かれない気がしてきた。

問題概要

正方形を座標平面状に、軸に平行に、かつ新しく並べる正方形は、既に並べた正方形のどれかと一辺がちょうど重なるように並べる。


2番目の正方形から、「（それまでに並べた正方形の中で）それが接する正方形の番号」、および「上下左右どの向きに接するか」が与えられたとき、全ての正方形を囲う座標軸に平行な長方形の幅と高さを求めよ。

続きを読む

2010 ICPC国内予選 C.ポロック予想

ICPC 動的計画法

問題概要

n番目の正四面体数はn(n+1)(n+2)/6で表される。
10^6未満の整数Nが与えられたとき、Nを正四面体数の和で表すのに必要な、最小の正四面体数の個数を求めよ。
また、Nを「奇数の正四面体数」で表すのに必要な、最小の「奇数の正四面体数」の個数を求めよ。

続きを読む

2010 ICPC国内予選 D.ぐらぐら

ICPC 実装問題

問題概要

テトリスのようにピースを積み重ねてオブジェを作るとき、そのオブジェが安定かどうかを判定せよ。


ただしオブジェが安定であるとは、全てのピースに対して、
そのピースおよびそのピースが支える全てのピースをあわせた重心が、そのピースと、それを支えるピースの接する部分のうち、最も左のx座標から最も右のx座標の間に含まれることをいう。（境界は含まない）

  • 最も下のピースは地面に接している。
  • ピースとピースは面がぴったりくっついている。
  • ピースは樹状に積み重ねられている。

ことを仮定してよい。

続きを読む

2010 ICPC国内予選 E.最強の呪文

ICPC 文字列 探索 ダイクストラ法

問題概要

辺に英小文字からなる呪文が書かれた有向グラフがある。
スタートからゴールまでグラフを辿ったときに得られる、「それまでにたどった辺の呪文を並べた」文字列のうち、辞書順で最も先頭に来るものを最強の呪文と呼ぶ。


最強の呪文が一意に決まる場合それを、決まらない場合"NO"を出力せよ。

（あ、なんか要約が適当……）

続きを読む

第4回ニコ生オープン!

TopCoder 参加記録

心折れる。なんかICPCでの負けを引きずってる。
練習しても全く実力向上しないし、僕みたいなのは何やっても無駄なのかもなあ。


今年中の目標達成できなかったらとっとと死んだほうがいいな。

Result

最下位 -50 / Challenge Succeeded / SystemTest Failed / Unopened

続きを読む

TopCoder Open 2010 Round 3 Medium.TheChroniclesOfAmber

TopCoder

問題概要

王子達のそれぞれの初期座標と、目的地の座標が与えられる。


王子達は、他の王子の居る場所へ、好きなタイミングで一瞬でテレポートできるとき、全ての王子達がそれぞれの目的地へたどり着くのに必要な最小の時間を求めよ。


王子の数は50人以下である。

続きを読む