お疲れ様です。猪狩です。

ICPCの公式の方にジャッジデータが上がっていたので僕もやってみました。
自力で解けたのはEまでなのでEまでの解説を記述しておきます。
「国内予選突破するには過去問を何度もやる必要がある。コーチの指導方針が悪い」と監督からの長時間にわたるお叱りを頂いたので、後輩達が復習できるようにしておきましたのでしっかり復習して下さい。

・問題A 税率変更
問題文:
http://icpc.iisf.or.jp/past-icpc/domestic2014/#section_A

考察:
税率変更前の合計金額になるような2つの税抜価格は何があるかを全て調べます。

ループ変数を税抜価格とした2重ループを回して税率変更前の税込価格を計算して一致するか調べます。
一致したら正しい2つの税抜価格なので、その税抜価格に対して新税率を求めましょう。

求めた新税率のMAXが解になります。

[cpp]
#define REP1(i,n) for(int i=1;i<(n);i++)

int main(){
int x,y,s;
while(true){
cin >> x >> y >> s;
if(x == 0 && y == 0 && s == 0) break;
int ans = 0;
REP1(i,s){
REP1(j,s){
int item1 = i * (100+x) / 100.0;
int item2 = j * (100+x) / 100.0;
if(item1+item2 != s) continue;
int solve1 = i * (100+y) / 100;
int solve2 = j * (100+y) / 100;
ans = max(ans, solve1 + solve2);
}
}
cout << ans << endl;
}
}
[/cpp]

・問題B 連鎖消滅パズル
問題文:
http://icpc.iisf.or.jp/past-icpc/domestic2014/#section_B

考察:
正しくシミュレーションしましょう。
細かい落とし穴が何か所かあります。

消す→落とす→消す→落とす…
を繰り返して、消せなくなったら終わりという実装を行います。

消す際には出来る限り多く消せるかどうかを探した方が楽に実装できます。
なので、各列に置いてまずは5個消せるかどうかを調べ、次に4個消せるかどうか調べ、最後に3個消せるかどうかを調べましょう。

落とす際には、必ず下側から落としましょう。空洞が出来てしまう可能性があります。
例として、





という状態があった際に、上の○が落ちる所まで落とす処理をしてから下の○が落ちる所まで落とすという実装をすると





から





となり空洞が出来てしまいます。
下から処理すると





から





となるので正しく処理が出来ます。

上記の点に気を付けて実装しましょう。

[cpp]
#define PB push_back
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i–)
typedef vector<int> VI;
typedef vector<VI > VVI;
int main(){
while(true){
int n;
cin >> n;
if(n == 0) break;
VVI data;
REP(i,n){
VI buf;
REP(j,5){
int buf2;
cin >> buf2;
buf.PB(buf2);
}
data.PB(buf);
}
bool flag = true;
int score = 0;
while(flag){
flag = false;
REP(i,n){
for(int j=5;j>=3;j–){
REP(k,5-j+1){
if(data[i][k] == 0) continue;
bool flag2 = true;
REP(l,j){
if(data[i][k] != data[i][k+l]) flag2 = false;
}
if(flag2){
flag = true;
score += data[i][k] * j;
REP(l,j){
data[i][k+l] = 0;
}
}
}
}
}
if(flag){
RREP(i,n-1){
REP(j,5){
if(data[i][j] == 0){
RREP(k,i){
if(data[k][j] != 0){
data[i][j] = data[k][j];
data[k][j] = 0;
break;
}
}
}
}
}
}
}
cout << score << endl;
}
}
[/cpp]

・問題C バンパイア
問題文:
http://icpc.iisf.or.jp/past-icpc/domestic2014/#section_C

考察:
解は必ずビルの端の何処かである。
問題文の画像1枚目は0の地点の左側の高さ0が解の位置であり、画像2枚目は0の地点の右側の高さ3が解の位置である。
このように、各距離の左右の高さの位置により解が一意に求められる。

ただし、地点0以外では太陽が出るまでの時間がある。その時間を計算する必要がある。

c1

上記の画像の-1の地点は、太陽が出るまでに赤の線の分の距離(時間)が掛かる。
赤の地点は計算で求めることができる。
まず、赤の線と円の中の青の線を足すと円の半径と等しくなる。
つまり、半径から円の中の青の線を引く事により赤の線を求めることが出来る。
青の線は三角関数で求めることができる。
黄色の線と緑の線と青の線で三角形を作ることが出来る。
黄色の線は半径なので元から確定しており、緑の線は各建物の端だけを調べるので半径の絶対値を超えない整数値である。
緑の線の箇所はcosΘになるので、計算するとΘを求めることが出来る。
青い線の箇所はsinΘ*半径になるので、求めたΘを使い計算することにより青い線の長さが求まります。

全ての建物の端の高さ+円が出るまでの距離のうち、最も小さい箇所が解となります。

