Arc's blog

競プロなど

AtCoder Beginner Contest (ABC) 089 レビュー

競技プログラミング

今回は良かったぞ。

AtCoder Beginner Contest (ABC) 089の個人的解法解説とレビューです。

問題はAtCoder公式からどうぞ。

A - Grouping 2

ソースコード

最大化問題。できるだけ3人グループを作っていきたい。

3人グループの数はN/3で求められる。

ここでちょっと考えると、N-N/3の答えは1か2。この余りをどっかのグループに押し込んでしまえばいい。

よって、N/3を出力すればいい。main関数がたったの4行だった。

B - Hina Arare

ソースコード

P W Gのひなあられが存在することが保証されている。

つまり、Yが存在すればFour、存在しなければThreeを出力すればいい。

C - March

ソースコード

名前の先頭の文字しか使わないので、残りの情報は切り捨てる。

名前がMで始まる人の数をtop[0]、Aで始まる人の数をtop[1]……とする。

「M,A,R」で始まる3人を選んだと仮定する。この場合の組み合わせ数はtop[0]*top[1]*top[2]で求められる。

うまくループを回して、全ての仮定パターン(5 C 3=10通り)の組み合わせの和を求める。

long longを使わないとバグることに注意(1WAした)。

D - Practical Skill Test

ソースコード

計算量はO(Q)かO(H*W)ぐらいだと予測。

なんとかして、キューに対してO(1)で答えられるようにしたい 。

最初はdp[i][j]=iからjまでのコストという形でメモ化再帰しようとしたが、O{(H*W)2}かかるので断念。そもそもメモリ確保ができない。

いろいろ考えてたら累積和を使う方法が降ってきた。

rui[i]={i%D(i%D!=0の場合),D(i%D==0の場合)}の場所からiの場所までのコストと定義。

すると、D<iを満たすiに対して、 rui[i]=rui[i-D]+(i-Dの場所からiの場所までのコスト)と計算できる。

キューに対しては、rui[r]-rui[l]を出力する。

計算量はO(H*W+Q)。

まとめ

D問題でだいぶ止まってたんですが、なんとか解けました。

計算量の削減目標を持って考えるの、大事だと思います。

結果はこんな感じ。

最高の成績でした(｀・ω・´)

AtCoder Grand Contest(AGC) 021 レビュー

競技プログラミング

大爆死

と思ってたらなんとか生きてた

今回はAtCoder Grand Contest(AGC) 021のレビューです。

問題はこちらのAtCoder公式からどうぞ。

A - Digit Sum 2

N以下の任意の値のうち、「各桁の数の和」が最大になるような値を見つけて、その値の「各桁の数の和」を出力する問題。

Nより大きくならないように、できるだけ9で桁を埋めていきたい。

下処理

まず、Nを、桁ごとに配列digit[]に入れる処理をしてみる。

ついでに桁数を表す変数lengthも用意したい。

とりあえず書いてみる

こんなコードを書いてみた。

int length;

long long power(int exp){//10^expを返す
    long long num=1;
    for(int i=0;i<exp;i++){
        num*=10;
    }
    return num;
}

int digitinput(void){
    int i=1;
    int remain;
    while(N>0){
        remain=N%power(i);
        N-=remain;
        digit[i]=remain/power(i-1);
        i++;
    }

    length=i-1;
}

こんな感じで、digit[1]にlength桁目、digit[2]にlength-1桁目、という風に値が入る。

しかし。

バグ発生

このコードを書いて、実際に数個のケースでACできることを確認したのだが、実行時にNの桁数が多くなるとFloating point exception: 8と表示されてしまう。

その名の通り浮動小数点周りのエラーみたいだが、原因特定できず。

しゃーない、別のコード書くか。

無理やり突破
void digitinput(void){
    length=SN.length();
    for(int i=1;i<=length;i++){
        digit[i]=SN[length-i]-48;
    }
}

なにをしたかお分かりだろうか……？

stringコンテナのSNに入力を突っ込んで、各桁のASCIIコードをdigit[i]に入れたあとに-48して数値化するクソコードを書いた。

ACできれば何でも良いんだもんっ

ようやく本処理

int solve_sum(int i){
    int sum=0;
    if(digit[i]==0){
        return 0;
    }else{
        int target;
        for(int target=length;target>i;target--){
            sum+=digit[target];
        }
        sum+=digit[i]-1;
        for(int target=i-1;target>=1;target--){
            sum+=9;
        }
    }
    return sum;
    
}

