ARC056 C問題 部門分け
想定解だと思って書いた解法が、どうやらそうではなかったようなので書きます。
解法
最小カットを使います。
部門を分割することによって幾つかの絆が切られる事を考えると、ある部門を2つに分割するための最小コストは最小カットと等しくなります。
この「2つに分割するための最小コスト」が、部門を1つ増やすことによって得られるスコア K 以上であれば分割を行うとスコアが高くなることがわかります。
このように、部門を最小カットで分割することを繰り返すと最大スコアが得られます。
なお、部門の分割を最小カットで貪欲に切ると良いという証明はできていません。(実験をして大丈夫そうだったので書くと通ってしまいました)(証明は解説を頼ろうと思っていたら全然違う解法が書いてありました)
ICPCアジア地区つくば大会D問題 「Hidden Anagrams」
※これは参加記ではありません。参加記は別記事で上げます。
問題概要
長さ 4000 以下の S1 と S2 が与えられる。
文字列Sの部分文字列を S' と呼ぶことにする。
「S1' が S2' のアナグラムとなるもの」のうち最長のものの長さを求める。
例
入力
anagram
grandmother
出力
4
解法
S1とS2のうち短い方の長さをNと呼ぶことにする。
一致判定をする部分文字列の長さLを 1~Nまで変化させながら、各Lにおいて以下の処理を行う。
- 長さLとなる部分文字列のヒストグラムを記録するmapを用意する。
- 長さLの、S1の部分文字列ヒストグラムをしゃくとり法の要領で列挙し、mapに記録しておく。
- この判定によりアナグラムが一致するものが見つかれば、最長の長さの値を更新していく。
空間計算量がO(文字列長)になるので余裕を持って通ります。
mapを使いまわさず、「長さLのヒストグラムは map[L] に格納する」という実装をするとMLEしてしまいました。
つくば会場ではMLが非常に大きかったようなので、本番ではmapを使いまわさなくても通っていたように思います。
会津合宿2016参加記
9月の17日〜19日に開催された会津合宿2016に参加しました。
会津合宿数日前~前日
🔥🔥🔥大学で一日中作問作業🔥🔥🔥
会津合宿day1
立命館大学セットの作問を担当していました。
講評・解説・入出力ケースは右のリンクから閲覧できます。public - Google ドライブ
会津合宿day2
会津大学セットに参加しました。
Twitterでメンバーを募集していたらctylさんとkazuさんに声をかけていただきました。
会津合宿day2にチームBN003 ( @ctyl_0 + @kazu0x17 + @Yazaten ) で出ます!
— やざてん (@Yazaten) September 18, 2016
コンテスト開始。
A問題がctylさんにより瞬殺されていたがB問題がうまく行っていないらしい。
一方僕はC問題を担当。謎の学園が出てきたが元アニメを知らず悲しかった(あんはぴというらしい)。
曜日ごとに独立だなーと考えて、各曜日においてbitDPした後「i日目にj科目で得られる幸福度の最大値」を求めるDPをする解法を思いつく。
B問題担当のkazuさんとPCを取り合いながら書いたがWA。
しばらくバグが見つからず悩んだが、論理演算のORを"||" ANDを"&&"と書いていた事に気付き修正し提出するとAC。
「bit演算やったことありますか???」という感じ(´・_・`)
Cが通った頃には、BとEが通っていてkazuさんがGを書いているという状態だったので、DとIの概要をctylさんに聞く。
D問題はダイクストラっぽく更新してゴール直前まで行き、ギリギリまで待ってからゴールに渡る解法で解けそうな感じ。
I問題は考察がある程度進んでいて、後は「各頂点から最も遠い頂点までの距離が高速に欲しい」という状態だった。
これ技術奥プログラミングコンテストの不可視境界線では?となったのでcityさんに解法を伝えると良さそうとのこと。
これでDとIの解法が出揃ったが、依然としてGでkazuさんがつらそうにしていた。
この時が一番PCの競争率(?)が高かったように思う。
このときにお菓子を食べに行くと、怒髪先生(ジャッジ側)から「並行して問題解いてるときは一番辛いときだからね。がんばってね。」というありがたいお言葉を頂いた。
その後Iはライブラリを写してもらってすんなりACしたが、DとGはバグが取れずにコンテストが終了してしまった(Gはライブラリが間違っていたらしい)。
コンテスト終了後は駅の方まで移動し懇親会に参加した。
皆で”限界集落”という単語がパワーワードであることに気付きめっちゃ盛り上がった。
会津合宿day3
北海道大学セットに参加しました。
怒髪くんと組みたくなったので探したが遅刻しているらしい。
motiさんに電話をかけてもらってOKの返事をいただく(怒髪先生と連絡をとるのは難易度が高いらしい)。
チームメートがもう一人欲しい気持ちになってTwtterを見ると@tookun_1213さんがメンバーを募集していたのでお誘いした。
会津合宿day3にチームenergy_star ( @dohatsutsu + @tookunn_1213 + @Yazaten ) で出ます!
— やざてん (@Yazaten) September 19, 2016
問題を各自分担する戦法で僕はA問題を担当。
頑張ってやるだけなのでバグらせないように気をつけながらAC。
実装待ちをしていた怒髪くんがD問題を読んでくれていたので概要を聞く。ありがちだけど時間の制約がデカい。
ライブの開始時刻だけ試すのはすぐ思いついたので累積和+二分探索の方針で実装を固める。
BとCがすんなりACしたようなのでPCを貰って実装を開始する。
場合分けや添字を微妙にミスりながらDをAC。
このあいだに怒髪くんがFの解法を思いついたらしいのでバトンタッチ。
ここでEを読んでいたtookunさんと合流して概要を聞く。
残念ながら僕は何も思いつかなかったが、「意外とゲームはすぐ終了するのでDFSで行けるのでは?」*1という感じと言っていたのでおまかせする。
Gを読む。「角角画伯,かく悩みき」の制約追加版という変わった形式で面白い。
まぁ凸包はするよねみたいなことを話したら、凸多角形の任意の辺を底面とした時の縦横の長さを探索できれば良さそうと教えてもらえた。
「キャリパー法で各辺の最遠点が高速に求まる」とか「辺と各点までの横方向の距離は3分探索で求まる」とか話したけれど、「この問題の制約上与えられる多角形の頂点の数はそんなに多くならない」という仮説が出たので時間の都合でそれを実装する…が僕の幾何実装力が低いので途中から怒髪くんに書いてもらう。
どうやら正しかったらしくコンテスト終了6分前にAC。
残り時間でEを書くのは厳しそうだったので、「Gは最悪ケースを作ろうという気持ちになると (多角形の頂点数)≒√(与えられる正方形の数) になりそうだね」みたいな話をしていた。
順位表を見ると、なんとオンラインで2位になっていていた。
普段2位なんて順位は取れないのでチーム戦は偉大だなぁと思った。
おわりに
考察にかなり時間をかけて作った問題が、オンライン参加していたプロによってあっという間に解かれて驚愕した。
去年はそもそもアルゴリズムを知らず考察に携われない問題も多かったが、今年はそういったことは起こらなかったので少し成長を感じた。
チーム戦は最高!組んでくれた方ありがとうございました
*1:行けませんでした
JAG夏合宿2016参加記
9月の2日~5日にかけて開催されたJAG夏合宿に参加しました
1日目 東京到着・ガイダンス
夜行バスで早朝に到着したので、yurahunaさん,37dbyeさん,T.M君と新宿のロッテリアでたむろしていました。
ガイダンスまでは時間があったので、模擬地区2012をyurahunaさんと一緒に解きました。
結局二人でDictionaryとMedian Treeを解き、Stack Mazeが解けず。
以下問題のネタバレなので白文字
「Median Treeは半信半疑で最小全域木を張ったら通ったのですが、解説を見るとキレイな証明が書いてあり面白い問題だと思いました。」
2日目 Central Europe Regional Contest 2014(CERC2014)
チームJag2015Mogichiku( @konjo_p + @nola_suz + @Yazaten )で出場しました。
CERCとはヨーロッパの激戦区の地区予選らしい。
寝坊でチーム決めにTLEしたのですが、2人で出場予定だったkonjo_pさんとnola_suzさんのところに入れてもらうことができました。
開始直後はA~Cをそれぞれ読む方針で僕はB問題を読む。
今いるところから見える一番近い山の斜面はどれですか みたいな問題だったけど斜面の数が結構多くて放置。
あとで聞くと実際ヤバい問題だったらしく良い判断だった。
その間に@konjo_pさんがC問題*1の解法を思いついたらしく書いてもらう。
なんか合わないらしく解法を確認していたが、実装のミスが見つかり無事AC。
その後H問題*2の概要をnola_suzさんに聞き、「なんか組み合わせをDFSで列挙して二分探索でホイみたいな感じですね」と言ったらnola_suzさんが実装をしてくれてAC。(実は列挙しても組み合わせは高々1000以下なので二分探索は不要だった。ごめんなさい。)
この段階で解けそうな問題はF*5かL*6で、Fはチームメンバーが実装してくれそうな感じだったのでLを考える。
区間DPして欲しそうな制約だったがイマイチ区間の持ち方がわからず、いろんな貪欲とかを考えていた。
Lは結局わからないままコンテスト終了だったが、僕を除く2人が熱意でFをACしてくれたので8位といういい感じの順位を取れた
t9qmib + Yazaten - nikollson で参加して8位だった.
— 青 (@konjo_p) September 3, 2016
Lは距離と時間を要素にした二次元平面を考えると、「一番遠くで発生する攻撃は必ず打たなければならない」ことからその左側と右側の2つの区間に綺麗にわかれるのでいい感じに区間DPができたらしい。なるほどなぁ
3日目 JAG 模擬アジア地区予選2016
チームBlackSeven( @shora_kujira16 + @yurahuna + @Yazaten )で出場しました。
( 由来はしょらーさん(@shora_kujira16)の言った「NAのB棟7Fはブラック」というローカルネタ )
LINEさんのオフィスを借りての開催で楽しかったです。
LINEピラミッドできた pic.twitter.com/2fSI9xqeMT
— やざてん (@Yazaten) September 4, 2016
2日目同様、開始直後はA~Cをそれぞれ読む方針で僕はB問題*7を読む。
よくあるBFSなのですぐ解ける。A問題*8がACするのを待って連続AC。
C問題*9をyurahunaさんと考えている間にしょらーさんが「Eはこれハッシュでしょ」と言って提出。WAを食らったので諦め、D問題*10を考えてもらう。
するとここでE問題にリジャッジがかかり時間差AC。
D問題の条件を満たす括弧列には規則性があるらしく、いい感じに生成するプログラムをしょらーさんに書いてもらう。実装ミスでWAをもらいつつAC。
F問題以降はわからなかったのでC問題をセグ木を使ってyurahunaさんとペアプロ。
時間ギリギリに「サンプル通った!よっしゃいくぞ!」と提出したらめっちゃWAが出て終了♨
模擬地区は解説を聞くと「確かに〜〜」となるような問題が多く面白かったです。
4日目 2015-2016 XVI Open Cup
チームMILK_TEA( @osrehun + @satashun + @Yazaten )で出場しました。
( その辺にミルクティーのペットボトルがあったのでこうなった )
KLABさんのオフィスを借りての開催でした。大人の事情でラブライブの写真を取るのは禁止でした、残念。
前日hecさん(@osrehun)がTwitterで組む人を募集していたので一緒に出ることに。
あとは会場でのランダムマッチングでsatashunさんが加わり、プロ&プロ&僕(´・_・`)という感じになりました。
開始直後はC問題を読んだのですが英語がわからず結局satashunさんに助けてもらった(英語弱者感)
その後読んだF問題では閉路を列挙すればいいと一瞬思ったが、一般にグラフの閉路はめっちゃあるらしくて厳しいらしい。
C問題がいけそう、 D問題もRMQ書けばいけそうという感じでstashunさんとhecさんが取り掛かる。
Aが結構解かれていたので僕が考えていたが計算量を落とす工夫が思いつかない…。
結局hecさんに助けてもらいながらなんとかACしたものの、他の問題には全くと言っていいほど関われなくて申し訳なかった。
F問題の最短経路木を考えると良いと言うのが面白かったです。
おわりに
自分より強い方々とチームを組めたので、いい勉強になりました。
今回の合宿で、ICPC系のセットは「解法のわかりやすい問題をいかに高速に片付けられるか」が大事だと感じました。新しいアルゴリズムを覚えるのも大事ですが、解ける問題をしっかり解く練習もしていきたいです。
夏合宿でチームを組んでくださった方々ありがとうございました。おかげさまで楽しい合宿になりました!
おまけ
夏合宿9日目(家に帰るまでが夏合宿です)にマジカルミライ2016に行きました。
行くのは今年で2度目なんですが、今年も神イベントでした。
興味がある人には超オススメですが、ライブ以降テーマソングを聞くと泣きそうになるという弊害があるので要注意です。
*1:連続する整数の和がNになるような式を求めよみたいな問題
*2: 眠い人が携帯電話で数字を打つ問題
*3:一つの歯車を回すと他の隣接した歯車もまわるので、それぞれがどれくらいどちら向きに回転したかを答える問題
*4:x個の'B'とy個の'W'からなる文字列が与えられるので、'B'の個数:'W'の個数 = x:y となる部分文字列に分解する問題(?)
*5:'?'を含む文字列が3つ与えられるので、それらがsortedであるような'?'の組み合わせの総数を求める問題
*6:敵の攻撃がいっぱい来るのでビームで全部破壊して生き残る問題
*7:お姫様とそれを追う兵士がグリッド状にいて、姫は逃げ切れますか?という問題
*8:読んでない
*9:やる気上位20%しか働かない会社に人間が出たり入ったりする問題
NAIST受験記
結果は合格で、学生宿舎優先入居の権利もいただきました。どの結果が功を奏したのかはわかりませんが、何かの参考になれば幸いです。
NAISTの試験は主に 小論文・数学・英語・面接 からなります。
小論文
A4用紙2枚で取り組みたいテーマを記述し、願書提出時に同封します。
大学での専攻がNAISTでの専攻とは異なるので、卒業研究を小論文用に書き換えることはしませんでした。テーマやアプローチは、スプリングセミナー参加時に志望研究室の学生や先生にお話を伺いながら考えました。
このように準備は春休み頃からしていましたが、実際に手を付けたのは願書提出の3週間ほど前でした。僕は言い回しなどの推敲に時間がかかるタイプなので、書き上がったのは願書提出の1週間ほど前でした。その後、志望研究室の博士後期課程の方のアドバイスを参考に修正し、提出しました。
評価はわかりませんが、納得のいく小論文を提出できたと思っています。
数学
解析・線形代数 の分野から出題され、ホワイトボードを用いて口頭で解答します。
数学に今までまじめに取り組んでこなかったのでイチから勉強しなおしました。
使用した参考書はマセマの「微分積分」と「線形代数」です。勉強を始めたのは願書提出後でした。練習問題を解きつつ参考書の内容を理解し、確認のために演習を解く といった形で勉強を行いました。
本番では、arcsinの微分を参考書に載っていた公式を使って解くと微妙な顔をされたり、解析・線形代数 ともに3つ目の小問が全く解けなかったりと、惨敗でした。
甘く見てもせいぜい60点という感じだと思います。
英語
TOEIC・TOEFLのどちらかを選択し、受験日当日にスコアを提出します。
英語に今までまじめに取り組んでこなかったのでイチから勉強しなおしました。
大学が開講している、TOEIC受験者向けの長期の講座に参加しました。講座参加前は350点ほどでしたが、5月の試験で最終的に600点台を取ることができたのでこれを提出しました。
面接
事前に提出した小論文や受験者の専攻に関する質問に、口頭で解答します。
恒例の3分間プレゼンの内容は、事前に作成し暗記して面接に望みました。どうしても説明したい背景なども含めると時間がギリギリになってしまいましたが、何度も練習をして制限時間を超えないよう心がけました。
プレゼン後の質問は、小論文の内容に関するものが多かったです。プレゼンの一部が正しく伝わっておらず再説明したり、学部の研究の内容や進捗について話をしたりしました。「質問に対してはまず解答を述べる」ことや「質問の意図を理解して簡潔に答える」ということを意識し、あとは自然体で受け答えを行いました。
面接官としっかりとコミュニケーションを取り、十分小論文の内容を伝えられたと思っています。
ICPC2016 国内予選 コード置き場
ICPC2016 国内予選の問題を解いたコードを載せておきます。
解法の説明はざっくりです。
参加記はこっちです。
ICPC2016 国内予選 参加記 - あったこといろいろ
問題文はこっちです。
All Problems
A問題
ソートして、隣り合う要素の差の最小値を出力
#include"bits/stdc++.h" using namespace std; #define rep(i,n) for(int i=0;i<(int)(n);i++) #define all(a) (a).begin(),(a).end() #define INF 999999999 int main(){ int n; while(cin>>n&&n){ vector<int> data(n); rep(i,n)cin>>data[i]; sort(all(data)); int ans = INF; rep(i,n-1){ ans = min(ans,data[i+1]-data[i]); } cout<<ans<<endl; } }
B問題
毎回、暫定1位と2位の得票数を調べ、「1位の得票数 > 2位の得票数+残りの票数」を満たした時が当選確実。
#include"bits/stdc++.h" using namespace std; #define rep(i,n) for(int i=0;i<(int)(n);i++) int main(){ int n; while(1){ cin>>n; if(n == 0) break; int a[200] = {0}; vector<string> v(n); bool f=false; rep(i, n){ cin>>v[i]; if(f)continue; a[v[i][0]]++; char ch='0'; int count1 = 0, count2 = 0; for(int j='A';j<='Z';j++){ if(a[j] > count1){ count2 = count1; count1 = a[j]; ch = (char)j; } else if(a[j] > count2) count2 = a[j]; } if(count2 + n-i-1 < count1){cout<<ch<<" "<<i+1<<endl; f=true;} } if(!f)cout<<"TIE"<<endl; } }
C問題
エラトステネスのふるいっぽく配列を埋めながらシュミレーション。
コードはチームメイトが書いたので、ここには貼りません。
D問題
遷移
dp[i][j] = min( dp[i][k] + dp[k+1][j] - deleted , dp[i][j] )
- 区間(i,j)での最適な解は、区間(i,k) と 区間(k+1,j) の組み合わせで求められる。
- deletedは、dp[i][k]の数列の右端 と dp[k+1][j]の数列の左端 の差 が1以下なら2、そうでなければ0。
- kは区間(i,j)の間のどこを区切りに2つの区間に分けるかを表し、列 i+1 ~ j-1 の範囲で変化させる。
- 数字の列も適当にマージする
状態に数列を持っているので、コピーコストなどが原因で少し実行に時間がかかる。
#include"bits/stdc++.h" using namespace std; typedef pair<int,int> pii; #define rep(i,n) for(int i=0;i<(int)(n);i++) #define INF 999999999 vector<int> w; struct st{ int val; vector<int> elm; }; st dp[310][310]; st dfs(int left,int right){ if(dp[left][right].val!=INF) return dp[left][right]; if(left==right) return dp[left][right] = st{1,vector<int>(1,w[left])}; int n = right-left+1; st mini = st{INF,vector<int>(0)}; rep(i,n-1){ st l = dfs(left,left+i); st r = dfs(left+i+1,right); int tmp = l.val+r.val; bool deleted=false; if( l.elm.size() && r.elm.size() ){ if( abs( l.elm[l.elm.size()-1] - r.elm[0] )<=1 ){ tmp-=2; deleted=true; } } if(mini.val>tmp){ vector<int> vec; vec.reserve(l.elm.size()+r.elm.size()); copy(l.elm.begin() ,l.elm.end()-deleted ,back_inserter(vec)); copy(r.elm.begin()+deleted ,r.elm.end() ,back_inserter(vec)); mini = st{tmp,vec}; } } return dp[left][right] = mini; } int main(){ int n; while(cin >> n&&n){ w.resize(n); rep(i, n) cin >> w[i]; rep(i,310)rep(j,310)dp[i][j]=st{INF,vector<int>(0)}; st res = dfs(0,n-1); cout<<n-res.val<<endl; } }
ICPC2016 国内予選 参加記
先輩( @LazyMii )と後輩と、「miyazoy72」というチーム名で参加し、33位でした。
恐らくアジア地区予選に出場できるのではないかと思います。
「SIMrit」という、熱意のある学内のライバルチームも参加していたので、学内1位の順位を取れたのは本当に運が良かったです。
(追記:地区予選進出が確定しました 順位と結果 | ACM-ICPC 2016 Asia Tsukuba Regional)
国内予選当日まで
チームでは、模擬国内予選A・Bに参加したり、1度だけICPCの過去問題を通して解くといった練習をしました。
模擬国内予選Aでは3完早解きで46位、模擬国内予選Bでは普通の速度で3完して40位台*1でした。
この程度の順位では恐らくアジア地区予選に行くことはできず、また前述のSIMritは両模擬国内予選で僕達よりも1問多くACしていたので、本当に歯がゆい気持ちでした。
この時から、「学内一位を取るならば早解きで勝つしかない」と考えていました。
コンテスト
予選にはLazyMiiさんの研究室から参加しました*2。
広い机とプリンタがあったので、良い環境だったと思います。
コードや詳細な解法については別記事参照。
ICPC2016 国内予選 コード置き場 - あったこといろいろ
A問題
問題文が短く、ABCのA問題かと思った。ついでにテンプレートを写しつつAC。
B問題
解法としては「得票数1位の人の票数 > (得票数2位の人の票数 + 残りの全票数)」を満たす、初めのタイミングが答えとなるという単純なもの。しかし、条件を満たしたタイミングでbreakしたため、入力を最後まで読まずプログラムが終了するバグが発生して20分ほど悩む。
早解きで勝とうと考えていた僕はこの時点でダメかもと思い始める。
C問題
パッと思いつくエラトステネスのふるい的な解法はTLEしそうに見えたが、一応LazyMiiさんに書いてもらいながら後輩と2人で考察。少しして前述のTLEしそうな解が問題なく通る。そんなんでええんか…
D問題
問題設定が単純でわかりやすかった。
「これに必勝法があるなら類題がいくらかありそうなものだし、どうせDPでいい感じに全探索やろ」とか思う。後輩にサンプルを解説してもらうと、区間で状態が持てそうなことに結構早く気づく。区間DPは、偶然参加していたSMR686で出題されており、pekempey先生の解説で理解していたので、本当に運が良かった。
この時はテンションが上がりすぎていて、ちょこちょこバグを出しながら*3メモ化再帰で書く。メモ化再帰恒例の、"dpテーブルは宣言したがメモ化を忘れるやつ"をやらかしながら、無事AC。
この辺でたしか2時間くらい経過していた気がする。SIMritはこのとき3完だが僕達よりもペナルティが小さかったため、僕達がACしてから20分以内にACされると逆転されるという状況だった。結果的にはこの20分の間に提出はなかったけれど、僕にとってほんとうにほんとうに長い20分だった。
👇pekempey先生の解説
TopCoder SRM 686 (Div. 1) Easy. BracketSequenceDiv1 - pekempeyのブログ
E問題
D問題をACしたテンションと疲れで僕が使い物にならなくなっていたので、考察を2人にまかせて少し休憩。休憩が終わって全員で話し合った結果、「完成する物体は連結」「完成する物体はドーナツ型かパス型」「一つの立方体と交差する立方体は高々8個?」という結論になった。スタートする立方体を一つ選び、そこからDFSみたいなことをする解法を書くが、いかんせん僕が使い物にならなくなっていて 実装が遅い&バグが出まくる という感じでヒドかった。LazyMiiさんに助けてもらいながら全体の40%くらい[要出典] 書いたところでコンテスト終了。
感想
Bのバグがなかなか取れなかった時は死を覚悟しましたが、Cの全探索をパッと書いてもらえたり、Dの解法がすぐに思い浮かんだのが功を奏しました。ある程度の難易度の問題に対して、早い段階で解法を思いつく能力を付けたいと思いました。
連続でコーディングしていると自分はすぐバテるらしいので、アジアに行けるならばそれまでにコーディングを分担できるようにしたいです。
競プロ引退気味だったLazyMiiさんが「また競プロやってみるかなぁ」*4と言ってくれたり、後輩が「僕も競プロ頑張りたいと思いました」*5と言ってくれたりしたので、本当に良かったです。ICPCは本当に偉大ですね。
たくさんお酒飲んでほえ〜なんですけども、多分ICPCアジア予選に出場できるんですよね。
— やざてん (@Yazaten) June 24, 2016
うれしいなぁ