u_sho競プロぶろぐ

21歳。みゃーくぴとぅ。ゆる~く続けますたぶん。  デザイン変えました(2019/2/25)これでいきます

AtCoder Beginner Contest 119 (ABC119)

みなさん,おはこんばんにちは,u_shoですにゃ
MacBook Airの記事をかいていたらABCの記事こんな時間になっちまったよ(昼だが(夜だったので))
u-sho.hatenablog.com

実は前回のABC118にも出ていたのだけど,3か月ぶりに競プロしてみたら爆死したからそっちの記事は書かないよ
あと,今回でなんと
AtCoder緑になりました
いぇ~いv(棒)
いえ,爆死しなければ上がれることは分かっていたので。
ついでに言えば,最高パフォも1415に更新しました(実はこっちの方が嬉しい)。

今回の勝因は,ABC史上2番目に正答率の低かったC問題に5分で見切りをつけたことですね。
わからないなら(もしくは実装に時間がかかるなら)一旦とばす。これ大事
ではでは,問題の方に

A - Still TBD

A問題は日付がyyyy/mm/ddの形で渡されるので,それが平成(Heisei)か次の年号(To Be Determined)か(なぜまだ発表されていないんだ)を判別するやつです。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string S;
    cin>>S;
    if(S<="2019/04/30") cout<<"Heisei\n";
    else cout<<"TBD\n";
    return 0;
}

string型の比較演算はまず長さで比較して,次に辞書順で比較します。
今回のケースでは長さはすべて等しく,また日付は辞書順ですので,これでOKです。
制約を見ている人は,mの部分が4以下かどうかだけ判定すればよかったみたいですね←爆死のもと

B - Digital Gifts

N人から x JPY(日本円) か x BTC(ビットコイン) のお年玉をもらえるので(貰いたい),
それが全部で何円か,合わせてみましょう。という,問題だけ見ると小学校の算数。
1BTCあたり380000円なので,それにをもとに計算すると,こんな感じ

#include <bits/stdc++.h>
using namespace std;

int main(){
    double N, x, ans=0.0;
    string u;
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> x >> u;
        if(u=="JPY") ans += x;
        else ans += x*380000.0;
    }
    cout << ans << endl;
    return 0;
}

今回は有効数字8桁だったので,double型なら十分です。
(参考)浮動小数点数型と誤差
出力もcoutのデフォルトでOKです。不安ならprintfを使いましょう。

C - Synthetic Kadomatsu

l[i](3≦iN)の長さのN本の竹に対して,魔法を使ってA,B,Cの長さの3本の長さの竹を錬成しましょう。
えー,個人的にはむずかった。発想としては,各々の竹にに関して,

  1. Aに使う
  2. Bに使う
  3. Cに使う
  4. 使わない

の4通りがあるので,4^N(N≦8)で全探索すれば解けます。

なんか,数学1Aの「場合の数」で、
『通し番号のついた8個くらいのボールをそれぞれ名前の付いた3個くらいの箱に入れるやり方は何通り?』
っていう問題と発想は似てると思うんですよ。

僕はこれと類似の発想を見る度に天才だと思っているし,この発想は苦手というか穴ですが、
典型ではあるので,他の人が解けていないのはちょっと謎に思いました。
みんな私と同じところが苦手なのでしょうか・・・
ともかく典型は解けるようになりたいと思ったのですよ。

D - Lazy Faith

1本の道があって,一方の端からs[i](1≦iA)の距離に神社(shrine),t[i](1≦iB)の距離に寺(temple)があり,
君がx[i](1≦iQ)の場所にいるとき,神社と寺を少なくとも1回ずつ訪れるには最短どのくらい歩けばいい?

こういう問題が出たら,とりあえずソートします。*1
んで,こういうときは実際に想像します。

  1. 右隣のお家に回覧板を回して,その右隣のお家にも何か差し入れするとき→→
  2. 右隣のお家に回覧板を回して,左隣のお家には何か差し入れするとき  →←←
  3. 左隣のお家に   〃   ,右隣のお家には   〃    とき  ←→→
  4. 左隣のお家に回覧板を回して,その左隣のお家にも何か差し入れするとき←←

というパターンがあって,回覧板(神社)と差し入れ(寺)はこの場合区別しなくてもよいので,これで以上になります。 