int solve(void){
    int max=0;
    int tempans;

    //maxを初期化
    for(int i=length;i>=1;i--){
        max+=digit[i];
    }

    for(int i=length;i>=2;i--){
        tempans=solve_sum(i);
        if(max<tempans){
            max=tempans;
        }
    }

    return max;
}

何をしているのか具体例で説明する。N=9876と仮定する。length=4である。

まず、max=9+8+7+6=30で初期化。

そのあと、「最高桁>i桁」まではdigit[]の値をそのままsumに加算。

i桁目ではdigit[i]-1を加算。ここでdigit[i]-1が負の値を取る場合は計算しない。

「i-1桁>=1桁」までは9を加算。

こうして計算されたsumを、iを減らしつつ全て試して最大値を出力する。

i=4 sum=8+9+9+9
i=3 sum=9+7+9+9
i=2 sum=9+8+6+9
i=1 sum=9+8+7+6

こんな感じでNを超えないように全探索してみた。

まだまだ計算量削れるかもしれない。43分かけてAC。

これ以降

わからん

まとめ

A問題早解きコンテストでしたが、実装に時間取られて死にました。

と思いきや

緑レート達成したぜ。やったね。

AtCoder Beginner Contest(ABC) 088 レビュー

競技プログラミング

2/18に行われたAtCoder Beginner Contest (ABC) 088のレビューです。

問題はこちらのAtCoder公式からどうぞ。

A - Infinite Coins

N÷500の余りが一円硬貨で払う必要のある額。

x=N%500として、x<=AならYes、違うならNo。

B - Card Game for Two

「残っているカードのうち、数が最大のものを取る」ことが双方にとっての最適な戦略。

C++なら降順にsortしたりpriority_queueに入れたりして、先頭の要素から順番に取っていけばいい。計算量はO(N log N)

sort priority_queueが無い言語でも、カードの数の情報を配列に保持して、「要素のうち最大の数を得点に追加」→「その要素を0に書き換える」という操作を繰り返せばACできる。計算量はO(V^2)。

C - Takahashi's Information

