JOI布教用チラシ(図抜け)

【追記】ちゃんとしたやつをここにあげたのでそっちを見てね。

eiya5498513.hatenablog.jp

 以下元記事...

 

 

情報オリンピックとは

与えられた問題を解くプログラムを書きます。

しかし普通にやると、実行に一時間や一日、場合によっては一年かかるような問題が出題されるので、発想や良いアルゴリズムを使って一秒以内に実行できるように工夫します。

予選、本選、春合宿、国際情報オリンピックと好成績をとるごとに上の大会に出られます。

 

参加のメリット

・大学入試の際AO、推薦で有利

・IT系に強い人と人脈を作れる

・プログラムの実行時間に対する理解が深まる

・プログラムを書くのに必要な要素を正確に把握する力が付く

・楽しい ※個人の見解です

 

参加について

例年通りなら個人での参加となります。

予選は、家で自分のPCからネット上のコンテストに参加する形になります。

本選以降は、会場に行って準備されたコンピュータを使って参加します。

コンピューター部に本選経験者がいるので、興味のある人はコンピューター部部室まで来るか、****のところまで来てください。

(プログラミング講習の始まる前にもたまにいるので、そのときに声をかけてもらっても良いです。)

むやみやたらと過去問を解いてもなかなか上達しませんが、ちゃんと勉強すれば本選は十分目指せます。参加したい場合はぜひ声をかけてください。

 -------------------------------改ページ----------------------------

例えばこんな問題を解きます!

Ants(POJ No.1852 )

長さLcmの竿の上をn匹のアリが毎秒1cmのスピードで歩いています。アリが竿の端に到達すると竿の下に落ちていきます。また、竿の上は狭くてすれ違えないので、二匹のアリが出会うと、それぞれ反対を向いて戻っていきます。各アリについて、現在の竿の左端からの距離x iはわかりますが、どちらの方向を向いているのかはわかりません。すべてのアリが竿から落ちるまでにかかる最小の時間と最大の時間をそれぞれ求めなさい。

ただし、1≦L≦106, 1≦n≦106, 0≦xi≦L とします。

 

間違った解法

・すべてのアリの向いている方向を全通り試す

考えられる蟻の向きは 右右右...右右右

           右右右...右右左

           右右右...右左右

           右右右...右左左

              ...

           左左左...左左左

向きのパターンは、各蟻について右か左か決めるので、2n通り。

nが最大で106なので、大体10301030(30万桁!)のパターンがあります。コンピュータはとても大雑把に言って一秒に107(一千万)回の計算が出来るので、これで計算すると計算が終わるのが1030100(3万桁!)年後!!太陽系が余裕で滅びます。工夫して計算回数を減らしましょう。

 

最大の和(JOI2006本選)

n 個の整数からなる数列 a1, a2, ..., an と正整数 k (1 ≤ k ≤ n) が与えられる.このとき, 連続して並ぶ k 個の整数の和 Si = ai + ai+1 + ... + ai+k-1 (1 ≤ i ≤ n - k + 1) の最大値を出力するプログラムを作りなさい.

1 ≦n ≦100000, 1 ≦k ≦n , -10000 ≦ai ≦10000

実行制限時間は一秒

 

間違った解法

1~k番目、2~k+1番目...、n-k+1~n番目までの和を求める。

一回の和を求める計算で、k-1回足し算し、これをn-k+1回行うので、n=100000,k=50001のときに、50000*50000=2.5*109回計算する。

これだと、10~100秒くらいかかるので、「実行制限時間は一秒」の条件を満たせない!

  -------------------------------改ページ----------------------------

例題の解法

Ants

ヒント:蟻がすれ違ったときどうなる?

まず最小の時間は、すべてのアリが近いほうの端に向かうとしてしまえば良いです。この場合、二匹のアリが出会うことはなく、これより短い時間で端に到達することはできません。

次に、最大の時間を考えます。

アリが出会った場合にどうなるかをよく考えてみましょう。

実は、二匹のアリはすれ違ってそのまま進んでいったと思ってしまっても何も問題ないことがわかります。

 

 

 

このように考えると、すべてのアリは独立に動けるようになるので、最大の時間を求めるためには端までの距離の最大値を求めればよいことになります。

 

 

こうすると、パターンが一通りずつになり、衝突も考慮しなくて良くなり、蟻の匹数回(n回)計算するだけになります。

これは計算回数が最大106になって、一秒以内で解けます!

 

 

 

参考資料:プログラミングコンテストチャレンジブック第2版

 -------------------------------改ページ----------------------------

最大の和(JOI2006本選)

ヒント:和を高速に求めよう

「1~k番目、2~k+1番目...、n-k+1~n番目までの和を求める。」という方針はあっています。

これらのk個の数字の和を高速に求めましょう。

 

累積和を使う方法

Si = a1 + a2 + ... + ai (つまり、a1からaiまでの和)をS1からSnまで計算します。

このとき、Si+1 = Si + ai+1 を利用して、S1から順番に計算することで、一回のSiの計算を足し算1回で済ませることが出来るので、Snまで計算してもn回しか計算しません。

Siがあると、k個の値の和を引き算一回で計算できます。

例えば、

2~k+1番目の和 = Sk+1 - S2

3~k+2番目の和 = Sk+2 - S3

となり、

i~k+i番目の和 = Sk+i - Si

と計算できます。

(1~k番目の和だけはSkで計算します)

これで合計2n回≦200000回の計算になるので、一秒に間に合います。

 

尺取り法を使う方法

1~k   番目の和 = a1 + a2 + a3 + ... + ak

2~k+1番目の和 =     a2 + a3 + ... + ak + ak+1

3~k+2番目の和 =         a3 + ... + ak + ak+1 + ak+2

と、順番に計算する場合、ずれていくことを利用します。

まず「1~k 番目の和」を計算します。次に、

2~k+1番目の和 = 「1~k 番目の和」- a1 + ak+1

と計算します。同様に、

i~k+i番目の和 = 「i-1~k+i-1 番目の和」- ai-1 + ak+i

と計算していきます。

始めの「1~k 番目の和」を求めるのがk-1回の足し算です。

一回の計算に足し算と引き算が一回ずつで二回の計算で、これをn-k+1回繰り返すので2*(n-k+1)回の計算です。

これで合計2n-k -3回<200000回の計算になるので、一秒に間に合います。