AtCoder Beginner Contest (ABC) 090 / AtCoder Regular Contest (ARC) 091 レビュー
AtCoder Beginner Contest (ABC) 090 / AtCoder Regular Contest (ARC) 091 の個人的解法解説とレビューです。
今回はABC/ARCのC問題&D問題のみとなります。
問題はこちらのAtCoder公式からどうぞ。
C - Flip,Flip, and Flip......
とりあえず解いてみる
最大のカード枚数は10^18
。全部シミュレートしてると間に合わない。
実際に操作してみる。
カードの置かれているマスの四隅は4回操作される。最終的には表になる。
カードの置かれているマスの辺上(四隅を除く)は6回操作される。最終的には表になりる。
その他のマスは9回操作される。最終的には裏になる。
ということで、カードの枚数-辺上(四隅含む)にあるカードの枚数
、つまりN*M-(2*N+2*M-4)
を出力すれば良さげ。
……ほんとかな?
カード1枚だけ、つまりN=1 && M=1
の状況だとどうなるだろうか。「四隅」「辺」が定義されないので、答えが変わってきそうな気がする。同様に、N=1 && M≠1
の場合も「四隅」が定義されないのでマズそう。
コーナーケースがありそうなので、順に調べていく。
N=1 && M=1 のとき(「四隅」「辺」の定義が不可能)
1回操作されるので、1枚だけ裏になる。上記の式に当てはめてみると……そのまま使えそう。
N=1 || M≠1 のとき(「四隅」の定義が不可能)
端の2枚は2回操作される。最終的には表。
その他は3回操作される。最終的には裏。
つまり、M-2
を出力すれば良い。上の式に当てはめてみると……1*M-(2*1+2*M-4)=-M+2
になってしまう。
修正する
コーナーケースがあるので、以下のように修正。
if(N==1 && M!=1){ //コーナーケース cout<<M-2<<endl; }else{ cout<<N*M-2*N-2*M+$<<endl; }
自分のソースコードだと無駄な条件分岐が……。
こんな感じで解けた。計算量はO(1)
。
D - Remainder Reminder
とりあえず解いてみる
愚直解は「1<=a,b<=N
を満たす組(a,b)
に対して、a%b>=K
であるかを確かめる」と言った感じだろうか。計算量はO(N^2)
。Nは最大10^5
なので間に合わない。
せめてO(N)
ぐらいには落としたいところ。ということで、「組の一方の値が与えられたとき
、有り得るもう一方の値の個数をO(1)
で求める」アルゴリズムを作ってみる(これなら、「与える一方の値」を1からNまで動かして和を取ることでO(1*N)
で解ける)。
計算量を削っていこう
bを「与える」と上手く行ったので解説。
表は、N=10の設定で「aをbで割った余り」を示している。余りがK=2以上のところには色が塗ってある。
値には、長さbの周期が見られることが分かる(表の赤線を参照)。
また、b>K
を満たすbについてのみ考えれば良いことが分かる。
表の中で「周期」がいくつ見られるかを「sequence」に記載した。この値はマス数/周期の長さ
、すなわち(1+N)/b
で求められる。
「周期」に含まれるマスの中で、余りがK以上のマスがいくつ有るかを「sequenceによるanswer」とした。この値はsequenceの値*一周期に存在する余りK以上のマスの数
、すなわちsequence*(b-K)
で求められる。
また、「周期」に含まれないマスの中で、余りがK以上のマスがいくつ有るかを「remain」とした。この値は周期に含まれないマスの数-K
、すなわち(1+N-sequence*b)-K
で求められる(負数になることがあるので、その場合は0扱い)。
以上の計算をすることで、「bの値が与えられたとき
、有り得るaの値の個数をO(1)
で求める」ことができた。bをK+1からNまで動かして和をとれば、O(N)
で解ける。
K=0のときがコーナーケース。この場合はN*N
を出力しておく。
まとめ
考察回&コーナーケース回避回だったなぁという印象。1WA吐きましたが、50分で二問解けました。
よっしゃよっしゃ
— Arc@競プロ (@arcslab123) March 11, 2018
rate 899->986(Highest)
perf 1453(Highest) pic.twitter.com/EiznrbLePT
最大パフォ更新。最近は調子がいい。
競技プログラミングを始めよう
追記: 2020年版を書き直しました
Arcです。今日はレビュー記事じゃない事を書きます。
新年度、なにか新しいことを始めたいと思っているそこのアナタに向けた布教記事です。
対象読者層
- 問わず
できるだけ専門用語を使わずに書いていこうと思います。
競技プログラミングって何それおいしいの?
人に説明するのが難しいんですが、僕が思うに競技プログラミング(以下「競プロ」)は「プログラミングをして様々な問題を解くスポーツ」です。食べ物ではありません。
競技性はもちろんあるし(競技プログラミングなんだからそれはそう)、生涯スポーツとしても有用です。
競プロには大きく分けて2つの楽しみ方があります。1つは「過去問を解く」こと。もう1つは「コンテストに参加する」ことです。
コンテストは「競プロの大会」。与えられた問題を解くプログラムを速く作る事が求められます。「解いた問題の難度」、「問題を解くのに掛かった時間」で順位が決められます。
また、過去にコンテストで出題された問題の多くは(全ては?)そのまま公開され続けるので、様々な問題を解きまくるのも楽しいです。
競プロの効果は?
C++が身につく
競プロではこのプログラミング言語が主流です。世界で幅広く使われています。
C++は「C言語」の上位互換言語なので、初めにC言語を学習してからC++へステップアップする、というやり方でもOK。僕はそうしました。C++はメチャクチャ複雑な言語なので、最初からC++だと言語習得で挫折しそう……。C言語はC++よりはシンプルです。
高度なプログラミング能力が身につく
競プロer(競プロをする人のこと)は世の中の平均的エンジニアと比べて相当高いプログラミング能力(特にアルゴリズム分野における能力)を持っているようです。ハイレベルな能力が自然と身につきます。
「競プロ界の『下の上』ぐらい」だと思っている自分がどこらへんのポジションにいるのかは分からない。
楽しい!!
最終的にはここに帰着します。高難度問題を解けたときの快感はたまらない。
どんな問題が出るの?
よしよし、ここまで読んでくれたということは興味を持ってくれたということですね?嬉しいです。具体的にどんなことをしているのか紹介します。
簡単な問題
たとえばこんな問題。
競プロの問題は、「時間制限・メモリ制限」「問題文」「入力」「出力」「制約条件」から成り立っています。
「問題文を読む」→「入力で与えられるデータを適切に処理して、形式通りに出力するプログラムを書く」→「書いたプログラムを提出する」というのが一連の流れです。
また、入力される値は「制約条件」に従っています。これが無いとメチャクチャ大きな値を入れられてしまうので……。
さらに、「時間制限」「メモリ制限」を守ったプログラムを書かなくてはなりません。
「時間制限2秒」の場合、プログラムを実行してから2秒以内に出力する必要があります。効率の悪いプログラムを書くと時間制限に引っかかってしまいます。競プロは効率化との戦い。
「メモリ制限128MB」の場合は、変数を格納する場所であるRAMメモリの使用量を128MB以内にする必要があります。専門用語が漏れてしまった。とりあえず理解できなくても大丈夫です(そのうち理解する必要はありますが)。
では、この問題について考えてみましょう。
入力Aと入力Bを受け取る (A*B)の値と、(A*2+B*2)の値を出力する
というプログラムを書けば良さそうですね。
この処理を記述して、サーバーに提出すると、サーバーがプログラムを実行してくれます。しばらく待つと、正解したかどうかが通知されます。「AC」と通知されたら正解。やったね。
難しめの問題
こんな問題も出ます。
初見で解けたら才能あります。保証します。
ほとんどの人はわからないと思います。僕も全然解けませんでした。でも、なんだかんだ言って解けるようになります。解けます解けました。
難しい問題をあーだこーだ考察するのが競プロの醍醐味、だと個人的には思っています。
どこで競プロができるの?
ざっくり分けると「ウェブ」と「オンサイト」です。
ウェブ
ブラウザでアクセスする形式。有名なサイトを幾つか紹介します。
AtCoder (たぶん)日本最大手の競プロサイト。毎週末にコンテストが行われています。僕も参加しています。いくつかレビュー記事書いてるので読んでね(露骨な宣伝)
Aizu Online Judge 通称AOJ。会津大学が運営している競プロサイト。後述の学生向けオンサイトコンテストで出題された過去問が充実しています。いわゆる「典型問題」もたっぷり。
yukicoder 問題を「出題できる」ことが特徴。僕も何か作ってみたい。
オンサイト
参加者が会場に集まって行うタイプ。「ウェブ上で予選コンテスト」→「オンサイトで本選コンテスト」といったパターンが多いです。
学生向けオンサイトコンテストを紹介します。
日本情報オリンピック 通称JOI。日本の高校生以下競プロerが参加できるコンテスト。ウェブで予選を行った後、最大80人ぐらいが本選へ出場できます。本選上位20人は「春合宿」に参加できます。
国際情報オリンピック(リンクは2018年日本大会) 通称IOI。世界屈指の高校生以下競プロerが出場するコンテスト。日本からは、前述の「春合宿」でいい成績を収めた上位4人(2018年のみオープン参加枠4人追加)が出場できます。
ACM国際大学対抗プログラミングコンテスト 通称ACM-ICPC、もしくはICPC。大学生競プロerが参加できるコンテスト。チーム戦であることが特徴。こちらも多くの予選を突破しないと世界大会には出られない。出てみたいです。
この他にも、IT系企業がオンサイトコンテストを主催したりしています。
必要なものは?
最低限、インターネットに繋がるPC1台でOK。ソフトウェアはいろいろインストールしないといけませんが……。
あとは問題考察用に紙とペン、リフレッシュ用に飲み物とかお菓子とか。
競プロしてみたい!
やったぜ。
そんなあなたに僕のオススメ学習法を伝授します(あくまで個人の意見ですが)。
以下、Amazonへのリンクを張りまくりますが、アフィリエイトでは無いことを一応書いておきます。
プログラミングの環境を整える
まずはPCでC言語・C++を扱えるようにセットアップします。
……といっても、ここらへんについては「ググれ」としか言えません。使っているPCによってやり方が異なるので……。
流石にこれだと投げやりすぎるので、いくつかアドバイス。最低限必要なソフトウェアは
です。以上2つが1つのソフトウェアとしてまとまっている「IDE(統合開発環境)」というのもあります。
使っているPCのOSとかにあわせて好きなものをインストールしてください。
とりあえずC言語を使えるようにする
前にも書きましたが、最初からC++を使おうとすると挫折する危険性があります。とりあえずCから始めましょう。
おすすめの教材はこちらの苦しんで覚えるC言語。だいぶ怪しげなタイトルですが、中身は非常に良いです。
よくあるC言語入門本だと「おまじない」とかいうファンタジーワードが羅列されているんですが、この本はそういった類の言葉を一切使わずにきちんと説明してくれることが特徴。「苦しい」と思うことはあっても、その後の理解度が半端じゃない。
「苦しんで覚えるC++」があったらC++から始めても問題ない、と言いたくなるぐらいの名著です。
簡単な問題を解いてみる
大体分かってきたな、と思ったら今度はアウトプットしましょう。全て理解してから、じゃなくても大丈夫。
基本的なことを学べば、簡単な問題は解けるようになります。
AtCoder Beginner Contest(通称ABC)にも出てみましょう。
(20180315 追記)
ここらへんのレベルまで辿り着いた方には、こちらのAtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~(drkenさん著)を読んでおくことをオススメします。AtCoder登録からABC参加の利点、重要過去問のピックアップ&解説までサポートしてくれます。
(追記ここまで)
アルゴリズムに手を出す
解けない問題に直面し、解説を読んでも「幅優先探索」「累積和」「動的計画法」とかいう謎ワードが並んでいて分からない……。
そういった感じになってきたら、「アルゴリズム」「データ構造」について勉強する必要があります。ようこそ競プロの真髄へ。
「アルゴリズム」とは、「プログラミングで問題を解くための手段」の事です。
「データ構造」とは、「プログラミングで効率的にデータを処理するための形式」の事です。
とりあえずこちらのなっとく! アルゴリズムを読んで雰囲気を掴みましょう。この本も名著だと思います。すげーわかりやすい。イラストがたくさんあるので視覚的にアルゴリズムを学べます。中身のソースコードはPythonという言語で書かれていますが、そこは分からなくてもなんとかなります。
今度はこちら、プログラミングコンテストチャレンジブック。通称「蟻本」。競プロerで持っていない人はいないんじゃないかと思うぐらいの「聖書」。主要アルゴリズムとデータ構造が網羅されています。
また、僕は持っていないのですが、プログラミングコンテスト攻略のためのアルゴリズムとデータ構造も良さげです。借りて読んでみた印象だと「なっとく! アルゴリズム」の内容をもう少し深めた感じ。
C++に手を出す
アルゴリズムに手を出すと同時に、C++の習得も目指していきます。
でも、「Cを学んだ人向けのC++入門本」を見たことがないんですよね……。僕はオンライン資料を読みまくることで乗り切っちゃいました(嘘です)
(20180306 追記)
オンライン資料で乗り切ろうとしていますが、そもそもC++を完全に理解するのは不可能レベルだという話もちらほら。
使う機能だけ理解しておけばいいと思います。
(追記ここまで)
ちなみにC言語でもJOI予選は突破できますよ。僕がその一人です。C++の方が圧倒的に便利だということに気づいたのは突破後の話。
この後
あとはひたすらアルゴリズムとデータ構造とC++の勉強して、コンテストに出まくるだけです。
これ以上書けと言われても書けない(´・ω・`)
どんどんコンテストに参加して実力を付けていきましょう。
まとめ
新年度の幕開けが近いということで、新生活のお供になるかもしれない記事を書いてみました。長文にお付き合い頂きありがとうございます。
以上で布教は終わり。この記事が、あなたが競プロの魔境に迷い込む世界に踏み出すきっかけになる事を祈ります。
更新情報
20180305/投稿
20180306/「プログラミングの環境を整える」追加、「C++に手を出す」追記、その他誤字修正
20180315/「簡単な問題を解いてみる」追記
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問題でだいぶ止まってたんですが、なんとか解けました。
計算量の削減目標を持って考えるの、大事だと思います。
結果はこんな感じ。
3次関数グラフみたいになった、やったね
— Arc@競プロ (@arcslab123) March 4, 2018
Rate:810→899(+89),Highest
perf:1363,Highest
水色レートとれたぜ pic.twitter.com/y9kFavmkrz
最高の成績でした(`・ω・´)
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問題早解きコンテストでしたが、実装に時間取られて死にました。
と思いきや
うおお!緑入ってた!死んでなかった! pic.twitter.com/u6laWCUCit
— Arc@競プロ (@arcslab123) 2018年2月24日
緑レート達成したぜ。やったね。
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無し全完」「全完タイム自己ベスト」「パフォーマンス自己ベスト」を達成できました。
しかーし。
グフォァァ(死) pic.twitter.com/UkF23tt0lx
— Arc@競プロ (@arcslab123) 2018年2月18日
こうなったんですけどね。惜しかった。
次回は絶対に緑レート行きます。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のアドバイスになれば幸い。
計算量見積もりはちゃんとしよう
制限時間とデータ量と問題ジャンルが分かれば自ずと解法が決まるような気がする(実装できるとは言ってない)
— Arc@JOIお疲れ様でした (@arcslab123) 2018年1月24日
こんなこと言ってるくせに何やってたんだか。
100,000,000(
=10^8
) 非常にシンプルな処理でない限り厳しい。(蟻本P20より)
とのこと。落ち着いて考えれば大体の計算量オーダーがわかる、と思う。
部分点戦略を考えよう
AtCoderだと部分点を得られる問題が少ないので、「ACかTLE(MLE)か」の二択になる。
しかし、JOIだと想定解より大幅に計算量が多くなっても(たまにO(N!)
でも)点がもらえたりする。
今回の問題は全て、全探索すれば小課題1あたりで点がもらえた。
ただ、一度「妥協したコード」を書いてしまうと、そこから想定解コードを作るには結構時間がかかる。最悪、コードをリセットしたほうが早い場合もある。
もちろん全課題ACしたほうが嬉しいが、残り時間なども考えて「この問題はしばらく粘ろう」「この問題は妥協しよう」といったことを検討するべき。
(追記 2018-02-16)
二完+(団子職人の課題2まで or 残り三問を全探索で部分点)で本選通過かな
— Arc@競プロ (@arcslab123) 2018年2月12日
個人的には2完+定期券ワーシャルフロイドの255点の方が可能性高かったかもしれない
— Arc@競プロ (@arcslab123) 2018年2月12日
まあ2完できなかった時点でア
JOI公式から本選Aランクボーダーが開示されたが、2完でボーダーに乗せるには多分上記の3パターンが現実的かと思われる。1完+部分点で無理やり本選通過しようとすると、
「問題AをAC(100点)+問題Bを課題3まで(50点)+問題Cを課題2まで(33点)+問題Dを課題3まで(55点)」
の、合計238点コースが妥当だろうか。けっこう非現実的ではある。
前日の睡眠を良質にしよう
今回宿泊した部屋は温度調節が大変だった……。
まあ、今回の宿泊場所に限らず、多くの人がホテルでは眠りづらいはず。
耳栓を持ってくる、加湿するなどして眠りやすい環境を作ろう。
競技中のエネルギー摂取手段を手に入れよう
だんだんネタに走っているような気がするが、結構重要。
今回は「粉っぽいモノ(ポテチなど)以外の菓子類を持ち込み可能」だったので、競技中にチョコレートを食べてた。(去年は違ったとの情報も耳にしているので、最新の規定はJOI委員会に尋ねてみることをおすすめします)
7時ぐらいに朝食を食べた後、9時から13時まで4時間頭を使ってたら、脳がエネルギー切れを起こすのは自明(僕だけか?)。
何か持っていったほうが良い。エネルギー切れ対策の他にもリフレッシュにもなる。
あと飲み物。魔剤を飲んでた人もちらほら。僕は飲めないが。
カフェイン取りすぎるとトイレが近くなるので注意。
体調管理のプロになろう
実は土曜日、若干熱っぽかったかも。体温測ってないので本当か分からないが。
無理して精進して体調崩したら元も子もないから気をつけよう。
あ、咳とか鼻水とかは無かったので、カゼでもないしインフルでもないと思います。ってかインフルだったら今ごろ倒れてる。
なにか思いついたら追加するかもしれないです。
まとめ
最初で最後のJOI本選だったわけですが、「もっと早く競プロやってればなぁ」と後悔しております。
実は、予選通過時にはまだ「競技プログラミング」ってのを知りませんでした。通過直後に知りました。
プログラミングは年齢より経験年数の方が遥かに重要だと思うので、まだJOI出場チャンスが残ってる&たくさん経験値を稼げる中学生・高1競プロ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
まず思いついたのは、
駅iに到着した時間=arrive[i]
として、arrive[i]<=S[i]+F[i]*n
となるような最小のnを見つける(次に乗る電車の到着時刻を計算)。arrive[i+1]=S[i]+F[i]*n+C[i]
これを終点に到着するまで繰り返す。
というもの。
だけど、このアルゴリズムだと(2)の処理にめちゃくちゃ時間がかかる。
そこで以下のように改良。
駅iに到着した時間=arrive[i]
として、駅iに到着してから次の電車が来るまでの時間=lag[i]
とする。もし
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
1つのクエリ(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年もプログラミング頑張りましょう。良いお年をお迎えください。