yukicoder contest 173
お久しぶりの投稿ですね。先に言っておきますと、きょうもSyntaxHighlighterの実装はしておりません。さぼりました。やる気なくてごめんなさい。
そんな私は昨日(今日かな？)、yukicoderに参加しまして、「こ、これがyukicoderか・・・」と洗礼を受けた気分であります。(←ここまで朝)
(こっからAtCoder後→)もう問題行っちゃいます。まずは No.564 です。問題名は「背の順」、自分の背の高さがクラスで何番目か気になっちゃう系男子、なる君が登場するおはなしです。いつものように２以上の自然数Nがもらえるので、なる君の身長Hとクラスメイトの身長H[N-1]を使って、なる君がクラスで何番目の身長なのか教えてあげてください。
ここで私は「身長と言えば小さい順だろ」みたいな固定観念があったせいでWAを食らうわけですが(←サンプルケースみてない(2回目))、みなさんは勘違いしませんでしたかね。
#include <iostream>
using namespace std;
int main(void){
int h, N;
cin >> h >> N;
int H, ans=1;
for(int i=1; i<N; i++){
cin >> H;
if(H>h)ans++;
}
if(ans%10==1){
cout << ans << "st\n";
}else if(ans%10==2){
cout << ans << "nd\n";
}else if(ans%10==3){
cout << ans << "rd\n";
}else{
cout << ans << "th\n";
}
return 0;
}
解法はですね、はじめに なま君がクラスで一番身長が高いと仮定(ans=1)してあげてですね、なま君よりも身長の高いおともだちが出てくるたびに、なま君の順位を一つ落としてあげるんですね(ans++)。もちろん最下位から一つづつ上げてやってもいいんですよ。私は大きい順にむかついた(自業自得)のでしませんでしたが。
んじゃ次！ No.565 です。問題名は「回転拡大」、yukicoは問題名が日本語なのでわかりやすくていいですね。いつもと違ってH×Wの画像を時計回りにR度回転させてK倍に拡大して返せばOKです。いつものNくんが出てこないから(←関係ない)簡単でした(なお"<="の"="忘れて提出1回でACもらえなかった模様)。
ちな「これで絶対合ってる」と思って提出した2回目のコードですが、問題のテストケースが死んでたようで、問題の難易度がコンテスト中に上がって下がってテストケースが直ってACにしてもらうのに15分くらいかかりました。今回はunratedだってさ、もともとyukicoにレーティングはないけどね。
#include <iostream>
using namespace std;
int main(void){
int R, K, H, W;
cin >> R >> K;
cin >> H >> W;
char c[H][W];
for(int i=0; i<H; i++){
for(int j=0; j<W; j++){
cin >> c[i][j];
}
}
if(R==0){
for(int i=0; i<H; i++){
for(int kk=0; kk<K; kk++){
for(int j=0; j<W; j++){
for(int k=0; k<K; k++){
cout << c[i][j];
}
}
cout << endl;
}
}
}else if(R==180){
for(int i=H-1; i>=0; i--){
for(int kk=0; kk<K; kk++){
for(int j=W-1; j>=0; j--){
for(int k=0; k<K; k++){
cout << c[i][j];
}
}
cout << endl;
}
}
}else if(R==90){
for(int j=0; j<W; j++){
for(int kk=0; kk<K; kk++){
for(int i=H-1; i>=0; i--){
for(int k=0; k<K; k++){
cout << c[i][j];
}
}
cout << endl;
}
}
}else if(R==270){
for(int j=W-1; j>=0; j--){
for(int kk=0; kk<K; kk++){
for(int i=0; i<H; i++){
for(int k=0; k<K; k++){
cout << c[i][j];
}
}
cout << endl;
}
}
}
return 0;
}
(K倍にする)イコール(K回おなじものを出力する)です。「4重ループが汚い」とかいう声は却下です。競プロerはACこそ正義です←
んで次は1時間悩んで結局「実装重ッ！」ってなってとばした No.566 です。問題名は「だいたい完全二分木」、いつものように自然数NKがいただけるので、１から(2^NK)-1 までの自然数を二分探索木につっこむと、深さがK以上3K以下になるような１から(2^NK)-1 までの自然数の順を出力すればいいらしいんだけど、ちょっと考えると、ちゃんとアルゴリズム組めば、深さはKぴったりでいい(というかその方が組みやすそう)なことが分かるんだけど、実装が重い。いや完全二分木作って最後の3,1,2を3,2,1にかえるだけなんだけどね。今年のICPC国内予選のB問題と同じくらいアルゴリズム難易度と実装難度がかみあってない。絶対星2じゃない！(←自分が解けないだけ)
私は結局飛ばしちゃったんですが、なんとなんと、想定解法のうち1つに、
二分探索木に をランダムな順序で挿入したときの高さの期待値は最大でも 4.311lnNで抑えられることが知られている(参考)．ここで，とするとおおよそ3Kとなる．
実際，(1,…,N)をランダムに並び替えた操作列は高確率で条件を満たす(ただし，K=2のケースは1/3の確率で高さが1になるので注意が必要である)． 興味があればUTPC 2011 Jを解くとよい．
とか書いてあって、なるほどWA出してもペナルティのないyukicoならではだなあと思った。冒頭のはそれ。
次の問題？ これに1時間かけたんだから解いてるわけないよね。うん。
とか言ってる間に日付をまたいでしまいました。あはは。またね。おやすみ。
ARC082 ABC072
きのうARC(AtCoder Regular Contest)に参加したよ。C問題とD問題の２完で終わってしまったよ。しかもてきとーにやり過ぎたせいでD問題めっちゃWAくらって痛かったよ(時間が)。
やべ、モバイルルーターのバッテリー切れた。半年前から接触悪かった充電器がついに死んでしまった(T^T)。買いにいこうにもめっちゃ雨降ってるしやる気が・・・。
・・・(￣^￣)・・・・・・(￣^￣)・・・・・・(￣^￣)・・・
夜になって充電器繋ぎ直したら充電はじまった。わーい。
というわけで、がんばって書きます。ちなみにTwitchでchokudaiさん(AtCoderの社長さん)がこれ解いてるのを配信してるのを聴きながら書いてるよ。やっぱE問題とばして正解だった。いやFも解けなかったけど。
まずC問題ですね。問題名はTogether。毎度のごとくN個の自然数a[N]をもらえるので、それぞれに1を足したり引いたりしたりしなかったりして、できるだけみんなtogetherな数にしましょうっていう問題。
#include <iostream> using namespace std; int anum[100005]; int main(void){ int N, a; cin >> N; for(int i=0; i<N; i++){ cin >> a; anum[a]++; } int ans=0; for(int i=1; i<100004; i++){ ans = max(ans, anum[i-1]+anum[i]+anum[i+1]); } cout << ans << endl; return 0; }
まあ 1≦a[i]≦10^5 なので1から10^5までの配列(このコードだとanum[ ])を用意して、a[i] っていう数が a[N] の中に何個あるかを anum[ a[i] ] に保存しといて、1から・・・これ説明要る？ あー、aの入力が 1 3 2 5 だと anum={0,1,1,1,0,1,0,0,0,,,} ってなります！ 以上！
あ、max(a,b) はaとbを比較して大きい方を返す関数だよ。max(max(a,max(b,c)),max(d,e)) みたいに使えるよ。便利だよ。似たようなのに min(a,b) があるよ。min(max(a,b),min(c,d)) みたいにも使えるよ。C++だけじゃなくてCにもあるよ。いい子たちだからお友達になってあげてね。
あとねー、グローバル空間(int main(){ }の外)で変数とか配列を宣言すると0に初期化されるよ。だから、はじめ anum={0,0,0,0,0,,,,,,} ってなってるよ。boolでも0(false)に初期化されるよ。便利だよ。そんなにいい子じゃないけど競プロerのみんなはグローバル変数とお友達になってあげてね。
chokudaiさんからツイッターフォローされた!?(deragement) 嬉しいんですがもしかしてツイッター見ながらあの速度で問題解いてるんですかね。。。
chokudaiさんのゲーム配信(違わない)も終わったのでD問題行きましょう。どうせ全部書き終わってからしか公開しないのにこんな時間経過感じさせるブログ書いていいんだろうか。まあいいか。問題名はDerangement(混乱)です。いつものようにN個の自然数p[N]がもらえるんですが今回はそれが1からNまでの数。これをderangement (p[i] ≠ i) になるように、隣り合うpを入れ替えるには最低何回入れ替えればいいですかっていう問題。u_shoは雑魚いのでわざわざ太字で書いてあった隣り合うの4文字を読み飛ばしててWAくらったんだよ。気をつけようね←
#include <iostream>
using namespace std;
int main(void){
int N;
cin >> N;
long long p, tp=0, tpfront=0;
for(int i=1; i<=N; i++){
cin >> p;
if(p==i) tpfront++;
if(p!=i || i==N){
if(tpfront%2) tp += (tpfront/2)+1;
else tp += tpfront/2;
tpfront=0;
}
}
cout << tp << endl;
return 0;
}
tpfrontは、変数の名付けかたに問題がありそうなんで気にしないでね(・x・) さすがに上のコードは読みづらいしアルゴリズムが悪いので、書き直しました。
#include <iostream>
using namespace std;
int main(void){
int N;
cin >> N;
long long p[N+1];
for(int i=1; i<=N; i++) cin >> p[i];
long long tp=0;
for(int i=1; i<=N; i++){
if(p[i]==i){
tp++;
i++;
}
}
cout << tp << endl;
return 0;
}
このアルゴリズムだと説明書かなくていいよね。うん。というわけで、おしまい。
POJ 1517 "u Calculate e"
A simple formula for napier's constant (e) is e=Σ0≦i≦n1/i!(n->infinity).
Imput
no imput
Output
n e
- -----------
0 1
1 2
2 2.5
3 2.666666667
4 2.708333333
...
とりあえずこれで通そうとしたのですが・・・
#include <iostream>
using namespace std;
double factorial(int i){
if(i==0) return 1;
else return i*factorial(i-1);
}
int main(void){
double e=0;
cout << "n e" << endl;
cout << "- -----------" << endl;
for(int i=0;i<10;i++){
e += 1/factorial(i);
cout << i << " " << e << endl;
}
return 0;
}
小数点以下が6桁でまるめられてしまいWA。
ならばと思ってprintf("%d %lf")とかprintf("%d %.9lf")とか使ってみたら、1 1と表示させるべきところで1 1.000000000と出てしまいWAくらった。
最初の３つだけ手打ち入力する以外の方法がよくわからなかったのでググったらsetprecision()とかいうの(初見)を使ってた解法を見つけた。C++で桁数指定したいときに使うらしいんだけど末尾を0埋めしないのがprintfでやるのと違うっぽい(てきとー)
#include <iostream>
#include <iomanip>
using namespace std;
double factorial(int i){
if(i==0) return 1;
else return i*factorial(i-1);
}
int main(void){
double e=0;
cout << "n e" << endl;
cout << "- -----------" << endl;
for(int i=0;i<10;i++){
e += 1/factorial(i);
cout << i << " " << setprecision(10)<<e << endl;
}
return 0;
}
今度こそACうぇい。
今回はブログ書く練習のためにてきとーに問題選んで解いてみました。コードに行番号振ったり色付けたりする方法がわかんなかったので強い人教えてくれると助かります。(強い人はこのブログにたどり着くことなさそう)HTML強い人と競プロ強い人たぶん違うよね。うん。
はじめてのぶろぐ。
一緒に競プロしてる友人が「競プロerってブログしてる人多いらしいよ」と言っていたのでブログはじめてみた。三日坊主になる予感しかしない。まあやる気の続く限り書こうと思う。
東京の大学(the Univercity of Tokyo)←違うに通うために沖縄から出てきて初めてできた友人に誘われて競プロを始めて早15ヶ月。やっとAtCoder(ABC)のD問題くらいは解けるようになった(と思う)。
大学に入るまでプログラミングはおろか自分のパソコンを持ったことさえなかったので、競プロをはじめた当初はPOJのNo.1000程度の問題ですらその友人に教えてもらいながら30分以上かけて書いていたことを考えると、割と成長したなと思う。
コンテストに参加していただけで何か勉強していたわけではないし長期休暇中はそれすらしてなかったので、上達スピードはかなり遅い方じゃないかと思うが、まあそういう
というわけで(どういうわけだ)、みなさんよろしくお願い致します。
あ、競プロに関係ないことも書いたりするかもよ。