[cpp]
#define REP(i,n) for(int i=0;i<(n);i++)
typedef pair<int,int> PII;
const int OFFSET = 20;
int main(){
while(true){
int r,n;
cin >> r >> n;
if(r == 0 && n == 0) break;
PII data[41];
REP(i,41){
data[i] = MP(0,0);
}
REP(i,n){
int xl,xr,h;
cin >> xl >> xr >> h;
xl += OFFSET;
xr += OFFSET;
for(int j=xl; j<=xr; j++){
if(j!=xl) data[j].first = max(data[j].first, h);
if(j!=xr) data[j].second = max(data[j].second, h);
}
}
double ans = 100.0;
int xl2 = OFFSET-r;
int xr2 = r+OFFSET;
for(int i=xl2; i<=xr2; i++){
int diff = abs(i-OFFSET);
double y = r * sin(acos(diff / (double)r));
if(i != xl2 ) ans = min(ans, r-y+data[i].first);
if(i != xr2 ) ans = min(ans, r-y+data[i].second);
}
printf("%.4fn", ans);
}
}
[/cpp]

・問題D 暗号化システム
問題文:
http://icpc.iisf.or.jp/past-icpc/domestic2014/#section_D

考察:
各文字について、暗号化有り無しの2通りが考えられる。
文字列の長さは最大で20なので、2^20の全てのケースについて試せばよい。
(ICPCのルールなら。僕のノートパソコンで大体30秒から1分掛かります)

全てのケースに対し、暗号化を再度行う。
入力で受け取った暗号化済みのデータと同じならその文字列は正しいので配列に入れておく。

最後に配列の長さとソートした後の前後5個を表示すればよい。
多分高速化可能なのでもう少し工夫できる点があると思います。

[cpp]
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
int main(){
while(true){
string str;
cin >> str;
if(str == "#") break;
set<string> ans;
REP(i,(1<<str.length())){
string use = str;
bool change = false;
REP(j,str.length()){
if( ((1<<j) & i) && use[j] != ‘z’){
change = true;
use[j]++;
}
}
if(!change && i != 0){
continue;
}
string bufstr = use;
REP(j,25){
REP(k,use.size()){
if(use[k] == ‘a’+j+1){
use[k]–;
break;
}
}
}
if(use == str){
ans.insert(bufstr);
}
}
vector<string> ans2(ALL(ans));
cout << ans2.size() << endl;
if(ans2.size() <= 10){
REP(i,ans2.size()){
cout << ans2[i] << endl;
}
}else{
REP(i,5){
cout << ans2[i] << endl;
}
REP2(i,ans2.size()-5,ans2.size()){
cout << ans2[i] << endl;
}
}
}
}
[/cpp]

・問題E 橋の撤去
問題文:
http://icpc.iisf.or.jp/past-icpc/domestic2014/#section_E

考察:
最初は解になる点を列挙して…とやったが、何も考えずに全探索することで解を求めることが出来る。
全ての点から探索する際に、下記の通り求める。
また、橋の数がn-1個しかないので与えられるグラフが木である。
木なら幅優先でも深さ優先でも最短路を求めることが出来る。

・移動先の点が行き止まりの場合
その点に行くと無駄に戻ることになる。なので、その点の橋を撤去する。
橋の長さ分のコストが必要。

・移動先の点が行き止まりでない場合
その先の点の橋を撤去しないといけないので、必ず行って帰って撤去しないといけない。
行って帰って撤去なので橋の長さ*3のコストが必要

これでコストを計算すると、全ての点から橋を撤去してスタートに戻った場合のコストが求まる。
作業を終える島が異なってもよいので、戻ってきた際のコストを引く事により解が求まる。
戻らなくていい場合は帰るコストが無くなり行って撤去なので橋の長さ*2になる。
ということは、スタートからゴールになるうる点の距離を引く事により解が求まる。

ただし、行き止まりの点は解になりえないので行き止まりの点はゴールとして選択してはならない。
行き止まりの点はその一歩前の点で橋を撤去するだけの方がコストが安く済むからである。

[cpp]
#define PB push_back
#define REP(i,n) for(int i=0;i<(n);i++)
typedef pair<int,int> PII;
const int MAX_V = 800;
vector<PII> G[MAX_V];
void add_edge(int to, int from, int cost){
G[to].PB(MP(from,cost));
G[from].PB(MP(to,cost));
}

int main(){
while(true){
int n;
cin >> n;
if(n == 0) break;
VI d1,d2;
REP(i,n){
G[i].clear();
}

REP(i,n-1){
int buf;
cin >> buf;
d1.PB(buf);
}
REP(i,n-1){
int buf;
cin >> buf;
add_edge(i+1,d1[i]-1,buf);
}
int ans = INF;
REP(i,n){
int costs[800] = {0};
int allcost = 0;
queue<PII> que;
que.push(MP(i,0));
while(!que.empty()){
int idx = que.front().first;
int nowcost = que.front().second;
costs[idx] = nowcost;
que.pop();
REP(j,G[idx].size()){
int to = G[idx][j].first;
int nextcost = G[idx][j].second;
if(to == i || costs[to] != 0) continue;

if(G[to].size() == 1){
allcost += nextcost;
}else{
allcost += nextcost*3;
que.push(MP(to,nowcost+nextcost));
}
}
}
REP(j,n){
if(i==j) continue;
ans = min(ans, allcost – costs[j]);
}
}
cout << ans << endl;
}
}
[/cpp]

5 のコメント

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)