あったこといろいろ

ほぼ自分用備忘録です。

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

ラズパイでMeCab-Pythonを使えるようにした