POJ2362 - Square

2362 -- Square

遅ればせながらid:Ozyさん、

Short Coding ~職人達の技法~

Short Coding ~職人達の技法~

発売おめでとうございます！私も今日（遅っ）購入させていただきました〜。ゆるゆると味わいながら読ませていただきます。サイン欲しいよ〜、サイン。


ショートコーディングとは関係ないけど、結城浩さんの

数学ガール (数学ガールシリーズ 1)

数学ガール (数学ガールシリーズ 1)

も購入。数学も大好きですけど、数学の読み物も大好きです。


で、Square。
長さが与えられたn本の棒で正方形を作れるかどうかを判定する問題。
素直に再帰で解いてみました。

続きを読む

現状報告

あまりに更新してないので生存報告でも。
最近はめっきりモンスターハンターフロンティアにはまってしまい、絶賛POJほったらかし中です。たまに気分転換にやったりしますが。知らない間にid:OzyさんがWiki立ち上げてたり、POJに問題が追加されてたり、気が付けばICFP終わってたり、、、
POJは1000問いったらガーっとまとめページでも作ろうかなぁと思ってはいるのですが実際やるのかは不明です。

PKU1941 - The Sierpinski Fractal

1941 -- The Sierpinski Fractal

タイトル通り。
最初に思いついたのが

  1. 2007-04-28を使う
  2. 普通に再帰
  3. オートマトン

の3つだったけど、結局(1)ならバッファが要らないのがでかくてそれで。
trailing spaceは1,2個なら余裕で通る。その意味で若干インチキコードと言えなくもない。

続きを読む

PKU3221 - Diamond Puzzle

3221 -- Diamond Puzzle
最近あんまPKUに時間がとれなくて、気がついたら新しい問題来てたのでやってみた。


変形15パズル。駒が7個しかなくメモリ制限も緩いので、階乗進法とか使わなくてもいけた。

続きを読む

PKU1731 -- Orders

うっひゃー、久しぶりの更新や〜。
PKU解くのが楽しくて、ひたすら解いてたらいつのまにかこんな時期に、、、


重複ありの順列を辞書順に出力する問題。
http://geocities.yahoo.co.jp/gl/nanagyou/view/20070210/1171061351で言及されてたりしたので晒してみる。あ、やっぱソースはじゃんじゃん晒していこうと思います(おい

今だったら瞬時にnext_permutation使うんだろうけど、若気の至りでGCCで書いてます。なんのひねりもなく再帰。

char s[99];
l,f[128];

F(i,k){
  for(k=96;++k<123;)
    f[k]?f[s[i]=k]--,F(i+1),f[k]++:0;
  l-i||puts(s);
}

main(){
  for(gets(s);s[l];)
    f[s[l++]]++;
  F(0);
}

135B。
あれ、、、いつの間にかスーパーpre記法が進化してる。さすがはてなさんです。
ていうか、いくらショートコーディング始めたころだからとはいえ、まったく同じアルゴリズムでこれより20B長かった、、、


最近ちょっと忙しくなってきたんですが、ぼちぼち更新していけるよう頑張ります。

PKU3075 -- Tic-Tac-Toe

○×の終局面が与えられて、それがありえるかどうかを判定。×からスタート。

うまい配列を使うと縦横斜めの判定をすっきり。ビンゴ系に使える？
○と×の個数と揃ってるラインで矛盾があるかどうかチェック。

277B。

頑張ればまだ縮むかも。