Hatena::Grouptopcoder

k_operafanのTopCoder日記

2011-12-04

[]Codeforces Beta Round #96 Div1 13:23

A問題

最初は問題文の意味が付かめず,与えられた文字列から数列を作るものだと勘違いしてしまい,答えが合わずに詰んでしまった.

結局問題文の下の方にあるNoteに気づき,それで問題文を理解し,修正してSubmit.

Accepted(466点)


BとCで悩んだ結果解いている人が多そうなC問題に

C問題

一次元上のロボットを命令によって動かす(ただしN回はかならず命令を変更しないといけない)問題

ある命令まで見た時に,ある方向を見ていて,ある回数だけ命令を変化させた時の最大の距離をメモして解いてみる.

サンプルが合ったので提出してみた所,"Wrong Answer(Pretest4)".

問題文を再読した所,"(one command can be changed several times)."を考慮していなかったのが不味そうだったので修正してSubmit.

Accepted(466点)


DとBで悩んだ結果,Bはただの実装ぽかったのでB問題に

B問題

愚直にシミュレートすると間に合わなそうだったので,ある点からある方向に出来るだけ進んだ時の座標をあらかじめ計算しておくことにした.

後は実装するだけ.

Accepted(1128点)

D問題

一番下の桁から見ることにすると,その桁に対して加算or減算or何もしない を選択することになる.

そこで,現在見ている桁と繰り下がりがあるかどうかでDP

経路復元に思ったより手間取ってしまい,かなり時間を掛けてしまった.

Accepted(1344点)

E問題

問題を見た瞬間,UTPC 2011 Hみたいな問題だと思ったので,それをベースに経路復元を追加する感じで解いた.

経路復元は逆辺にフローが流れているかどうかを用いて行なった.

Accepted(1340点)

Hack

何も出来なかった

結果

点数:466+1128+1222+1344+1340+0=5550

順位:3位

レート:2032(+158)

AwaAwa2012/08/30 20:55Four score and seven minuets ago, I read a sweet article. Lol thanks

xvouymqyzkmxvouymqyzkm2012/08/31 15:57ndXart <a href="http://zwliwohkpkgq.com/">zwliwohkpkgq</a>