diff(1,1)=c(1,1)-c(2,1)、diff(1,2=c(1,2)-c(2,2),という風に、diff(x,y)=c(x,y)-c(x+1,y)と定義する。

すると、情報が正しいときは、少なくともdiff(1,1)==diff(1,2)==diff(1,3) && diff(2,1)==diff(2,2)==diff(2,3)が成立する。

上下方向の差の他に、左右方向の差も同じように計算して、条件が成立することを確かめる。

間違えても6重ループなんて実装したらダメだよ！

D - Grid Repainting

(1,1)から(H,W)までの最短路以外のマスを塗りつぶせばスコアが最大になる。

つまり、「初期状態の白マス数」-「最短路を通る時に通過するマス数」が答え。

「初期状態の白マス数」は、単に'.'を数えるだけで良い。

「最短路を通る時に通過するマス数」は、

struct{
    int h //h方向の位置
    int w //w方向の位置
    int grid //通過マス数
}

という感じに構造体を作って幅優先探索をかけて、(H,W)に到達したときのgridの最小値を求めれば良い。

到達済みのマスを再度探索しないように、bool型の配列などで到達済みかどうか管理しておくこと。計算量はO(H*W)。

まとめ

C問題でアホコード書いたり、D問題で深さ優先探索のコードを書いてしまったりして時間をロスしてしまいました。

でも「初めてWA無し全完」「全完タイム自己ベスト」「パフォーマンス自己ベスト」を達成できました。

しかーし。

こうなったんですけどね。惜しかった。

次回は絶対に緑レート行きます。AGCですが頑張ってパフォ稼ぎたい。

JOI終わってしまいましたが、やっぱり競プロは面白いですね。今日はこの言葉を書きたかった。

JOI2017/2018 本選のレビューとか教訓とか、今後の話とか

競技プログラミング

さて、第17回 JOI（日本情報オリンピック）2017/2018 本選が終わりました。今回はそのレビューです。

あと、教訓・来年度JOIerへのアドバイスとかもあります。

コードレビュー

110点しか取れなかったので、あまり参考にならない。僕の思考ルートを追いかけて楽しんでください。

A ストーブ

最近の本選は累積和・いもす法を最初の問題で使ってきたので、今回もそうかと思ったけど違うっぽい。

ということはDPか。とりあえずこんな感じでDPテーブルを定義してみる。

dp[a][b]=a人まで考慮して、b回マッチを使ったときの最小時間

すると、

dp[a][b]=min{dp[a-1][b]+(a-1人目の人が来てから、a人目の人が来るまでの時間),dp[a-1][b-1]+1}

で求められる。minの前者は「ストーブをつけっぱなしにした場合」、後者は「ストーブを消してつけ直した場合」に該当する。

しかし、ここで問題発生。ACするにはdp[100000][100000]を用意する必要があるが、そんなにメモリ容量がない。

dp[a][b]の[b]の方は、bとb-1の情報だけ持っておけば漸化式を回せるので、dp[100000][2]にしてメモリ容量圧縮を図った。でもTLE。

そもそも、計算量がO(N*K)=10^10なのでメモリ容量があってもAC不可能。このことに気づいたときには1時間を過ぎていた。

一度コードをリセットして、「つけっぱなしにした場合の時間」から「消しておいても良い時間の区間」をできるだけ多く引く作戦にした。

「消しておいてもいい時間の区間」は、a人目が来る時間とa+1人目が来る時間をそれぞれtx tyとするとty-tx-1で求められる。

これを全てのaに対して求めた後、降順ソートをかける。

マッチがk本あるなら、途中で消して良い回数はk-1回。「つけっぱなしにした場合の時間」から、先程降順ソートした「時間の区間」を上から順にk-1回引いていってAC。

long longが必要であることに注意。計算量はソートがボトルネックとなってO(N log N)。

B 美術展

なんかもうパニクっててBFSしてました。10点。

美術品それぞれに対して「入れる」「入れない」を判定するだけ。O(2^N)。

「その美術品を入れることによってS-(Amax-Amin)の値が減少するなら打ち切る」って感じで枝刈りしてみようとしたが失敗。ここでタイムアップ。枝刈り可能なのかすら怪しい。

解説を聞いたところ、累積和を使うのはこのB問題だった。

ここからは駆け足で。

C 団子職人

DPかなぁ……と思ったけど実装せず。

解説はDPでしたが、当日解説では理解しきれず……。

D 定期券

なぜワーシャルフロイドを思いつかなかったのか。あのアルゴリズム好きだったのに。（なお部分点）

たぶん、この問題を解いていたほうが点を稼げた。

E 毒蛇の脱走

高速ゼータ変換、かっこいい。

解説時のDEGwerさんのギャグセンスが高くて面白かった。

コードレビュー編はここまで。多分この後がメインコンテンツ。

教訓編

JOIに参加して得た教訓を書いてみる。来年度以降のJOIerのアドバイスになれば幸い。

計算量見積もりはちゃんとしよう

こんなこと言ってるくせに何やってたんだか。

100,000,000(=10^8)　非常にシンプルな処理でない限り厳しい。（蟻本P20より)

とのこと。落ち着いて考えれば大体の計算量オーダーがわかる、と思う。

部分点戦略を考えよう

AtCoderだと部分点を得られる問題が少ないので、「ACかTLE（MLE)か」の二択になる。

しかし、JOIだと想定解より大幅に計算量が多くなっても(たまにO(N!)でも)点がもらえたりする。

今回の問題は全て、全探索すれば小課題1あたりで点がもらえた。

ただ、一度「妥協したコード」を書いてしまうと、そこから想定解コードを作るには結構時間がかかる。最悪、コードをリセットしたほうが早い場合もある。

もちろん全課題ACしたほうが嬉しいが、残り時間なども考えて「この問題はしばらく粘ろう」「この問題は妥協しよう」といったことを検討するべき。

(追記 2018-02-16)

JOI公式から本選Aランクボーダーが開示されたが、2完でボーダーに乗せるには多分上記の３パターンが現実的かと思われる。1完＋部分点で無理やり本選通過しようとすると、

「問題AをAC(100点)＋問題Bを課題3まで(50点)＋問題Cを課題2まで(33点)＋問題Dを課題3まで(55点)」

の、合計238点コースが妥当だろうか。けっこう非現実的ではある。

前日の睡眠を良質にしよう

