あったこといろいろ

ほぼ自分用備忘録です。

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は本当に偉大ですね。



*1:当日はメンバーの予定が合わず、後日集まって解いた結果なのでざっくりとした順位です

*2:快く承諾してくださった研究室の先生および学生に感謝します。

*3:LazyMiiさんが横でバグを潰してくれて本当に助かった。

*4:意訳

*5:意訳

AOJ 2282: Problem B

Problem B | Aizu Online Judge
問題が長くてややこしいけれど、考察すると意外と簡単

考察・解法

問題文を素直に読むと自分より前の申請を考慮した場合分けが必要に見えるが、考えると実は不要であることがわかる。

  • 申請の時点で自分が担当者にならない申請ができる場合、"B問題の担当者"から外れられることが確定する。"B問題の担当者"になり得ない人の作業時間は結果に影響しないので、Mを超えない最大の"難易度の倍数"の値を申請すると考えて良い。
  • 申請の時点で自分が担当者にならない申請ができない場合、問題文通りMを超えない最大の"難易度の倍数"の値を申請する。

つまり、全ての人は前の人の状態にかかわらず、Mを超えない最大の"難易度の倍数"の値を申請すると考えることができる。

なお、申請が嘘かどうかの判定をする必要はない。
なぜならば、すべての人は作業時間を0と申請することが可能なので必ず嘘とバレない申請をできるからである。


あとは考察によって簡単になったシミュレーションを行い、pairの比較演算の特性を利用してソートすると意外とスッキリ解ける。

#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 all(a)  (a).begin(),(a).end()

int under(int v,int m){
	int ret=0;
	while(ret+v<=m)ret+=v;
	return ret;
}

int main(){
	int n,m;
	while(cin>>n>>m&&(n||m)){
		vector<pair<pii,int>> vec;	//各人の 作業時間、問題難易度、識別番号を持つ
		vector<int> v(n);
		rep(i,n)cin>>v[i];
		
		rep(i,n){
			int time=under(v[i],m);	//i番目の人が申請する作業時間
			int diffi=v[i];		//i番目の人が担当した問題の難易度
			vec.push_back( make_pair(pii(time,diffi),i) );
		}
		sort(all(vec));
		if(vec[0].first==vec[1].first)cout<<n<<endl;	//time,difficultが最小の人が複数居た場合
		else cout<<vec[0].second+1<<endl;		//time,difficultが最小の人が一意に決まる場合
	}
}

RUPC2016参加記

参加記です
問題の概要が雑であることなど、参加者でないと理解不能な内容があるのはご容赦ください

day1 立命館大学セット

B問題とD問題の作問を担当していました。
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=B
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=D

解説スライドはここです


day2 会津大学セット

@wanimaru さんと @kenkoooo さんと、チームyazamaruooooで参加しました

僕はB問題とD問題を解きました


読むとなぜか rollman さんの顔が思い浮かぶB問題は、どう見てもバグらせると辛い系だったので慎重に紙コーディングしてから提出。紙から写経するときに'A'と'B'を打ち間違えて1WAを食らいながらAC。

D問題は @kenkoooo さんに「木を切ってパスグラフ2つになったらOK」みたいな概要を聞いて考察。「パスグラフ or T字グラフ or H字グラフ に場合分けして、距離とか端点で場合分けして…」みたいなのが思い浮かんだ。

絶対バグを出す自身があったのでもうちょっと考えると、2人が同時に木を移動してゆくdfsが思い浮かんだので時間をかけて実装＆AC。


チーム全体ではA,B,C,D,F,Gの6完と、まずまずかなぁという感じだった(終了後すぐに @kenkoooo さんがHをACしてて惜しかった)。

懇親会で、D問題は「肝試しで2人が神社をめぐる」みたいなストーリーがあったことを知ったけど
kenkooさん「木の上のノードを2つの点が移動します」
ぼく「OK、解きます」
みたいな感じでスルーしてしまったので、なんだか申し訳なかった


day3 北海道大学セット

かず さんと motxx さんと、チームekmnotで参加しました
競プロを始めたばかりという人もいたので各自問題を分担することはせず、チームでA,B,D問題を解きました

A問題は 与えられる文字列の添字が逆順( 11,10,9, ... ,2,1,0 )に振られていて悪質
かず さんと一緒にバグらせながらAC

B問題は motxx さんが「周期Tは必ず数列長Nの約数」みたいなことを言ってくれたのでバーッと書いてすんなりAC

D問題はお菓子を食べてたら解法が湧いたので実装。気をつけていたつもりが一箇所オーバーフローで1WAを食らいながらAC。
解法の確認で「チームメイトに数列を決めてもらい、僕がクエリを投げながら数列を当てる」ということを実際にやったときに、「Yazatenさん、なんかメンタリストみたいっすね」と言われたのがめっちゃツボだった