lvdogjlvdogj2012/09/01 04:02rDY7uh , [url=http://mikwbavebwlo.com/]mikwbavebwlo[/url], [link=http://bgzmsnxtujrk.com/]bgzmsnxtujrk[/link], http://zprrvkeurgip.com/

znlwyeznlwye2012/09/02 02:35y4tvBR <a href="http://esubbkldtdey.com/">esubbkldtdey</a>

ovavislifalovavislifal2012/09/02 08:45a7cPNc , [url=http://jmkzpwwebqwx.com/]jmkzpwwebqwx[/url], [link=http://wpyqgwkmmxos.com/]wpyqgwkmmxos[/link], http://xycrfemhhsfs.com/

2011-11-20

[]Unknown Language Round #4 03:20

Befunge言語.

資料は大体Wikipedia(ja).

A問題

とりあえずやるだけ

&::2**\-.@

B問題

スタックを用いる

0v      >v
 >~:5-5-|> 
        $ >v
        >:|>,
          @

C問題

Bよりも簡単

0&v        >v
  >\&+\ 1-:|>
           >$.@

D問題

プログラム上に数値を記録することが出来る

&55p&00p&66p1v    >v
             >00g:|> \55g*66g%\ 1-00p
                  >\.@

E問題

プログラム上には0~255の数字しか記録出来ないことに注意.

v       >v
>001&:1-|> 2-v
        >0.@ 
v            <
  >1-v
>:|  >:99*/ 00p 99*%11p 10p 20p 20g+ 10g+ 99+8+% 30p 20g 10g 30g 00g99** 11g+
  >$.@

F問題

200p&v     >00g1+00pv          >v 
     >:00g%|      >>> 00g 88*- |>
           >00g:./^            >v   >.@
                                >:1-|
                                    >@  

2から順番に割っていくだけ

G問題

v       >v       >v                 >v
>~:5-5- |>:348**`|>:9999997++++++2*`|>,    >
        >@       >,                v>84*-, ^ 
                                   >       ^

場合分け.小文字だったら32を引く

H問題

競技プログラミング的には典型問題.スタックを使う.

0v      >v     >v  >v
 >~5-5-:|>:65*-|>\:|>  1-\      >$    
        v          >"ON",,@         
        v      >            \1+\^
        
          >"ON",,@ 
        >$|>"SEY",,,@
          >^

結果

8問解けて14位だった.

80x25ということを忘れててソートが解けなかったのが悲しい.

PinkPink2013/02/18 18:37IJWTS wow! Why can't I think of thgins like that?

uaihaxeuuaihaxeu2013/02/19 02:16ZLCb5g <a href="http://vabroxfdkcxh.com/">vabroxfdkcxh</a>

ilwxvxveyjtilwxvxveyjt2013/02/19 11:23pc2xpX , [url=http://wekxaiffbfix.com/]wekxaiffbfix[/url], [link=http://kerpjdelhbaq.com/]kerpjdelhbaq[/link], http://whkudnhelhpy.com/

ncrsjpgmtttncrsjpgmttt2013/02/21 14:19mk7dWi <a href="http://jltigiodwqay.com/">jltigiodwqay</a>

seghehldrlcseghehldrlc2013/02/21 18:44ogW4WC , [url=http://egwmtxsovhrv.com/]egwmtxsovhrv[/url], [link=http://dxfjfzicqbjq.com/]dxfjfzicqbjq[/link], http://vjmyyqqivqif.com/

StitchesStitches2016/05/03 06:48Inlntligeece and simplicity - easy to understand how you think.

2011-11-04

[]Codeforces Beta Round #92 Div1 00:27

敗北

A問題

2の倍数と2で割ったら素数になる2の倍数の数を同じ色で塗るようにする.

貪欲法

B問題

座標を45度回転して,隣接移動及び斜め移動が出来ると考える.

オーバーフローによりWA

C問題

分からなかった

D問題

Suffix Arrayをごにょごにょすれば解けそうな気がしたけど…

結果

点数:936+0+0+0+0=936

順位:180位

レート:1874(-9)

RandhilRandhil2016/05/03 08:22Do you have a spam issue on this site; I also am a blogger, and I was wanting to know your situation; many of us have created some nice procedures and we are looking to trade methods with others, why not shoot me an e-mail if inerdestet.

FinchFinch2016/05/04 02:00that some of the Elders in this <a href="http://xwpgdj.com">pe#srn&o8217;s</a> district in Chile would be leaving their mission early so they could begin school on time. Found that interesting. Not sure how much longer they had to serve….I guess not too long.

CaeliiCaelii2016/05/08 12:25Fabrizio, come è andata l&rcs17;in8u#2ione nella tana di SeL?Tu sarai anche ateo, ma a me sembri un uomo di fede ferrea e incorruttibile (e guarda che non lo dico con tono ironico!) http://myahavx.com [url=http://afccsfw.com]afccsfw[/url] [link=http://dkckhfo.com]dkckhfo[/link]

2011-10-27

[]Codeforces #91 02:56

人権なんて無かったのです.

A問題

普通にやろうとすると10^9*11ぐらいになりそうだったので分割統治法を使って解いた.

intオーバーフローで2WA喰らった.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long lli;
lli l,r;
set<lli> luckynumber;
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
vector<lli> lucky;
void dfs(lli now){
	lli f=now*10+4;
	lli s=now*10+7;
	if(now>1e11)return;
	if(luckynumber.find(f)==luckynumber.end()){
		luckynumber.insert(f);
		dfs(f);
	}
	if(luckynumber.find(s)==luckynumber.end()){
		luckynumber.insert(s);
		dfs(s);
	}
}
lli next(lli x){
	return *lower_bound(lucky.begin(),lucky.end(),x);
}
lli sum(lli l,lli r){
	lli t=next(l);
	if(l==r)return 0;
	if(t==next(r-1)){
		return t*(long long)(r-l);
	}else{
		return sum(l,(l+r)/2)+sum((l+r)/2,r);
	}
}
int main() {
	dfs(0);
	FOR(it,luckynumber){
		lucky.push_back(*it);
	}
	cin>>l>>r;
	cout<<sum(l,r+1)<<endl;
	return 0;
}

B問題

4477などがあるとループしそうだったのでループするまで回し,ループしたら残り回数mod2だけ回すという方針で解いた.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <tr1/unordered_set>
using namespace std;
typedef long long lli;
#define set tr1::unordered_set
set<int> ac;
string data,back1,back2;
int n,k,v;
int main() {
	cin>>n>>k>>data;
	int seen=0;
	for(int i=0;i<k;i++){
		bool ok=false;
		for(int j=max(0,seen-1);j<n-1;j++){
			if(data[j]=='4'&&data[j+1]=='7'){
				if((j+1)%2==1){
					data[j]=data[j+1]='4';
				}else{
					data[j]=data[j+1]='7';
				}
				seen=j;
				ok=true;
				break;
			}
		}
		if(!ok)break;
		if(ac.find(seen)!=ac.end()&&v==0){
			v=1;
			i=k-2-(k-i)%2;
		}
		ac.insert(seen);
	}
	cout<<data<<endl;
	return 0;
}

C問題

k<10^9ということに気づかず10^9!をどうやって求めるのかを永遠と考えていた.

要復習

結果

点数:364+806+0+0+0=1170点

順位:278位

レート:1883(-43)