今回宿泊した部屋は温度調節が大変だった……。

まあ、今回の宿泊場所に限らず、多くの人がホテルでは眠りづらいはず。

耳栓を持ってくる、加湿するなどして眠りやすい環境を作ろう。

競技中のエネルギー摂取手段を手に入れよう

だんだんネタに走っているような気がするが、結構重要。

今回は「粉っぽいモノ（ポテチなど）以外の菓子類を持ち込み可能」だったので、競技中にチョコレートを食べてた。（去年は違ったとの情報も耳にしているので、最新の規定はJOI委員会に尋ねてみることをおすすめします）

7時ぐらいに朝食を食べた後、9時から13時まで4時間頭を使ってたら、脳がエネルギー切れを起こすのは自明（僕だけか？）。

何か持っていったほうが良い。エネルギー切れ対策の他にもリフレッシュにもなる。

あと飲み物。魔剤を飲んでた人もちらほら。僕は飲めないが。

カフェイン取りすぎるとトイレが近くなるので注意。

体調管理のプロになろう

実は土曜日、若干熱っぽかったかも。体温測ってないので本当か分からないが。

無理して精進して体調崩したら元も子もないから気をつけよう。

あ、咳とか鼻水とかは無かったので、カゼでもないしインフルでもないと思います。ってかインフルだったら今ごろ倒れてる。

なにか思いついたら追加するかもしれないです。

まとめ

最初で最後のJOI本選だったわけですが、「もっと早く競プロやってればなぁ」と後悔しております。

実は、予選通過時にはまだ「競技プログラミング」ってのを知りませんでした。通過直後に知りました。

プログラミングは年齢より経験年数の方が遥かに重要だと思うので、まだJOI出場チャンスが残ってる＆たくさん経験値を稼げる中学生・高１競プロerが正直言って羨ましいです。

僕も頑張ってACM-ICPCに出たいですねぇ。そのためには受験を突破しなければならないわけですが。

でも、1年以上ブランクを空けるのが余りにももったいない気がするので、これからもAtCoderのコンテストにはたまに参加したいと思います。

ということで、帰宅後に勢いで書いたJOI本選レビューでした。今度のリアルイベントはCombNafかな？

更新情報

2018-02-16 タイトルと本文をちょっとだけ変更、部分点戦略について追記

AtCoder Beginner Contest(ABC) 084 レビュー

競技プログラミング

今回は12/30のAtCoder Beginner Contest(ABC)084 についてです。

あ、前回のABC083ですが……全然ネタがないので飛ばします……

A - New Year

ソースコード

2日は48時間。48-MすればOK。

B - Postal Code

ソースコード

ハイフンが見つかる or 文字列の末端まで到達するまで文字数をカウント。これを二回繰り返す。

最初のカウント数＝=A and 二回目のカウント数==Bなら条件を満たす。

C - Special Trains

ソースコード

まず思いついたのは、

  1. 駅iに到着した時間=arrive[i]　として、

  2. arrive[i]<=S[i]+F[i]*n　となるような最小のnを見つける（次に乗る電車の到着時刻を計算）。

  3. arrive[i+1]=S[i]+F[i]*n+C[i]

これを終点に到着するまで繰り返す。

というもの。

だけど、このアルゴリズムだと（２）の処理にめちゃくちゃ時間がかかる。

そこで以下のように改良。

  1. 駅iに到着した時間=arrive[i]　として、

  2. 駅iに到着してから次の電車が来るまでの時間=lag[i]とする。

  3. もしarrive[i]-s[i]<0なら(まだ最初の電車が動いていなかったら)arrive[i+1]=S[i]+C[i] 、そうでなければarrive[i+1]=S[i]+lag[i]+C[i]

これを終点に到着するまで繰り返す。

で、lag[i]の計算方法は、

lag[i]=F[i]-((arrive[i]-S[i])%F[i])

もしlag[i]=F[i]ならlag[i]=0にする

という感じ。

これなら計算量少なくて済む。

D - 2017-like Number

ソースコード

１つのクエリ(l[i],r[i])に関して、l[i]<=n<=r[i]を満たす全ての奇数nをチェックするのは明らかに無駄。同じnに対してチェックを何回も繰り返すことになる。

たとえばクエリが(l,r)=(5,9),(3,11)なら、5,7,9は二回チェックしていることになる。時間が足りない。

