JOI2009-2010 予選報告
高校2年なので今年が最後のチャンスなのですが、参加しました。
一応全部解けました。
何とかして本戦でも頑張って、春合宿に行きたいものです。
とりあえずソースはそのうち載せるので今は解法だけ。
Q1
最初の入力から、あとの入力を引いていくだけ。
Q2
サイコロの目とすごろくのマス情報を配列に保存して交互に足していくだけ。
Q3
各生徒の友達リストを作って、1さんの友達の友達まで招待リストに加えるだけ。
入力例2「あなたには友達が居ない。」
Q4
nPkの順列を生成して、出現リストに加える。
最大99が4つ並ぶだけ(99999999)なのでint型に変換しても良い。
Q5
座標と元居た座標の方向(西or南)と直前に曲がったかの4つのパラメータでdp。
100*100*2*2=40000なので余裕で間に合う。
要素間の依存関係がちょっと面倒。
Q6
始点からの降り立った家のリスト(ビットで管理)と最後に降り立った家の番号でdp。TSPの変形。
ある家aから他の家bに渡るまでに上空を通過する家のリストをビットで保持しておき、
そのビットと降り立った家のビットでANDして0でなければ枝刈りとか。
あと23・2^23 * 4byte=736MBを確保するのは(PCによっては)難しいので、map
なんかすごい偉そうに書いてるけど、予選中は結構悩みました。
PC甲子園2003本選01
i;
main(j){
for(;i++<9;)
for(j=0;j++<9;)
printf("%dx%d=%d\n",i,j,i*j);
}
先輩が考えたもの。改行・Tabを除外して67byte。
11の倍数判定問題
ICPCアジア地区予選の模擬選があったので、参加資格は無いが問題だけ貰い解いてみた。
その中に11の倍数を判定する問題があったので、
11の倍数というものは10進数表示した整数にどのような特徴で現れるのかを調べてみた。
まず、1桁の場合。
数をと置くと、これが11の倍数であるのは
の場合だけである。
次に、2桁の場合。
数をと置くと、これが11の倍数であるのは
の場合だけである。
更に、3桁の場合。
数をと置く。
直感では分からないので、となるような数
を考える。
右辺を展開して整理すると、
左辺と比較すると、
が得られる。
真ん中の式に左右の式を代入してやると、
となる。
つまり、100の位の数と1の位の数の合計が10の位の数となるわけだ。
実際には、が繰り上がりを起こすことがあるため、
とすれば全ての場合に対して正しくなる。
4桁の場合は、説明は省略するけれど
は11の倍数なら
が成り立つ。
ここで、
1桁の場合の11の倍数である条件を、 と変形し、
2桁の場合の11の倍数である条件を、 と変形する。
そしてこれを一般化してわかることは、
「任意の整数nが11の倍数である時、nの偶数桁の数字の合計と奇数桁の数字の合計は、11を法として合同である」ということ(証明省略)。
そしてこれは実は必要十分条件であるので(また証明省略)、この命題の逆を取って
「任意の整数nの偶数桁の数字の合計と奇数桁の数字の合計が11を法として合同であるとき、nは11の倍数である」が成り立つ。
こういうこと。
ちなみに、Wikipediaの11のページにちょっと違う形で普通に書いてあった。。
