【No.021】「Live archive 7232 Path」
2015年、韓国のアジア地区予選
DaejoenのG問題です。
2015 ACM-ICPC Daejeon Regional
簡単な問題概要
ヒストグラムの形をした多角形があります。
どの辺もx軸かy軸に平行です。
左下の点をスタート地点とします。
多角形の辺上に、複数のゴール地点があります。
それぞれのゴール地点までの最短路を求めて、その総和を出力してください。
解法
すべてのゴール地点と多角形の頂点をイベント点として列挙します。
このとき、多角形の辺の上を右下の地点から時計回りにぐるっと一周するような順番に並べておきます。
あとは蟻本のp234のような凸包を行うだけです。
はじめに空のスタックを用意し、そこにイベント点を順番に追加していきます。
ただし、新しいイベント点をスタックに追加するたびに、凹んでいる部分を除去していく必要があります。
イメージ用スライド
実際にACしたソースコード
【No.020】「ICPC 2016 国内予選 E問題 3Dプリント」
問題文はこちら
1つの候補を1つのノードとみなして、実際に設置したとき共通部分をもつもの同士にエッジを張ります。エッジのコストは、
S*S*12 - (その2つを重ねて設置してできる多面体の表面積)
にします。※この2つを設置することで全体の表面積がいくつ減らせるかを表す値です。
あとはこのグラフの中で長さKのパスか閉路の中でコストの和が最大のものを探索することで解くことができます。
問題文に書いてある3条件をよく読むと、簡単な深さ優先による全探索でも計算量が全く増えないことがわかります。
下の図は、2つの直方体を設置して、それを1つの多面体として見たとき、その多面体の表面積を求めるときの例として僕が作った図です。
上からみると、面積は4、正面からみると3、横からみると2なので、
表面積は ( 4 + 3 + 2 ) × 2 = 18 となります。
この方針なら、それぞれの直方体のペアに対して、O(1)で計算できます。
僕が実際に本番で書いたコードです。
【No.019】「 SRM 691 div1 easy 」
コンテスト中に書いたコードがいろいろと無駄なことをしていたので、書き直しました。(かなり短くなりました。)
using namespace std;
class Sunnygraphs {
public:
map<int,bool> mp;
void func(int &cnt,int p,vector<int> &a){
while(!mp[p])mp[p]=true,cnt++,p=a[p];
}
long long count(vector <int> a) {
int n=a.size();
int ac=0,bc=0,cc=0,dc=0;
mp.clear();
func(ac,0,a);
func(bc,1,a);
mp.clear();
func(cc,1,a);
func(dc,0,a);
int C=n-ac-bc;
long long ans=(1LL<<n);
ans-=((1LL<<bc)-1LL)*(1LL<<C);
ans-=((1LL<<dc)-1LL)*(1LL<<C);
if(ac==dc)ans-=(1LL<<C);
return ans;
}
};
変数acは、エッジを向有としたとき( i 番目のノードから a[ i ] 番目のノードに向かってエッジを張る)に、0のノードから到達可能なノードの個数です。
変数bcは、0のノードからは到達可能だけれど、0のノードからの到達が不可能なノードの個数です。
似たような感じで、ccは1から到達可能、dcは0から到達で1から到達不可能なノードの個数です。
acとdcが等しいときは、0のノードと1のノードが異なる連結成分に存在していることになります。
【No.018】「 AOJ-ICPC 550 引っ越し 」
House Moving | Aizu Online Judge
この問題を解くためには、
元の数列の総和から、「その数列から任意の長さの部分増加列を取り出して、その増加部分列の要素の総和を最大化したときの値」を引けばよいです。
サンプル1ならば、
元の数列 : { 1, 4, 2, 3 }
元の数列の総和 = 1+4+2+3 = 10
総和が最大の増加部分列 : { 1, 2, 3 }
増加部分列の総和 = 1+2+3 = 6
よって、10-6=4が答えになります。
※要するに増加部分列に採用されなかった項は、体力を消費して動かすことになる。
サンプル4ならば、
元の数列 : { 6, 2, 1, 3, 8, 5, 4, 7 }
元の数列の総和 = 6+2+1+3+8+5+4+7 = 36
総和が最大の増加部分列 : { 2 , 3 , 5 , 7 }
増加部分列の総和 = 2 + 3 + 5 + 7 = 17
答え = 36 - 17 = 19
総和が最大になる増加部分列を求める問題をO( n^2 )で解く場合、どの項に着目しているかを状態に持って、次にどこの項を採用するかで遷移するDPになります。
このとき、遷移にO(N)かかってしまうところを、セグメントツリーやBITをつかうことでO( log N ) で遷移できるようになります。
【No.017】「AOJ-ICPC 500 それぞれの感想 前編」
aoj-icpc 500 が埋め終わりました。 pic.twitter.com/kEVJ2cXTuT
— 怒髪 (@dohatsutsu) April 26, 2016
今回は、AOJ-ICPC 500 にある問題(42問)について、感想をひとつずつ書いていこうと思っています。
○カードゲーム
AIZU ONLINE JUDGE: Code Review
学部2年の5月、蟻本のp197にある二部マッチングのコードの使い方を練習するために解いた記憶があります。
68行目に V=m; とあるけれど、これはどうなんだろう・・・・。
このエッジの張り方だと、別に問題はない。(そもそも実際にACしている)
だけど、ノードの数を表す変数としてVを用意しているのなら V=n+m が正しいと思う。
(このときはまだ中身をよく理解していなかったからしかたない)
○Mr. リトー郵便局
Mr. Rito Post Office | Aizu Online Judge
AIZU ONLINE JUDGE: Code Review
学部2年の6月に解いた問題。
なぜかすごく印象に残っていて、今でも概要と解法を覚えているくらい。
それだけ解けたときに嬉しかったんだと思う。
○鉄道乗り継ぎ
Railway Connection | Aizu Online Judge
AIZU ONLINE JUDGE: Code Review
学部3年の6月末(チームFinalZukkyとして国内予選に参加する数日前)に解いたっぽい。
この問題を解いたことによって得られた経験がその国内予選での結果につながったかどうかはかなり怪しい。
○全宇宙生命ゲノムデータベース
The Genome Database of All Space Life | Aizu Online Judge
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1181781#1
学部2年の1月に解いた問題。
再帰関数で素直に最初の文字から1文字ずつ求めていって、i 文字目が分かったら即、再帰関数を終了するようにしました。もっと賢いやり方があるかもしれないけど、この方法はあまり面倒ではないのでこの方法で求めました。
○天の川
AIZU ONLINE JUDGE: Code Review
学部3年の7月に解いた問題。
線分どうしの距離を求める方法を自力で思いつける人はどのくらいいるのだろうか・・・。(僕は本で知りました。)
○Never Wait for Weights
Never Wait for Weights | Aizu Online Judge
AIZU ONLINE JUDGE: Code Review
部活の練習中にUnionFindを使うというネタバレを受けてしまったため、
完全に自力で挑戦して解いた問題ではないです。
結構バグを取るのに時間がかかった思い出があります。
○僕の友達は小さい
My friends are small | Aizu Online Judge
AIZU ONLINE JUDGE: Code Review
学部3年の7月に解いた問題で、結構面白かった。
最初は全く解法が思いつかず、翌日になってもう一度考察してみたらあっさりと解けた思い出があります。
問題文に「なお1,000,000,007 は素数である。」と書いてあるのを初めて見ました。
○Test Case Tweaking
Test Case Tweaking | Aizu Online Judge
AIZU ONLINE JUDGE: Code Review
個人的に解法を考えるのに時間がかかってとても悔しかった問題です・・・。
○Beautiful Currency
Beautiful Currency | Aizu Online Judge
AIZU ONLINE JUDGE: Code Review
個人的に計算量がよく分かっていないです。
n/1+n/2+n/3+...+(n-1)/n+n/n って意外と小さいっぽい?
【No.016】「今更すぎるパソコン甲子園2012参加記?」
高校3年の4月、高校の数学の先生から「かなり勉強しないと会津大学の合格は難しい」と言われた。(このときまで僕は数学ABという科目の存在を知らなかった)
毎日、部活が終わった後はすぐに家に帰って数学ABの勉強をするようにした。(約3カ月続けた)具体的には教科書を読みながら例題と章末問題を解いていった。分からないところがあったときは次の日に高校の先生に聞きに行った。
パソコン甲子園の練習もしたかったけれど数学の勉強で忙しかったし家にネット環境も無いからできなかった。
夏休みに入る頃には数学ABの勉強が一通り終わったので数学IIの勉強をはじめた。
そして9月上旬、パソコン甲子園の予選があった。
All Numbers Lead to 6174 | Aizu Online Judge
まず始めに僕が30分かけてこの問題を解いた。
Points for a Perfect Scorer | Aizu Online Judge
Railway Ticket | Aizu Online Judge
この2つは僕が別の問題の解法を考えている間にチームメイトに解いてもらった。
Kitchen Garden | Aizu Online Judge
何分かかったかは覚えていないけれど、うまく場合分けをしてO(n)で解いた思い出がある。
初めから等差数列になってるような入力は存在しないと勝手に思っていた。
結果は4問ACで22位。地域枠として本選に行くことができた。
ちなみにこの年は10回目記念で本選に進出したチーム数が32チームとなっていた。
11月の上旬、本選に参加するも1問しか解けなかった。
Aka-beko and 40 Thieves | Aizu Online Judge
この問題を解くのに2時間もかかってしまった。
(javaのString型で i 文字目にアクセスする方法を知らなかったため)
持ち込んでいた資料の中からいろいろ探した結果、 split を使ってACした。
残りの2時間はチームメイトに
Triangle of Blocks | Aizu Online Judge
を任せつつ、残りの問題を考察していた。
12月の上旬、会津大学の合格発表があった。
12月の末から4月になるまでの間は数学C、数学III の勉強をした。
【No.015】「JOIOIの塔 貪欲法」
Tower of JOIOI | Aizu Online Judge
この問題を解いた後、JOIのページに行くと想定解が二分探索で、O(N long N)でした。
僕の解法は貪欲法でO(N)でした。
今回はその簡単な解説を行いたいと思います。
つくりたいものがJOIのみだった場合、以下のようなコードになるはずです。
#include<bits/stdc++.h>
using
namespace
std;
int
n,J,JO,JOI;
char
str[1000001];
int
main(){
scanf
(
"%d"
,&n);
scanf
(
"%s"
,str);
for
(
int
i=0;i<n;i++){
if
(str[i]==
'J'
){
J
++; // Jをつくる
}
else
if
(str[i]==
'O'
){
if
(J>0){ // Jが作られていたら、それを1つ使ってJOを作る。
J
--; // 残っていなかったらこのOは決して使われない。
J
O++;
}
}
else
if
(str[i]==
'I'
){
if
(JO>0){ // JOが作られていたら、それを1つ使ってJOIを作る。
J
O--; // 残っていなかったら、このIは決して使われない。
J
OI++;
}
}
}
cout<<JOI<<endl;
return
0;
}
しかし、今回はIOIでもよいため、工夫が必要になります。
'J'を読んだときは'I'を作るようにします。
'O'を読んだときは、'I'が余っていれば'IO'を作ります。'I'が余っていないときは、すでに完成している 'IOI' を分解して 'IO' を2つ作るようにします。
Iを読んだときは、'IO'が余っていたらそれを使って'IOI'を作るようにします。
※ただし、分解によって作られたIOはなるべく使わず、普通に作られた'IO'を優先的に使うようにする。
余っていなかった場合は'I'を作るようにします。
(分解することによって作ったのにも関わらず余ってしまった'IO'をくっつけて元に戻すようすることを最後に行います)
#include<bits/stdc++.h>
using
namespace
std;
int
n,I,IO,IOI,cnt;
char
str[1000001];
int
main(){
scanf
(
"%d"
,&n);
scanf
(
"%s"
,str);
for
(
int
i=0;i<n;i++){
if
(str[i]==
'J'
){
I++; // Iを作る
}
else
if
(str[i]==
'O'
){
if
(I>0){
I--; // Iを1つ使ってIOを作る
IO++;
}
else
if
(IOI>0){
IOI--; // Iが残っていないときはIOIを分解してIOを2つ作る
IO+=2;
cnt+=2; // この方法によって作られたIOの数を数えておく
}
}
else
if
(str[i]==
'I'
){
if
(IO>0){
IO--; //IOを使ってIOIを作る。
if
(IO<cnt)cnt--;//使用したIOが分解によって作られたものかどうかを判定
IOI++;
}
else
{
I++; // Iを作る
}
}
}
cout<<IOI+cnt/2<<endl; // +cnt/2 は分解しすぎたIOIをもとに戻す処理
return
0;
}