ということで、累積和を使うことにする。

rui[i] = [1<=n<=i*2+1を満たす奇数nのうち、2017に似た数の個数]

と定義すると、クエリ(l[i],r[i])に対して

left=l[i]/2 , right=r[i]/2と定義し

  • left==0ならrui[right]を出力

  • そうでないならrui[right]-rui[left-1]を出力

以上の処理を実行することで解答可能。

で、「2017に似た数」をどうやって判別するかですが……「エラトステネスの篩」でググってみてください。僕は使いませんでした。完全に嘘解法です。

あと、この問題解いている時にコンパイラのバグ(?)に遭遇。プログラム上では書き込んでいないグローバル変数に勝手に値が書き込まれてました。AtCoderのシステムにソースコード投げたらあっさりACしましたが。

まとめ

  • 初めてABC4完しました。やったね。
  • でもARC上位陣が沢山いたからか、パフォーマンスはそこまで良くもなかったです。自己ベストだけど。
  • 茶レートにあがりました。
  • デバッグ用の出力はちゃんとコメントアウトしましょう。これのせいで1WA。
  • 実戦で累積和使えたので良かったです。
  • エラトステネスの篩ぐらい知っておこう……。

それでは皆様、2018年もプログラミング頑張りましょう。良いお年をお迎えください。

AtCoder Beginner Contest(ABC) 082 レビュー

競技プログラミング

今回は12/16のAtCoder Beginner Contest (ABC)についてです。

今回が初参戦となります。

僕のAtCoderのアカウントはこちらです。

問題はAtCoder公式をご参照ください。

A - Round Up the Mean

int型の割り算は小数点以下切り捨てなので、a+bに1足してから2で割れば切り上げた平均値が出てくる。

なぜか僕は(a+b)%2の値を見てから処理していましたが。

B - Two Anagrams

Cしか触ったことのなかった身にとっては、C++の　ちからって　すげー！　と思った問題。

stringコンテナのs,tを用意して文字列を代入し、sort(s.begin(),s.end()); sort(t.begin(),t.end(),greater<char>());を実行する。

すると、sの中身は昇順、tの中身は降順にソートされる。

で、if(s<t)がtrueならYes、falseならNoを出力。

ソートアルゴリズム書く必要もなし。strcmp使わなくてOK。そう、C++ならね

C - Good Sequence

数字nがm回出現したとき、

-n>mならm個消す

-n<mなら`m-n'個消す

というのを、全てのnに対して確認する。

この時、数字nが何回出てきたかをカウントする配列count[]が必要になってくる。

しかし、count[]の長さは普通に考えると109必要。メモリ足りない。

そこで、数列の長さNが105以下に制限されていることに注目。

105を超える数字nはn回以上出るわけがない。つまり、常にn>mを満たす。

ということで、105を超える数字が出てきたら無条件で消すことにする。

そうすれば、105以上の数字をカウントする必要がなくなるので、count[]の長さは105で十分。計算量はO(N)で解ける。

……模範解答は連想配列使ってましたね。研究が必要そうです。

D- FT Robot

最初は深さ優先探索して、その後メモ化したんですが、向き情報をDPの情報に入れていなかったので撃沈。タイムオーバー。

しかも、この方法ですらTLEになるらしい。O(N3)ならそこそこ速くない……？

x軸方向の移動とy軸方向の動きを分離すればO{N2}で解けるそう。

最初の提出時にデバッグ用のprintfを貼りっぱなしにしていたのは秘密。

まとめ

今回はstringの書式確認やらDPの凡ミスやら、時間の無駄遣いをしすぎました。

次回は変なミスしないようにします。

はじめまして

Arcと申します。

競技プログラミング、写真といったテーマについて書いていこうと思います。

ブログの目的としては

  • 自分の思考の記録
  • 文章力を上げる
  • 競プロなどの初心者の手助け
  • 覚書

こんな感じでしょうか。

とりあえず最初のうちはJOI本選に向けた勉強の記事でも書いていこうかと思います。

 よろしくお願いします。

 

Twitter（本垢＆競プロ垢）::　

Arc@競プロ (@arcslab123) | Twitter

Twitter（写真垢）::

Arc@写真 (@arcslab_photo) | Twitter

Instagram::

Arcさん(@arcslab_photo) • Instagram写真と動画