これを4パターンをそれぞれのxについて全探索すればよいわけですが,
A,B,Q≦1e5なので,『それぞれのxについてO(log(A+B)程度で解く必要がある』ことが分かります。
これが†真の制約†です。

全探索自体は4パターンしかないので,それぞれのxがソート済みのsとtのそれぞれ何番目にあるかをO(log(A+B)程度で求めればよいわけです。
それぞれのxがソート済みのstのそれぞれ何番目にあるかを求めるのといえば,
upper_bound()やlower_bound()がお馴染みですが,
奇しくもそれらの計算量はO(logn)なので(2分探索するため),なんと†真の制約†をクリアできました。やったね☆

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll A, B, Q;
    cin >> A >> B >> Q;
    vector<ll> s(A), t(B), x(Q);
    for(ll i=0LL; i<A; i++){
        cin >> s[i];
    }
    for(ll i=0LL; i<B; i++){
        cin >> t[i];
    }
    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    for(ll i=0LL; i<Q; i++){
        cin >> x[i];
    }

    for(int i=0; i<Q; i++){
        ll ans=0LL;
        decltype(s)::iterator its = upper_bound(s.begin(), s.end(), x[i]);
        decltype(t)::iterator itt = upper_bound(t.begin(), t.end(), x[i]);

        ll sl = *its, tl = *itt;
        if(its==s.end())sl=3e10;
        if(itt==t.end())tl=3e10;

        ll ss = *(its-1), ts = *(itt-1);
        if(its==s.begin())ss=-3e10;
        if(itt==t.begin())ts=-3e10;

        if( sl < tl ){
            ans = min( x[i] + sl - 2*ts, -x[i] + 2*sl - ts );
            ans = min( ans, tl - x[i] );
            ans = min( ans, x[i] - min(ss,ts) );
        }else{
            ans = min( x[i] + tl - 2*ss, -x[i] + 2*tl - ss );
            ans = min( ans, sl - x[i] );
            ans = min( ans, x[i] - min(ss,ts) );
        }
        cout << ans << endl;
    }

    return 0;
}

こぼれ話

手元でg++コンパイルして提出前に確認できたから
イテレータ関連でCEやREを投げなかったのが嬉しかったかな。
やっぱり手元に実行環境は作っておくもんだね。
そういえば今回はレッツノートで参戦しました。

*1:ソートの計算量は配列の大きさnについてO(n log n)なので,そこだけ確認しましょう。

MacBook Air 2019を理系大学生が1ヶ月使ってみた使ってみた感想

久しぶりの更新です。もう成人したどころか21になりました。u_shoです。
ブログ紹介欄に19歳とか書いてあって流石に笑いました。
最終更新から1年以上経っているということですね←おい

時の流れは速く,この20年間働いたことのなかった私も
3か月ほど前からレッドインパルス株式会社さんでアルバイトをはじめました。

開発環境を揃えるという名目でMacBookPro2015を貸与してもらっていたのですが,
使っているうちに自分で1台所有したくなってしまったので
大学の帰りにMacBook Airを買ってしまいました。

f:id:u_sho:20190225101432j:plain
MacBook Airとその箱の間からこんにちはしているのが,私御用達の大学生協PCくんです。

購入したのは MacBook Air 2019年モデル(メモリ8GB,SSD256GB,Retinaディスプレイ13インチ)です。

学生・教職員の方は,Macの学生プランで購入した方が*1,家電量販店で購入するよりも格安と思います*2
私は家電量販店でバイトしてる友人がいたので少しばかりごねたら主任と価格交渉してくれて,
学生プランと同額で購入できました。学生プランと同額でないと買うつもりはなかったのですが,
割り引いて頂いたおかげで,その日のうちに手に入れることができて満足でした。

ありがとうビックカメラ京王調布店。 ありがとう売り上げ目標。ありがとう友人A――

MacBook Airの利点・欠点

いうわけでMacBook Airを普段使いしているのですが,

  1. ディスプレイがめっちゃ綺麗
  2. 音質が最高

という感想が強くて,15万円のディスプレイとスピーカーセットを買った気分です(笑)
正直ノートPCとしての性能はゴミ私が今まで使っていた大学生協PCくん(レッツノート8GB,256GB,Corei7-6500U)とそんなに変わらないです。

というかAirはスレッド数,コア数が少ないので,だいたいの場面においてレッツノートのほうが強いです。
拡張性についてもレッツノートの方が強いですが,省電力性に関してはAirがリードしています。
正直5時間もHD動画を流していて,バッテリーを60%程度しか消費しないのをみたときは驚異的だと思いました。
あと貧弱なりにもGPUがついているので,囲碁AIとか機械学習とかでもよい性能を発揮するかも

プログラミングで使っていて思う利点としては,

  1. _(アンダーバー)が打ちやすい
  2. 半角/全角キーにあたる,英数キー/かなキーやCtrlキーの配置がよい
  3. Ctrl+(P,N,B,F)キーによるカーソル移動(初期設定)
  4. 画面遷移のしやすさ

とかですかね。どれもmacOSならではです。
ただし,キーが固くて大きいので,打っていて疲れます。HHKB*3BTを買ってみたくなります。

また,1番目に関してはunix系のOSなら(というか何故か円マーク¥が表示されるWindows以外なら)問題ないですし,
2番目に関してもHHKBの日本語配列がだいたいこんな感じですがね・・・
ただ,4番目に関しては本当にmacOSならではですし,3本指アプリ移動と2本指でブラウザバックはもう戻れない感じがします。
あと,touch IDは地味に便利ですね。使っていきましょう。

本当は上の部分は導入にして,ABC119の話をするつもりだったのですが,前書きのほうが長くなったのでわけますm(_ _)m

*1:apple storeapple公式サイトからのみ

*2:家電量販店からすると利益率の少ない商品なので,あまり値引きしてもらえない

*3:HHKB:Happy Hacking KeyBoardという,エンジニア界隈に根強い人気があるキーボードシリーズ。静電容量無接点の数万円するやつは依存性が高いらしい。

AtCoder A埋め

久々のゴルフを兼ねてA埋め。ゴルフはこたつがめ氏が強すぎて萎えた。

ABC100

A - Happy Birthday!
Submission #2892439 - AtCoder Beginner Contest 100
「かつ」を示す「&&」のうち1個はいらないですね。a<9の返り値は0/1なので。

ABC101

A - Eating Symbols Easy
Submission #2892339 - AtCoder Beginner Contest 101
scanfで読み取っていますが、getchar()を使った方が短いです。
43は「+」の文字コードです。これも、s==43?...とやるより、t+=s/45;printf("%d",4-2*s);とした方が2文字少ないです。
45は「-」の文字コードで、char型を整数で割るとint型として計算されるので、s='+','-'のときs/45=0,1です。

ABC102

A - Multiple of 2 and N
Submission #2892151 - AtCoder Beginner Contest 102
includeしていますが、importした方が、cin/coutが使えなくなったとしても、短いですね。
また、n%2?2*n:nの部分ですが、n%2が1か0かによって2*nかnかを出力させたいので、n<<n%2という書き方の方が断然短い。
ここでの<<はビットシフト演算子です。例えばa<<bだと、aの2進数表記で立っているビットを左にbだけ動かします。
a=1、b=2のときはa_(2)=0000000000000001なので、1を左に2個動かしてa_(2)=0000000000000100となり、a=4になります。

ではではここで

AtCoder Beginner Contest 103 (ABC103)

ABC103に参加しました。遅刻しなかった上に全完したのでレートが96上がりました。やったぜ。

A - Task Scheduling Problem

問題文はこちら
回答コードはこちら

6通り全部試してもいいですが、A_i → A_j → A_k とタスクを行う場合、直感的に A_i ≦ A_j ≦ A_k がもっともコストが低そうですね。
なので、A_k = max(A), A_i = min(A), として答えはabs(A_k - A_j)+abs(A_j - A_i) = abs(A_k - A_i) = max(A)-min(A)となります。

B - String Rotation

問題文
回答

(問題文で言われたとおりに)やるだけ。
str.substr(index)でstr[index]から末尾までの部分文字列を示します。
また、str.substr(index,length)でstr[index]からstr[index+length-1]までの部分文字列を示します。
最初に、s=s+sとしておくとより簡単な実装になるかも。

C - Modulo Summation

問題文
回答

思考過程
aのそれぞれに対して m=(aの倍数-1)のとき嬉しいことは明らか。
つまりm=(全てのaの最小公倍数)-1とするとよい。
このときm%a=a-1となるので、∑(a-1)でよい。

D - Islands War

問題文
回答

思考過程
(Aの最大値)<(Bの最小値)なら答え1だねってのは分かる。
じゃあそうじゃないときは1番大きいaを脇によけてans++して、もう1回判定するってのを繰り返すとよくって、
脇によけたやつどうしで、それと同様の操作をする((Aの最大値)<(Bの最小値)なら答え+1,そうじゃないときは1番大きいaを脇によけてans++して、もう1回判定するってのを繰り返す)と良さげ。
わきによけるときはaとセットのbも一緒によけて、Aの最大値、Bの最小値を更新する。

ただ、それすると実装が重い。つか毎回最大値判定にO(m)使うからともするとO(m^2)で通らない。
のでaの昇順にソートする。→たぶん解説と一緒でO(n logn)。

でもこれって、別に脇によけるのは一番大きなaでなくてもよくって、
つまりすべての(a,b)についてa<(Bの最小値) && b>(Aの最大値)なら答え+1,そうじゃないときは(a,b)を脇によけてans++して、もう1回判定するってのを繰り返すをやればよい。
このときソートがいらないのでO(n)。
僕のコードはこのときにソートつけてても通るので提出時間意識してつけっぱ。

AtCoder Beginner Contest 094 (ABC094)

ABCの過去問。ショートコーディングしてみた。Cは配列2つ持つよりもlower_bound()使いたかったけど、実装力ぅ(イテレータを理解していないため)。難しそうだし眠いから諦め。kotatsugameさんはやっぱりショートコーディング強い。

A問題:Submission #2819377 - AtCoder Beginner Contest 094
B問題:Submission #2819431 - AtCoder Beginner Contest 094

Atomエディタの入力補完機能をいじくってみた

 おはこんばんにちは、u_shoです(=^・ω・^=)

 私はエディタとして、入力補完の優秀さなどの点からAtomを使っているのですが、
main関数やnamespaceの補完では、「競プロ向け」*1でない補完をしやがるので少しばかり不満に思っていました。

 そこで今回、Atomの入力補完機能(スニペットというらしい)を「競プロ向け」に魔改造することにしました。
参考はこのブログ↓
rfs.jp


 まずは「ファイル(もしくはEdit)」から「スニペット(Snippets)」を開きます。*2
f:id:u_sho:20180709233442p:plain
 そしたらこのファイル(snippets.cson)が開きます(たぶん)。Atomのバージョンとかによっては違うかも
f:id:u_sho:20180709233438p:plain
 んでこのファイルの末尾にこんな感じで書いてあげます。最初っから書いてあるやつはコメント(トリセツ)なので消しても消さなくてもいいです。
f:id:u_sho:20180709234055p:plain
 '.source.cpp':ってのが、このスニペットはcppファイルの中で使いますよ~ってことです。
次にはインデントをしっかり*3とってスニペットの名前(補完時に表示される)を書きます。
そこからインデントをしっかりとって'prefix:'以下に、この文字打ち込んだらスニペットを呼び出しますよ~ってのを書きます。私はsettingとしました。
次に、インデントをしっかり(しつこい)とったら'body:'以降にこーゆー補完して! ってのを書きます。$1で最初のカーソル位置、$2でタブキーで移動した後のカーソル位置を指定できます。私はいわゆる競プロテンプレートにしました。

 これで完成!!

試しにやってみる。
f:id:u_sho:20180709235620p:plain
setと打ってエンターキーを押すと・・・
f:id:u_sho:20180709235616p:plain
できた~(*´▽`*)

*1:個人の主観です

*2:画質が荒いのは通信量とかめんどくささとか諸々の関係

*3:ちゃんとインデントしないと認識されないので注意

ICPC過去問

先週金曜日(7/6)にICPC国内予選がありまして、私も出場しまして、まあ去年と同じく3完だったのですが、大会の熱に中てられまして、やる気が爆上がりしたので久々に精進をすることにしました。前のように解説とかは無理なので、解いた問題のリンク張るだけにしようかなと思います。
ICPC国内予選2015 A問題(すなおに解いた)http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3009207
ICPC国内予選2017 C問題(ごり押し全探索o(10^6))http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3009198