Dを通した段階であまり時間が残っておらず、あとは余った問題文をみんなで読んでただけだった

おわりに

チーム戦は一人よりもたくさんの問題に触れられてやっぱり楽しいです。組んでくれたみなさんありがとうございました。
解けなかったりチームの別の人が解いた問題をしっかり復習して、今後は長時間セットで座ってるだけの時間を減らすことができるように頑張ります！

AOJ 0151: Grid

Grid | Aizu Online Judge

実装が面倒なやるだけっぽいですが、DPで書くとさくっと解けました。

遷移

左から、左上から、上から、右上からの4パターン。

状態の持ち方

dp[i][j][0] = i 行目 j 列目まで見た時、横向きにいくつ連続しているか
dp[i][j][1] = i 行目 j 列目まで見た時、縦向きにいくつ連続しているか
dp[i][j][2] = i 行目 j 列目まで見た時、右ななめ下向きにいくつ連続しているか
dp[i][j][3] = i 行目 j 列目まで見た時、左ななめ下向きにいくつ連続しているか

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back

int n;
int main(){
    int n;
    while(cin>>n&&n){
        int dp[256][256][4];
        rep(i,256)rep(j,256)rep(k,4)dp[i][j][k] = 0;

        vector<string> data(n);
        rep(i,n)cin>>data[i];
        
        int maxi = 0;
        rep(i,n){
            rep(j,n){
                if(data[i][j]=='1'){
                    dp[i][j][0] = ( j-1>=0          )*dp[i  ][j-1][0] +1;
                    dp[i][j][1] = ( i-1>=0          )*dp[i-1][j  ][1] +1;
                    dp[i][j][2] = ( i-1>=0&&j-1>=0  )*dp[i-1][j-1][2] +1;
                    dp[i][j][3] = ( i-1>=0&&j+1<n   )*dp[i-1][j+1][3] +1;

                    rep(k,4) maxi = max(maxi,dp[i][j][k]);
                }
            }
        }
        cout<<maxi<<endl;
    }
}

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 B問題 ディスコ社内ツアー

コンテスト中に解法を思いつけなかったので、AtCoderの解説とTwitteを参考に解きました。

問題

B: ディスコ社内ツアー - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 | AtCoder
面白さがそれぞれA_iの部屋が環状にならんでいて、面白さが広義単調増加となるように部屋を回る。
1番目の部屋を出発点としたとき何周する必要があるかをもとめる。
みたいな問題

解法

実際にぐるぐるまわる単純なシュミレーションを書くとO(N^2)になり部分点の20点が得られます。



満点解法もぐるぐるまわるシュミレーションなのですが、面白さが等しい部屋をまとめて管理することで高速化でき、O(N)で解くことができます。


まわる部屋はかならず広義単調増加になっているため、面白さが等しい部屋は必ず続けて通ることになります(例 : 2 1 3 2 2 2 -> 1 2 2 2 2 3 )
これに注目し、キーを「面白さ」、値を「"その面白さである部屋のindex"をもつvector」のmapを使用して、面白さが等しい部屋をまとめて管理します。
このmapを利用してシュミレーションを行います。


基本的にはmapのキーが小さい順に舐めていくだけなのですが、今いる部屋の更新の際に工夫が必要になります。
説明を簡単にするため、「map[i]」と書いたときのiを、mapのキーの中でi番目に小さいものとします。
また、map[i]の値(vector)は昇順にソートされており、大きい値が格納されている方を右と呼ぶことにします。


現在いる部屋のindexをnowとし、はじめは-1に初期化しておきます。
すると次に向かう部屋は「map[0]の値(vector)のうち、nowのindexから右にたどっていき、はじめに見つかったもの(右端にくると左端にローテーションする)」となります。
その後、向かった部屋と同じ面白さの部屋を全てまわることになります。
つまり今いる部屋のindexをnowとすると、以下のようにnowの値を更新していくことができます。

next = upper_bound( map[i].begin(),map[i].end() , now ) - map[i].begin();
now = map[i][  (next - 1 + map[i].size()) % map[i].size()  ]

now==1の時の更新を図にするとこんな感じで、この例ではnowの値は1から0に更新されます。
f:id:Yazaten:20160203074018p:plain


よく読むとわかるのですが、「(next - 1 + map[i].size()) % map[i].size()」は基本的にはnext-1の結果と一致し、next==0のときにのみ「map[i].size()-1」となります。



面白さが等しい部屋の左端と右端だけを持つと今いる部屋の更新がうまく行かず、例えば「2 1 3 2 2 2」というケースに対して3と出力してしまう(正解は2)ので注意が必要です。

#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 all(a)  (a).begin(),(a).end()
#define pb push_back

int main(){
    int n;
    cin>>n;
    vector<int> vec(n);
    map<int,vector<int>> mp;
    rep(i,n){
        cin>>vec[i];
        mp[vec[i]].pb(i);
    }
    
    int count=1,now=-1;
    for(auto itr = mp.begin();itr!=mp.end();itr++){
        vector<int> sec = itr->second;
        sort(all(sec));
        
        int p = lower_bound(all(sec),now)-sec.begin();
        if(  now>sec[  (p+sec.size()-1)%sec.size()  ]  )count++;
        now = sec[  (p+sec.size()-1)%sec.size()  ];
        
    }
    if(now == 0)count--;
    cout<<count<<endl;
}

CODE FESTIVAL 2015 参加記まとめ

CODE FESTIVAL 2015 の参加記まとめが少し寂しかったので、僕が観測できた範囲の参加記をメモしておきます。

togetter版 -> CODE FESTIVAL 2015 参加記まとめ - Togetterまとめ

参加記

投稿日が新しい順に並んでいます。

CODE FESTIVAL 2015 参加記

CODE FESTIVALの参加記です。

前日

自費前泊したかったが試験があったので断念
当日遅刻が怖いので21時くらいに寝ました。

1日目

3時過ぎに起きる

新幹線の切符の予約予約はしていなかったので適当な時間の新幹線に乗る。
新幹線の中で各位の現地入りツイートを見ながらワクワク。

チョット早めに会場につく。
お馴染みの音楽が流れていて、「今年もこどふぇすに来たんだなぁ」という気持ちになりました。 あの音楽配布はされないのかなぁ

色々な人との再開を楽しんでたらコンテスト開始時間になりました。
回線の不調で開始が少し遅れたので ichigo_o_re さんとDDRをしていました。その後は特に何事もなく無事開催。
ABCDEを解いて、FGHわからんぞ〜 といってる間にコンテストは終了。 結果は110位でした。
パーカー圏内ではあるけど、できれば6完して頭一つ抜け出したかった。精進案件。

今年はご飯が立食では無くなっていたので慌ただしくて少し残念でした。
お寿司を貰ってトークライブへ。
トークライブフェイズでは、けんしょーさん、秋葉さん を見に行きました。

その後は去年特に楽しかったイベント、エキシビションマッチを見ました。
尊敬するプロ達のコーディングが見れて最高！

最後に2日目のチーム対抗リレーのチーム決めをして解散しました。
チームで集まった際に eha さんがリュックにつけていたマムルのぬいぐるみに気付いてくれ、風来のシレンの話が出来たので嬉しかったです。


夜は眠かったのですぐに寝ました。

2日目

高層ホテルなのでエレベータがなかなか捕まらず集合にTLE、タクシーであさプロへ。
あさプロはEasyに参加したけれど、ハマりにハマって全完できず…

その後は様々なお弁当が準備されていたので天丼のお弁当を選びました( 焼肉にしておけばよかったと少し後悔した )。
急いでお弁当を食べ、chokudaiさん、りんごさんを見に行きました。
りんごさんクイズがぶっ飛んでいて非常に面白かったです。

↓参考

ここで残っているスタンプを埋めるとギリギリタンブラーが貰えることに気付いたので、急いでボードゲームや太鼓の達人などなどをやりました。
一緒に遊んで頂いた nikollsonさん、kyosさん、dohatsutsuさん ありがとうございます 楽しかったです♪

その後は最後のイベントチーム対抗リレー。
僕はE問題( 時計を回転させてあさプロに間に合わせるアレです )を担当したもののバグを埋め込んでしまい、「全探索してみれば」との助言を基にAC。 チーム対抗っぽいぞ。

その他の問題にはあまり貢献出来ませんでしたが 無事全完して2位。
余った時間で eha さんにゴミ箱の作り方を伝授するという貴重な体験をしていました。
参考 : 『広告チラシで折るゴミ箱』で便利＆エコ [家事] All About

表彰式では、全体的にはWAを結構出しつつも2位を取れたということでMVPならぬMVTをいただきました。
商品としてスウェットを頂いたので、CODE FESTIVALでもらった物だけで外出が可能になりました！！

最後の懇親会で強い方と話す機会があったのでCODE FESTIVALの話をしました。
強い人は実は退屈だったりはしないのかと気になっていたけれどどうやらそんなことはなく、コンテストよりも催しが楽しみだ！という強い人もいる( 誇張かもしれないけれど )らしく、改めて凄いイベントだなぁと思いました。

おわりに

CODE FESTIVAL は最高のプロコンイベントなので来年も参加したいのですが、今年の予選の順位を考えると難しいかもしれません…
ただ「来年も来るために精進するぞ！」と思えたので来年に向けて頑張ります！