うーん、就職活動うまくいかないな

東京に面談に行った。

ＩＴ系の会社、近くに六本木ヒルズや警官3名に護送車が表門に立っている中国大使館。

税務署や大きな消防署と都市機能が集中している近辺にある会社。

初めての東京行きに家族と一緒に駅探で電車時刻を調べたり。

当日は会社に近い地下鉄駅に気付かず、遠くから1ｋｍも歩いたりした。

一時間も前に会社の前について六本木ヒルズの下で時間をつぶしたり。

小説やテレビやゲームでよく出てくる六本木ヒルズ。

見上げてもあまり感慨がわかない。

東京といっても、そんなにすごいという感じはしないな。

地方都市がプチ東京化して、ここは神戸に、ここは明石に、ここは姫路に似ているな。

とそんな感じで新鮮さは感じない。

こち亀の、水路の上を通る高速道路を電車の車窓から見たときが一番印象に残った。

これは感性がバーチャル化していて記号を通して現実を見て印象に残ったのだろう。

日本人的感性ともいえる。

考えたら万葉集の昔から日本人は自然の名所を記号化して扱っていたのだし。

浮世絵も地方名物風景の記号化。

そういう意味では僕は典型的日本人の尻尾なのかもしれない。

会社はいい場所に立っているだけあって中々立派な会社に仕事だ。

面談で聞かされたのはネットの教育関係サービスを扱っている会社だということだった。

当然私の年では即戦力が求められるが、全く触ったことがない人でも入ってる。

という説明を受けたりした。

採用試験となるプログラムの問題で2/3を大雑把に選別にかけ、その後10％を選ぶ。

10倍以上の倍率の採用試験は突破したのだがそのあとにうけたこの面談は通らなかったようだ。

返事のメールは来てない。

面談中。

Ｍｏｏｃという単語をだしたら相手の顔が一瞬変わった。

この単語は採用担当が喜ぶ単語だったらしい。

しかし落ちたのだった。

まあ職歴悪い俺では仕方ないか。

ブラウザパズルゲームを考えてみた

蛇の道は蛇。

サブタイトル

蛇の寝床。

連なったボールをの両端をクリックアンドドラックで移動し同じ色のダイヤの上全てに同じ色の丸を持ってこれたらクリアというゲーム。

移動して

操作方法

丸は空白マスか線のマスへ移動できる

線は空白マスと同じ扱い

線の隙間を通って移動する。

他のボールが占めている場所へは移動できない。

もちろん2色以上を所定の位置に持ってくるステージも作成すれば面白くなります。

色数とボールの連結線の数を増やせばＧａｍｅ性が出てくる可能性を期待します。

追加要素

ボールが侵入できない移動不可のブロックマスや、その上を移動するとボールの連結が増える減るギミックなどの可能性を考えます。

アイディア考案者

堀江伸一

mail sinapusu2002@yahoo.co.jp

中二病な記述

根が複雑な分岐を繰り返し地の中で複雑に絡み合ったとき、地から吸い上げられるもの。
葉の裏にある気孔、リズム正しく息遣いから吐き出されるもの。
空で白い光のノイズとなるもの。
陽光を浴びてキラキラと輝くもの。
空からポツリポツリとふるもの。
寒い時に吐く息から見えるもの。
空から結晶となって、ユラリユラリと落ちてくるもの。
地面を暴れまわるもの。
大地を削っていくもの。



ゲームは状況を表現するという新しい段階に入った。
任天堂は古いゲームの経験値を膨大にためているがそれに気づいていないっぽい。

この状況というのを私は、うまく説明できない。



大雑把で大げさなわかりやすい少ないポリゴンモデルで表現されていたものが昔のモデルだった。
今は一流の俳優のようなしぐさの連続がプレーヤに与える印象の差。
これは人間関係や人間の心理に与える演出という状況が作り出されている。


巨大な生き物が森の木をなぎ倒して、その横を主人公が見つからないように歩く。
という状況は、画面やエフェクトやなぎ倒される木などが綺麗に表現されないとそのドキドキ感は、それが低質な画面で作られたゲームでは表現できない、質が根本的に違う。



ＣＰＵの心のモデルが多様になったら、それを組み合わせたり、心の状態が自然変化しそれが複数のキャラで関連を持たされるとき、新しい付加価値を作れる。
心のモデルがゲームに与える影響という状況が表現できるようになっている。


うまく説明できない。
小さな惑星から飛び立って宇宙に出て隣にある小さな惑星に入るとそれがシームレスに描画される。
そしてその移動はユーザーの自由になる。

聖剣伝説２でフラミーの操作が可能になった時、それは空を自由に飛び回るという状況をえんしゅつできた。
これはブレイクスルーだった。
ハードの進化なくしてはこの状況の表現（空を自由に飛べる）は不可能だった。

今のゲームもこういう状況を構築でき計算する力が出てきたからこそ発生する状況。

こういうのは確かに状況的な何かがある。

うまく説明ができないが、いまゲーム業過はなにかが確実にかわってるんだなたぶん。

ナーガールジュナの中論を少しだけ読む

仏教のことは右も左もわからないが。
読んで何となく感じたこと。

仏教においては時間の概念は認められず、ダルマの縁起が変化することで進む。
つまりコンピュータのシミュレーションに近い。


また、五感に関する話などはどう考えてもヴァラモン教を意識している。
両宗教ともにインド人の共通認識から生まれてきたから似ているのか。
それともヴァラモン教の構造を仏教が間借りしたのかよくわからない。

仏教のことはわからないので中論は全く持って私には意味不明だが。

なんとなく感じたことは。
つまり現代風に解釈すると計算速度無限大のコンピュータの上で世界が走っているとしたら、定数解以外意味がないと主張してるように感じた。

現代人が時間の経過だと考える世界計算の途中解は計算速度無限大なので意味がないとナーガールジュナは主張してるのではないか？

とりあえずわかったことは仏教は難しいので私には全く分からないということだけだった。

何せ中論では、何物も同一のものは無い。
何物も常在するものは無い。

このルールがダルマにまで適用されるとしたらどんな結論がでるのか？
多分そういうことを中論は窮理したのではないかとは思う。


書けば書くほどこいつ仏教分かってねえなと思われるだろうけど感想を書いてみる。


時間という概念を認めないことからくる色々な矛盾を、中論は縁起とダルマの改善で解決しようとした。
土台が間違ってるから理屈が立派でも中論は砂上の楼閣だとは思う。


まず、インド人は輪廻転生、世界の無限循環という観念の中で生きていた。
だからものが形を変えても世界からなくなることはない、表面上形を変えてもアートマンやブラフマンという本質は変わらないとインド人は考えた。
縁起がなくなればものがなくなるという仏教はこれと矛盾する。
これは解決されねばならない。


また物事や人が変化しつづけるということは縁起からはうまく説明できない。
ダルマの縁起は成立してる間は固定的である。
しからば変化するはずがない。

ダルマの中に変化（去ることと翻訳される）という要素があればそれは常にダルマの関係である縁起の中に存在する。

変化の一種である去ること（縁起がなくなること）がダルマの要素なら、それはダルマが縁起を持った瞬間に発動して縁起が存在できなくなるはずである。

これから去る物の中には、まだ去るという要素をダルマはもつことができない。
今去ってるものの中では、ダルマは自身を消去してしまうので去ることを要素として持てない。
去ったものの中にはもう去ることという要素はダルマの中には存在してない。


すると変化はどこに存在するのか？


これを解決しようとしたのかもしれない。

感想者
堀江　伸一

無意味な日本語羅列

砂を噛むような気持ち。

コンドルが脇をかすめる。

霧の中を進む。

霧の中の影はなんだ。

赤ちゃんの笑顔。

今夜は豆腐鍋だった。

神はいるのか？

熱心に議論している変人だ。

アート。

アーティスト、宗教家、ディトレ、ニート。

彼らが物語を進める。

ニンジンを短冊に切り、青菜を重ねて切り刻み豚肉を煮立てた鍋に入れる。

夕食の風景。

４人で囲む鍋、冬。

あかちゃんはアーティストの子供だ。

妻は別居し、パリで活躍しているという。

東京の下町。

浅草。

２ＬＤＫアパートで鍋をつつく４人。

ＡＯＪ Sort II - Minimum Cost Sort

会津大学オンラインジャッジ。
問　ALDS1_6_D

Sort II - Minimum Cost Sort

の解法。
問題原文はこちら。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_D


独自解法。

配列の要素をマスとし、ソート後にあるマスに入る数字をそのマスの正しい数字と定義します。

問題の着目点。
要求されるタスクは、4,1,3,5
とあったとき
1を正しいマスに確定する。
3を正しいマスに確定する
4を正しいマスに確定する
5を正しいマスに確定する
ということです。

これを踏まえて解法を考えます。

解法は以下の通り。

処理Ａ
数字列が与えられたとき、一番小さな数字に注目します。
一番小さな数字の入ってるマスに入る正しい数字。
これと一番小さな数を交換します。
一番小さな数が自分の正しいマスに入るまでこの作業を繰り返します。
正しいマスに入れば処理は終了です。

次は２番目に小さな数３番目に小さな数、、、も同様に処理Ａを繰り返します。


これは、一番小さな数と、その小さな数のあるマスを正しい数で交換すれば、正しい数は最も低いコストでマスを確定できるのでこの処理は妥当です。



しかしこれだけでは処理はうまくいきません。
２番目に小さな数以降を処理する場合。
その数をｍ番目に小さな数だとします。

処理Ｂ
まず処理Ａをした場合を考え、この時の交換手順をＲとして記録します。

処理Ｃ
次にｍ番目に小さな数と一番小さな数を入れ替えてその後はＲの交換手順通りに交換し、入れ替え終了後ｍ番目に小さな数と一番小さな数を交換した場合。

Ｃのほうがコストが小さくなる場合があります。
Ｂ，Ｃを検討し、小さいほうを処理Ａのコストとして確定します。


しかしＲという点ではＢもＣも同じ処理ですから、処理Ｂの副産物として簡単に処理Ｃの場合のコストが出ます。

後は上記処理を効率的に実装した結果。
私の場合この問題の最悪の計算量はＢｉｇＯ　1000*log(1000)という結果となりました。





ＡＯＪを知っている方ならコードが合格したらまず解法に間違いがないとご理解いただけると思います。
私は６時間ほどコードをいじくりながらああでもないこうでもないと一人考えました。
その結果上記解法を思いつきこれに従いコードを実装したところ合格したので。
まず解法に間違いはないと思います。



解法者
兵庫県加古川市加古川町南備後79-16
堀江伸一

バーチャル株式は

自分の無能さを、金額とランキングという形で見事に映し出してくれる鏡だな。
いやあ鏡をみといてよかった。
太った体でスポーツ大会に出るような愚行をおかすところだった。

素晴らしいね。
それにしても上位の人はすごい。
あっという間に１０００万の元手で1000万以上稼いでる。
一気に大量買いする度胸と分析力だろうか。

凄いのは上位の人は安定して上位だという点がすごい、運ではなく実力なのだ。
将棋の名人とペーペーぐらいの差が現実としてあるのだと。
そう実感した。





堀江　伸一

ナンセンス詩の練習

何故がない。
時がない。
大地がなければ宙もない。
広がりがない、心がない。
あなたがなく私もいない。
執着はない。
それは執着を持たない。
執着という概念がない。

言葉が無になる。
言葉が虚になる。
虚空から来るものだ。
虚空より来たるものだ。
虚空を引き連れてくるものだ。

全てが飲まれるぞ。
全てが飲まれるぞ。

さあ、あなたに時はない。
刹那の時すら与えられない。

それは一瞬であなたを飲み込むぞ。
全てがのっぺらぼうだ。

さあ覚悟はいいか。

ＭＭＯ系のゲームでほしい機能

Ｙａｈｏｏ知恵袋に投稿したものを書き直してみた。


キャラクター操作型（見下ろし型など）のＭＭＯ系ゲームでほしい機能。

落し物集積場。
敵にやられるともってるアイテムが消えることのあるゲームで、
アイテムが消えるとき低確率でアイテムが消えずにどれかの落し物集積場にランダムに移動。

落とした人の名前付き落し物アイテムというアイテム（以下落し物）に変換されて集積場に集まる。
落し物は使用不可なアイテムで捨てるか渡すしかできない（渡すがないＧａｍｅでは不可能ですね）

落し物は、落とした本人は拾えない。
ただしどのプレーヤも他人の落としたものを落し物集積場から拾える。
落し物集積所からは一時間に一回だけ拾えるとする（落し物集積場に張り付く人を出さないため）

落し物をもった人が元の持ち主の近くに行くと。
落し物がアイテム欄から消え。
公式からのプレゼントの形で（渡すができないＭＭＯのほうが多いから）元のアイテムが落とし主のもとに帰ってくる。
落し物を渡したほうにも報酬の形でアイテムかゲーム内通貨が出される。

4流同人小説

なんか4流同人作家な自分を知っているけれど何か書いてみたい的な記事。
ここまでレベルの低い作品をよくかけるなという視点で見ていただけたらと思います。
しかし閲覧数0のこのブログに記事を書く私自身の理由とは何だろうか？
自分でもよくわからない、、、


作品Ａ
つまるところ小説なんてものはだ。
友人から借りた車で事故った。
友人になんて謝ろう。
みたいなそんな話でも読者の感情の念をうごかさせることはできるのだろうと思う。
腕の悪い作家ほど、大きな事件や大仰な仕掛けに頼って自分の能力の低さを糊塗しようとする。
作家自身が人間としてしょぼいことから目をそらさせるための目くらまし。
大仰な設定とは詰まる所そういうことなのだろう。
、、、記述中



作品Ｃ
クライム小説のアイディア。
物語前半では何気ない一人の男の日常と時々会う人とマジわされる奇妙な会話。
会社らしき場所での一見平凡に見える事務作業など。
物語中盤では実はその男は大掛かりな組織的詐欺の一員であり前半の動きは全て犯罪と関係があったことが読者に判明し。
そこに主人公の恋人が絡んできて、、、
みたいな小説書いてみたいな、、、







作品Ｂ
バイオソルジャーというのをどう説明すればいいかな。
世間一般に流布しているのは、100ｍを7秒で走れるとか、武術の達人と戦えば一瞬で制圧できるとか。
超人的な兵士、まあそんなところだろう。

でもバイオソルジャーの強みはそこじゃない。
猫みたいな俊敏な反射と人としての理性が明確に分離されること。
そこにある。
遊離病患者に近い感じとでもいおうか。
目の前の事態に対し体が自動で動いて、理性は理性で視野全体で起こったことを冷静に分析している。
だから猫みたいに俊敏に動くけど猫のように間抜けな罠にはつかまらない。
危険をするりとすり抜ける。
銃撃が鳴り響く中でもわずかな音を聞き逃さずに危険を察知する。
だから私たちバイオソルジャーの死亡率は極めて低い。
何せ間抜けな兵士が足音をどかどかさせてくれば音だけで誰がどこにいるのかわかるのだから。
市街戦では私たちは一級品だ。


その一人である私も中東での任務を終えて、今は民間復帰のためのキャンプを終えた。
バイオソルジャーというのは脳配線のレベルで戦いが自動化されている。
日常に戻った時こいつが誤動作しないよう、脳の配線が消える処置を病院で定期的に受けるし。
隔離するために僻地のキャンプで暮らし、その間は大自然を満喫できる。
銃弾も爆撃もない平和な日常だ。

この話は、戦場の話じゃない。
バイオソルジャーがキャンプを終えて日常に戻るためのホームスティ先での話なんだ。
ＰＴＳＤは問題じゃない。
戦場で起こるストレスは全部遊離病が引き受けてくれる。
自動化されてる部分が残って誤動作しないか。
猫に戻らないかって話になる。
、、、記述中



私の好きな曲

ココロオドル
車輪の唄
全力少年

Bad Apple!! ＰＶ【影絵】

不完全燃焼

One more time, One more chance

見事に精神年齢の低さを暴露してるラインナップｗ

プロジェクトオイラー問217 Balanced Numbers

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20217
４７桁までのバランスのとれた整数全ての合計を3^15で割った余りでこたえる問題。
バランスのとれた数とは数字を真ん中で左右に区切って左と右別々に各桁の和をとった時、両側の合計が同じになる数のことである。
奇数桁の場合真ん中は無視してもよいようだ。


たぶん数式で求めるのだと思いますが私は数学の知識が乏しいので動的計画法で解きました。
意外と考えるパターンや桁あふれが多く結構苦労しました。
パズルゲームみたいで解いてて楽しい問題でした。


#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>

const int T=47;
const int LIMIT=T*9+10;
__int64 dp[T][LIMIT],permDP[T][LIMIT];



int main(){
      __int64 ans=45,temp,m=10,mR=1;
      __int64 MOD=pow(3,15);
      memset(dp,0,sizeof(dp));
      memset(permDP,0,sizeof(permDP));
      for(int i=1;i<10;i++){
            dp[0][i]=i;
            dp[T-1][i]=i;
            permDP[0][i]=1;
            permDP[T-1][i]=1;
      }
      for(int i=2;i<=T;i++){
            int p=i/2-1;
            int revP=T-p-1;
            if(i%2==1){
                  m=(m*10)%MOD;
                  mR=(mR*10)%MOD;
                  permDP[0][0]=1;
                  for(int j=0;j<10;j++){
                        for(int k=0;k+j<LIMIT;k++){
                              dp[p+1][k+j]=    (dp[p+1][k+j]    +dp[p][k]      +j*mR*permDP[p][k])%MOD;
                              dp[revP-1][k+j]= (dp[revP-1][k+j] +dp[revP][k]*10+j*permDP[revP][k])%MOD;
                              permDP[p+1][k+j]=(permDP[p+1][k+j]+permDP[p][k])%MOD;
                              permDP[revP-1][k+j]=(permDP[revP-1][k+j]+permDP[revP][k])%MOD;
                        }    
                  }
            }
            __int64 d=ans;
            __int64 test;
            for(int j=0;j<LIMIT;j++){
                  //if(permDP[p][j]==0||permDP[revP][j]==0)continue;
                  test=((i%2==0?0:permDP[p][j]*permDP[revP][j])%MOD*mR*45)%MOD;
                  temp=((dp[p][j]*permDP[revP][j])%MOD*(i%2==1?10:1)+(dp[revP][j]*m)%MOD*permDP[p][j]*(i%2==1?10:1)+test)%MOD;
                  ans=(ans+temp)%MOD;
            }
            std::cout<<"T="<<i<<" "<<ans<<" d"<<ans-d<<"\n";
      }
      std::cout<<"ans="<<ans<<"\n";
}

会津大学オンラインジャッジ 問

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_5_A&lang=jp
平面上に散らばった１０万点から最も近い２地点を選ぶ問題。

ｘ、ｙ座標の順でソートして左から右へ平面走査をしていけばよいです。
素朴に実装したら何かメモリ使用量が大きくなりました。




#include<stdio.h>
#include<map>
#include<set>
#include<math.h>

struct P{
      double x,y;
      bool operator<(const P& p)const{
            return y<p.y;
      }
};

std::map<double ,std::set<double> > Ps;


int main(){
      P p;
      int n;
      double x,y;
      scanf("%d",&n);
      while(n--){
            scanf("%lf %lf",&x,&y);
            Ps[x].insert(y);
      }
      std::map<double ,std::set<double> >::iterator it;
      std::set<double>::iterator sItD,sItU;
      std::set<P> Left,Dells;
      std::set<P>::iterator pIt;
      double ans=1000000;
      for(it=Ps.begin();it!=Ps.end();){
            sItD=(*it).second.begin();
            sItU=sItD;
            sItU++;
            while(sItU!=(*it).second.end()){
                  double dy=fabs((*sItU)-(*sItD));
                  if(dy<ans)ans=dy;
                  sItU++;
                  sItD++;
            }
            sItD=(*it).second.begin();
            sItU=sItD;
            sItU++;
            double x=(*it).first;
            double dy,dx,dy2;
            Dells.clear();
            for(pIt=Left.begin();pIt!=Left.end();){
                  dy=fabs((*sItD)-(*pIt).y);
                  dx=fabs(x-(*pIt).x);
                  double len=hypot(dx,dy);
                  if(len<ans)ans=len;
                  if(dx>ans){
                        Dells.insert((*pIt));
                  }
                  if(sItU!=(*it).second.end()){
                        dy2=fabs((*sItU)-(*pIt).y);
                        if(dy2<dy){
                              sItD++;
                              sItU++;
                        }else{
                              pIt++;
                        }
                  }else{
                        pIt++;
                  }
            }
            for(pIt=Dells.begin();pIt!=Dells.end();pIt++){
                  Left.erase((*pIt));
            }
            for(sItD=(*it).second.begin();sItD!=(*it).second.end();sItD++){
                  p.x=x;
                  p.y=(*sItD);
                  Left.insert(p);
            }
            Ps.erase(x);
            it=Ps.begin();
      }
      printf("%0.7lf\n",ans);
}

古物発掘 マリオカートＤＳ

昔懐かしのゲームを今日また発掘して遊ぶ。

子供にとって携帯ゲームを遊ぶとき一番悲しいことは電池切れだろう
友達と集まってる時一人電池切れだと悲しいものがあると思う。

だからかわからないがマリオカートは電池の持ちがいい。

色々なところで省エネテクニックが使われているような気はする。

例えば立体物はかなり板で置き換えられている。

ユーザの操作するカートのほうを向く板。。
ユーザの操作するカートのほうを向く周期的な表示を繰り返す板
固定された単なる板。
固定された周期的な表示を繰り返す板
ユーザーの操作するカートのほうを向く動く板。
の5種類で上手にマップ内の立体物が平面物で置き換えられている。

例えば
マリオサーキットの火を吐くぱっくんフラワーの幹は板に書かれた絵で。
頭部だけが立体物になっている。
幹も安易に３Ｄモデルにしそうなところこういう細かいところで電池を節約してんだろうなと感心したり。

キラーシップの小型キラー砲台はカートのほうを向く板であって立体物ではない。

ワルイージピンボールの巨大ボールは単なるカートのほうを向く動く板だ。

板の向こうがすけない技術は私にはマジックに見える。
当たり判定や視界判定の処理はちょっとどうなってるか想像がつかない。

誰もが気付くことだけど立体物のポリゴン数はどこをみても最小だ。
巨大キラーは誰が見ても６角柱に６角錐をつけたものだしトンネルはカクカクしている。
コーナーもカクカクしているのにそのカクカクがなぜか視界的に気持ち良いという不思議さ。

遠くの立体物はよく見ると単なる絵だったりする。

一時代を築いたゲームはやっぱり。
電池切れのような子供がどこを喜ぶかを大事にしてるのだろうと思う。

AOJ Range Query - Range Sum Query

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B
会津大学オンラインジャッジ問ＤＳＬ２Ｂ
データの変更と集計クエリに高速に答える問題。

もちろん、クエリごとに線形で集計していたら答えは出ない。
セグメント木で分割して集計したものをさらに集計するというひと手間が必要。

実は細部は直感で書いてるので理論面ではちょっと曖昧な部分があります。
色々なテストデータを用意して全部うまくいったからこれでいけるだろという感じで合格しました。


#include<stdio.h>
#include<map>
#include<algorithm>

const int LIMIT=262144;
const int FIRST=LIMIT/2;
int A[LIMIT];

void set(int p){
      if(p==0)return ;
      A[p]=0;
      set(p/2);
}


void dellAndSet(int p){
      if(p==0)return ;
      int a=0,b=0;
      if(p*2<LIMIT){
            a=A[p*2];
      }
      if(p*2+1<LIMIT){
            b=A[p*2+1];
      }
      A[p]=a+b;
      dellAndSet(p/2);
}

int sum(int x,int y,int p,int L,int R){
      if(x>y)return 0;
      int M=(L+R)/2;
      if(L==x){
            M=R;
            while(y<M){
                  p*=2;
                  M = (L+M)/2;
            }
            int a=A[p];
            int b;
            b=sum(M+1,y,1,0,FIRST-1);
            //printf("(%d %d %d)<%d %d %d %d %d>",a,b,p,L,M,R,x,y);
            return a+b;
      }
           
     
      if(M<x){
            return sum(x,y,p*2+1,M+1,R);
      }else if(x<=M){
            return sum(x,y,p*2,L,M);
      }

      return -10000;//おかしな処理の検出
}
int main(){
      int n,q,com,x,y;
      scanf("%d %d",&n,&q);
      for(int i=0;i<FIRST;i++){
            set(FIRST+i);
      }
     
      for(int i=0;i<q;i++){
            scanf("%d %d %d",&com,&x,&y);
            if(com==0){
                  A[x+FIRST]+=y;
                  dellAndSet((x+FIRST)/2);
            }else{
                  printf("%d\n",sum(x,y,1,0,FIRST-1));
            }
      }
}

Range Query - Range Minimum Query

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
データを更新しながらクエリに答える問題。


セグメント木で更新検索するだけです。
木の根元へ更新するとき、子のより小さい値を選びながら上へ更新していきます。
実行速度は一位タイですが皆僅差なので大差ありません。
set関数がかなり無駄というのは書き終えた後に気付きました。

#include<stdio.h>
#include<map>
#include<algorithm>

const int LIMIT=262144;
const int S=2147483647;
const int FIRST=LIMIT/2;
int A[LIMIT];

void set(int p){
      if(p==0)return ;
      A[p]=S;
      set(p/2);
}


void dellAndSet(int y,int p){
      if(p==0)return ;
      int a=S,b=S;
      if(p*2<LIMIT){
            a=A[p*2];
      }
      if(p*2+1<LIMIT){
            b=A[p*2+1];
      }
      int nowMin=std::min(std::min(y,a),b);
      A[p]=nowMin;
      dellAndSet(nowMin,p/2);
}

int search(int x,int y,int p,int L,int R){
     
      if( R<x|| y<L)return S;
      if(x<=L&&R<=y){
            return A[p];
      }else{
            int a=search(x,y,p*2  ,L,  (L+R)/2);
            int b=search(x,y,p*2+1,(L+R)/2+1,R);
            return a<b?a:b;
      }
}
int main(){
      int n,q,com,x,y;
      scanf("%d %d",&n,&q);
      for(int i=0;i<FIRST;i++){
            set(FIRST+i);
      }
     
      for(int i=0;i<q;i++){
            scanf("%d %d %d",&com,&x,&y);
            if(com==0){
                  dellAndSet(y,x+FIRST);
            }else{
                  printf("%d\n",search(x,y,1,0,FIRST-1));
            }
      }
}

Elementary data structures - Areas on the Cross-Section Diagram

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_D

地形データから水たまりの面積を算出する。
単なるパズルに見せかけて　数学理論を裏側に控えているだろう問題。


右か左で高さが決まるから左右から攻めていくだけです。
￥で水たまりに入る。
/で外に出る
右きから左へ見るときは￥と/を反転してから見る。


#include<stdio.h>
#include<vector>
#include<string.h>

const int LIMIT=20001;
const int out=-1;
const int in=1;
char str[LIMIT];
int inOut[LIMIT]={0};


void setInOut(int sp,int dx){
      int len =strlen(str);
      char c;
      bool isIn=false;
      int outHight,nowHight=0,sum,inP;
     
      std::vector<int> anss;

      for(int i=sp;i>=0&&i<len;i+=dx){
            c=str[i];
            //printf("(%c %d)",c,nowHight);
            if(isIn==true){
                  if(c=='\\'){
                        sum+=outHight-nowHight+1;
                        nowHight--;
                  }else if(c=='/'){
                        nowHight++;
                        sum+=outHight-nowHight;
                  }else if(c=='_'){
                        sum+=outHight-nowHight;
                  }
                  if(nowHight==outHight){
                        //printf("%d ",sum);
                        if(dx==1){
                              inOut[inP]=std::max(sum,inOut[inP]);
                        }else{
                              inOut[i]=std::max(sum,inOut[i]);
                        }
                        isIn=false;
                  }
            }else{
                  if(c=='\\'){
                        //printf("\n<in>");
                        inP=i;
                        isIn=true;
                        sum=1;
                        outHight=nowHight;
                        nowHight--;
                  }else if(c=='/'){
                        nowHight++;
                  }
            }
      }
}
void changeSTR(int len){
      for(int i=0;i<len;i++){
            if(str[i]=='\\')str[i]='/';
            else if(str[i]=='/')str[i]='\\';
      }
}

int main(){
      scanf("%s",str);
      int len=strlen(str);
      setInOut(0,1);
      changeSTR(len);
      //printf("\n\n");
      setInOut(len-1,-1);
      std::vector<int> anss;
      int all=0;
      for(int i=0;i<len;i++){
            if(inOut[i]>0)anss.push_back(inOut[i]);
            all+=inOut[i];
      }
      printf("%d\n%d",all,anss.size());
      for(int i=0;i<anss.size();i++){
            printf(" %d",anss[i]);
      }
      printf("\n");
}

会津大学オンラインジャッジ 問 Tree - Diameter of a Tree

Tree - Diameter of a Tree

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_A
グラフ理論における木の直径をこたえる問題。


解法
一点を根元と定めて木を探索します。
深さ優先探索で木を旅する旅人を考えます。
枝先まで旅をします。
枝先にぶち当たったら戻りますが戻るとき距離を数えて、枝先からここまでの距離を分岐ごとに点に記録しておきます。
この分岐の先で一番遠かった枝先までの距離は何々だとします。

ある点の枝先を全部調べ終えたら帰るとき、枝先で一番距離が遠かったものをその道の最も長い距離だと根元側の点に記録します。
これを繰り返してスタート地点まで戻ってくれば答えです。

途中の点で二つの枝先の距離合計が最も遠くなる点を計算する場合を忘れないようにします。

私のコードは試行錯誤の後が残ってるので少し無駄な処理が入っていますが答えには影響しません。
一応コード実行速度で一位に並びました。
こういう綺麗な問題は解いてて楽しいですが、順位差をつけにくいのが欠点ですね。



#include<stdio.h>
#include<vector>
#include<map>
#include<stack>
struct E{
      int t,w,old;
      bool first;
};
const int LIMIT=100001;
std::vector<E> G[LIMIT];
int ans=0;

int sumMax[LIMIT]={0},sumSecond[LIMIT]={0},nowMax[LIMIT]={0};
void setSumMax(int p,int w){
      if(sumMax[p]<=w){
            sumSecond[p]=sumMax[p];
            sumMax[p]=w;
      }else if(sumSecond[p]<=w){
            sumSecond[p]=w;
      }
}


void calc(){
      std::stack<E> sta;
   
      E e1,e2;
      e1.t=0;
      e1.old=-1;
      e1.w=0;
      e1.first=true;
      sta.push(e1);
      int ans=0,c=0;
      while(sta.empty()==false){
            e1=sta.top();
            sta.pop();
            int p=e1.t;
            if(e1.first==true){
                  e1.first=false;
                  sta.push(e1);
            }else{
                  int resultMax=sumMax[p]+e1.w;
                  setSumMax(p,nowMax[p]);
                  ans=std::max(ans,sumMax[p]+sumSecond[p]);
                  setSumMax(e1.old,resultMax);
                  continue;
            }
         
            std::vector<E>::iterator vIt,vItEnd;
            vItEnd=G[p].end();
            for(vIt=G[p].begin();vIt!=vItEnd;vIt++){
                  e2=(*vIt);
                  e2.first=true;
                  if(e2.t==e1.old)continue;
                  sta.push(e2);
                  nowMax[e2.t]=nowMax[e1.t]+e2.w;
            }
      }
      printf("%d\n",ans);
}

int main(){
      int n,s,t,w;
      E e1,e2;
      scanf("%d",&n);
   
      for(int i=1;i<n;i++){
            scanf("%d %d %d",&s,&t,&e1.w);
            e1.t=t;
            e1.old=s;
            G[s].push_back(e1);
            e1.t=s;
            e1.old=t;
            G[t].push_back(e1);
      }
      calc();
}

会津大学オンラインジャッジ 問140 Bus Line

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0140

昔書いたコードがあるのだがあまりにデータ構造に頼ったあれなコードだったので
もう少しましなコードに直してみた。
このコードならバスラインを表現するdataの形が変わってもきちんと動く。
それにしてももっと短い人たちはどんな風にコードを書いてるのかな。



#include<stdio.h>
#include<vector>
void search(int s,int e){
      int data[]={9,8,7,6,5 ,4,3,2,1,0, 1,2,3,4,5 ,9,8,7,6};
      std::vector<int> sp,ep;
      for(int i=0;i<19;i++){
            if(s==data[i]){
                  sp.push_back(i);
            }
            if(e==data[i]){
                  ep.push_back(i);
            }
      }
      int p1,p2,len=100,d;
      for(int i=0;i<sp.size();i++){
            for(int j=0;j<ep.size();j++){
                  d=sp[i]-ep[j];
                  if(d>0&&d<len){
                        p1=sp[i];
                        p2=ep[j];
                        len=d;
                  }
            }
      }
      for(int i=p1;i>p2;i--){
            printf("%d ",data[i]);
      }
      printf("%d\n",data[p2]);
}

int main(){
      int n,s,e;
      scanf("%d",&n);
      while(n--){
            scanf("%d %d",&s,&e);
            search(s,e);
      }
}

日常への愚痴

このブログでの個人的な記述は全部ここに集積。

スーパーの店内を回遊魚のように周遊して何か食べ物を買ったり。
日本中にあふれかえってる本が吹きだまってできたような、うらびれた小さな町の本屋を訪れたり。
地域の健康屋さんを自認する小さな薬局で売れてない健康飲料を買ったり。
デパートで土讃もの市を見たり。
アマゾンで手に入りにくい希少本を買ったり。

こういうことをしても私は単なる消費者という記号であって、こういうことは人生ではないな。
人生を生きている気がしない。


ネットでは。
フランス政府のセクト（カルト）教団対策がいかに間違ってるか宗教団体の人が主張している。
彼らの主張が事実に立脚するならいいのだが、フランス政府が行ってないことに基づいた妄想も大量に含まれている。
私はそれではフランス政府の活動がどのようなものか公平に議論できるよう中立的な観点から資料を提供しましょう。
といってＷｉｋｉソースにＭｉｖｉｌｕｄｅｓの年次報告書（セクト対策の有識者会議）の日本語訳を掲載した。

が宗教団体の人海戦術の前には大海の一滴。
翻訳代もないのでごく一部しか翻訳できてない。
などいろいろ困っている。



さて宗教団体側の妄想でひとつ例を挙げてみる。
例えば創価学会は、創価学会はフランス政府からカルト指定を受けたが、フランス政府は自分たちのカルト指定がずさんだったことを認めその指定を解除したと主張してます。

どこが妄想なのかというと、フランス政府はカルト指定など行ってない点。

フランス政府が行ったのは行政の実務上、悪質な活動が確認された団体を色々資料にまとめてセクト対策に生かしているのですが。

この記載をセクト指定だと創価学会員が勘違いしているわけです。

単なる実務上の記載であり、指定でもなんでもありません。
指定ではないからその解除も存在するはずがなく、ただ単に悪質な活動があったから、その悪質な範囲に対し行政として対処しているだけというのがフランス政府のカルト対策の実態です。

フランスでも一つだけカルト指定と言えるものがあります。
２００１年に制定された反セクト法というものがあり

この法律は活動内容が悪質で組織犯罪が多発しそれが改まりそうにない団体に対し、裁判を通じてその団体のフランス国内での５年間の活動禁止を裁判で争えるようにする法律です。

この法律の適用が唯一のカルト指定なのですが、
よほど悪質でよほど犯罪体質でない限り適用されません。

創価学会のカルト指定が解除されたという主張を認めるなら、この法律が適用されるほど自分たちは悪辣だったと主張していることになるのですが、彼らはこれに気付いてないようです。

会津大学オンラインジャッジ 問139 Snakes

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0139
Ｃ++には標準では正規表現がないので、今回はＪａｖａで記述。
Ｊａｖａは全く分かってないので他人のソースをそのままマルコピ。
正規表現の勉強になった。


import java.util.*;
import java.util.regex.*;

class Main{

public static Pattern
a= Pattern.compile(">\'(=+)#\\1~"),
b= Pattern.compile(">\\^(Q=)+~~");
static final Scanner stdin=new Scanner(System.in);
//javaの手習い　手習いなので今回は他人のをマルコピー
//マッチ結果のグループ化や後方参照という概念などかなり正規表現の勉強になった
public static void main(String[] args){
int n=stdin.nextInt();
for(int i=0;i<n;i++){
solve(stdin.next());
}
}
public static void solve(String str){
if(a.matcher(str).matches() ){
System.out.println("A");
}else if(b.matcher(str).matches()){
System.out.println("B");
}else{
System.out.println("NA");
}
}
}

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B

ＧＲＬ＿３＿Ａのコードを９割流用して１０分で解けた。
前の問題の解放を我流であみだすのに３日かかったことを考えるとあっという間であった。

お祈りは済ませたか？
コードのチェックは。
部屋の隅で胸をドキドキさせながらジャッジデータを通ることを祈る心の準備は？

ＯＫだ。
というわけで一発で通りました。
問題的には3Ａとほとんど同じでした。




#include<stdio.h>
#include<queue>
#include<map>
#include<vector>
#include<string.h>
#include<algorithm>
#include<set>
#include<stack>

struct E{
      int t,len,old,no;
      bool alive;
      bool operator<(const E& e1)const{
            return len>e1.len;
      }
};

const int LIMIT=10*10000+1;
std::vector<E> G[LIMIT];
int lens[LIMIT];
int roots[LIMIT];

bool alivePoints[LIMIT];
int  loopCounts[LIMIT];
int size;


void D(){
      E e1,e2;
      int v,e,s,t;
      scanf("%d %d",&v,&e);
     
      for(int i=0;i<e;i++){
            scanf("%d %d",&s,&t);
            e1.alive=false;
            e1.len=0;
            e1.t=t;
            G[s].push_back(e1);
            e1.t=s;
            G[t].push_back(e1);
      }
      memset(lens,-1,sizeof(lens));
      e1.old=-1;
      e1.t=0;
      e1.len=0;
      e1.no=0;
      std::priority_queue<E> pq;
      pq.push(e1);
      std::vector<E>::iterator vIt,vItEnd;
      size=v;
      while(pq.empty()==false){
            e1=pq.top();
            pq.pop();
            if(lens[e1.t]!=-1&&lens[e1.t]<=e1.len){    
                  continue;
            }
            lens[e1.t]=e1.len;
           
            if(e1.old!=-1){
                  //printf("(a t=%d old=%d no=%d)\n",e1.t,e1.old,e1.no);
                  G[e1.old][e1.no].alive=true;
                  roots[e1.t]=e1.old;
            }
           
            e1.len++;
            vItEnd=G[e1.t].end();
            int i=0;
            for(vIt=G[e1.t].begin();vIt!=vItEnd;vIt++){
                  e2=(*vIt);
                  e2.len=e1.len;
                  e2.old=e1.t;
                  e2.no=i;
                  i++;
                  if(e2.t==e1.old){
                        //printf("(b old=%d t=%d no=%d)\n",e2.old, e2.t, e2.no);
                        G[e2.old][e2.no].alive=true;
                  }else{
                        pq.push(e2);
                  }
            }
      }
      //std::set<int>::iterator sIt;
      //for(int i=0;i<v;i++){
      //      printf("\n%d\n",i);
      //      for(sIt=pareMemo[i].begin();sIt!=pareMemo[i].end();sIt++){
      //            printf("<%d> ",(*sIt));
      //      }
      //}
}


std::map<int,int> memo;
int countNos[LIMIT];
int nowLoopAdds[LIMIT];
int dells[LIMIT];
bool cutOKs[LIMIT];
std::set<std::pair<int,int> > ans;


void search(){
      memset(alivePoints,true,sizeof(alivePoints));
      memset(loopCounts,0,sizeof(loopCounts));
      memset(nowLoopAdds,0,sizeof(nowLoopAdds));
      memset(dells,0,sizeof(dells));

      std::stack<std::pair<int,int> > sta;
      std::pair<int,int> pp,pp2,pp3;
      alivePoints[0]=false;
      pp.first=0;
      pp.second=0;
      sta.push(pp);
      std::vector<E>::iterator vIt,vItEnd;
      E e1;
      int countNo=0;
      while(sta.empty()==false){
            countNo++;
            pp=sta.top();
            sta.pop();
           
            int s=pp.first;
            int i=pp.second;
            //printf("%d ",s);
            alivePoints[s]=false;
            if(i==G[s].size()){
                  int t=countNos[s];
                  memo.erase(t);
                  if(s!=0){
                        loopCounts[roots[s]]+=loopCounts[s]+nowLoopAdds[s]-dells[s];
                        if((loopCounts[s]==dells[s])&&((nowLoopAdds[s]+loopCounts[s]==0)||(dells[s]>0))){
                              if(cutOKs[s]==true){
                                    pp3.first=std::min(s,roots[s]);
                                    pp3.second=std::max(s,roots[s]);
                                    ans.insert(pp3);
                              }
                        }
                  }
                 
                  //printf("\n<d=%d>\n",t);
                  //std::map<int,int>::iterator sIt;
                  //for(sIt=memo.begin();sIt!=memo.end();sIt++){
                  //      printf("<%d %d>",(*sIt).first,(*sIt).second);
                  //}
                  //printf("\n");
            }else{
                  if(i==0){
                        memo[countNo]=s;
                        cutOKs[s]=true;
                  }else{
                        int t=countNos[s];
                        memo.erase(t);
                        memo[countNo]=s;
                  }
                  countNos[s]=countNo;
                 
                  e1=G[s][pp.second];
                  pp.second++;
                  sta.push(pp);
                  if(roots[s]!=e1.t && lens[e1.t]<=lens[s]){
                        cutOKs[s]=false;
                  }
                 
                  if(e1.alive==false&&alivePoints[e1.t]==true){
                        nowLoopAdds[s]++;
                  }
                 
                  if(alivePoints[e1.t]==false&&e1.alive==false){
                        int dellP=(*(memo.upper_bound(countNos[e1.t]))).second;
                        nowLoopAdds[s]++;
                        //printf("\n<dell=%d t=%d s=%d>\n",dellP,e1.t,s);
                        dells[dellP]+=2;
                        continue;    
                  }
                  if(alivePoints[e1.t]==false){
                        continue;
                  }
                  if(e1.alive==true){
                        pp2.first=e1.t;
                        pp2.second=0;
                        sta.push(pp2);
                  }
            }
      }
      std::set<std::pair<int,int> >::iterator it;
      for(it=ans.begin();it!=ans.end();it++){
            printf("%d %d\n",(*it).first,(*it).second);
      }
}

int main(){
      D();
      search();
}

会津大学オンラインジャッジ ＧＲＬ＿３＿Ａ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A

Ｃonnected Components - Articulation Points
完全に自己流の解放で解決。

問題ページのヒントへのリンクに解法が載っているがそれはガン無視。
まずは全くの0から自分で考えた解法で解いてみた。
中学生レベルの教育も満足に受けてないしグラフ理論なんてわかんねというのでとにかく時間かかった。

コードの方針を決めるのに２時間。
一睡しながら夢の中で考え直し、そのあとは試行錯誤しながらコード実装をガリガリ６時間。
実質３日かかった。

コード実行時間0.03セコンド、正答者の中では実行速度最下位である。
残念。

そのうちヒントのほうの解法を実装しようと思う。


#include<stdio.h>
#include<queue>
#include<map>
#include<vector>
#include<string.h>
#include<algorithm>
#include<set>
#include<stack>


struct E{
    int t,len,old,no;
    bool alive;
    bool operator<(const E& e1)const{
        return len>e1.len;
    }
};

const int LIMIT=10*10000+1;
std::vector<E> G[LIMIT];
int lens[LIMIT];
int roots[LIMIT];

bool alivePoints[LIMIT];
int  loopCounts[LIMIT];
int size;


void D(){
    E e1,e2;
    int v,e,s,t;
    scanf("%d %d",&v,&e);
   
    for(int i=0;i<e;i++){
        scanf("%d %d",&s,&t);
        e1.alive=false;
        e1.len=0;
        e1.t=t;
        G[s].push_back(e1);
        e1.t=s;
        G[t].push_back(e1);
    }
    memset(lens,-1,sizeof(lens));
    e1.old=-1;
    e1.t=0;
    e1.len=0;
    e1.no=0;
    std::priority_queue<E> pq;
    pq.push(e1);
    std::vector<E>::iterator vIt,vItEnd;
    size=v;
    while(pq.empty()==false){
        e1=pq.top();
        pq.pop();
        if(lens[e1.t]!=-1&&lens[e1.t]<=e1.len){
            continue;
        }
        lens[e1.t]=e1.len;
       
        if(e1.old!=-1){
            //printf("(a t=%d old=%d no=%d)\n",e1.t,e1.old,e1.no);
            G[e1.old][e1.no].alive=true;
            roots[e1.t]=e1.old;
        }
       
        e1.len++;
        vItEnd=G[e1.t].end();
        int i=0;
        for(vIt=G[e1.t].begin();vIt!=vItEnd;vIt++){
            e2=(*vIt);
            e2.len=e1.len;
            e2.old=e1.t;
            e2.no=i;
            i++;
            if(e2.t==e1.old){
                //printf("(b old=%d t=%d no=%d)\n",e2.old, e2.t, e2.no);
                G[e2.old][e2.no].alive=true;
            }else{
                pq.push(e2);
            }
        }
    }
    //std::set<int>::iterator sIt;
    //for(int i=0;i<v;i++){
    //  printf("\n%d\n",i);
    //  for(sIt=pareMemo[i].begin();sIt!=pareMemo[i].end();sIt++){
    //      printf("<%d> ",(*sIt));
    //  }
    //}
}


std::map<int,int> memo;
int countNos[LIMIT];
int nowLoopAdds[LIMIT];
int dells[LIMIT];
bool ans[LIMIT];

bool lastPoint0Check(){
    //この関数はとても恥ずかしい
    if(size<3)return false;
    if(G[0].size()==1)return false;
    std::queue<int> qu;
    qu.push(1);
    memset(alivePoints,true,sizeof(alivePoints));
    alivePoints[0]=alivePoints[1]=false;
    std::vector<E>::iterator vIt,vItEnd;
    E e1;
    while(qu.empty()==false){
        int p=qu.front();
        qu.pop();
        vItEnd=G[p].end();
        for(vIt=G[p].begin();vIt!=vItEnd;vIt++){
            int p1=(*vIt).t;
            if(alivePoints[p1]==false)continue;
            alivePoints[p1]=false;
            qu.push(p1);
        }
    }
    for(int i=0;i<size;i++){
        if(alivePoints[i]==true)return true;
    }
    return false;
}

void search(){
    memset(alivePoints,true,sizeof(alivePoints));
    memset(loopCounts,0,sizeof(loopCounts));
    memset(ans,false,sizeof(ans));
    memset(nowLoopAdds,0,sizeof(nowLoopAdds));
    memset(dells,0,sizeof(dells));

    std::stack<std::pair<int,int> > sta;
    std::pair<int,int> pp,pp2;
    alivePoints[0]=false;
    pp.first=0;
    pp.second=0;
    sta.push(pp);
    std::vector<E>::iterator vIt,vItEnd;
    E e1;
    int countNo=0;
    while(sta.empty()==false){
        countNo++;
        pp=sta.top();
        sta.pop();
       
        int s=pp.first;
        int i=pp.second;
        //printf("%d ",s);
        alivePoints[s]=false;
        if(i==G[s].size()){
            int t=countNos[s];
            memo.erase(t);
            if(s!=0){
                loopCounts[roots[s]]+=loopCounts[s]+nowLoopAdds[s]-dells[s];
                if((loopCounts[s]==dells[s])&&((nowLoopAdds[s]+loopCounts[s]==0)||(dells[s]>0))){
                    ans[s]=true;
                    if(nowLoopAdds[s]==0){
                        ans[roots[s]]=true;
                    }
                }
            }
           
            //printf("\n<d=%d>\n",t);
            //std::map<int,int>::iterator sIt;
            //for(sIt=memo.begin();sIt!=memo.end();sIt++){
            //  printf("<%d %d>",(*sIt).first,(*sIt).second);
            //}
            //printf("\n");
        }else{
            if(i==0){
                memo[countNo]=s;
            }else{
                int t=countNos[s];
                memo.erase(t);
                memo[countNo]=s;
            }
            countNos[s]=countNo;
            //printf("(%d %d)",s,countNo);
           
            e1=G[s][pp.second];
            pp.second++;
            sta.push(pp);
            if(e1.alive==false&&alivePoints[e1.t]==true){
                nowLoopAdds[s]++;
            }
           
            if(alivePoints[e1.t]==false&&e1.alive==false){
                int dellP=(*(memo.upper_bound(countNos[e1.t]))).second;
                nowLoopAdds[s]++;
                //printf("\n<dell=%d t=%d s=%d>\n",dellP,e1.t,s);
                dells[dellP]+=2;
                continue;
            }
            if(alivePoints[e1.t]==false){
                continue;
            }
            if(e1.alive==true){
                pp2.first=e1.t;
                pp2.second=0;
                sta.push(pp2);
            }
        }
    }
   
    ans[0]=lastPoint0Check();
    for(int i=0;i<size;i++){
        if(ans[i]==true&&G[i].size()>1){
            printf("%d\n",i);
        }
        //printf("(i=%d count=%d dell=%d %d)\n",i,loopCounts[i],dells[i],roots[i]);
    }
}

int main(){
    D();
    search();
}

会津大学オンラインジャッジ 問ＡＬＤＳ1＿1Ｄ

Getting Started - Maximum Profit

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_D

儲かることしか考えない人間心理の盲点を突いた問題です。
r日目以降に売ることを考えた場合、r日目以降の最大値とr-1日目までの最小値を角突き合わせればよいだけです。
というわけでr日目までの最小値をminsに保存してあとは逆向きにr+1日目以降の最大値と差額を計算します。
儲からない場合があるのがこの問題の盲点です。


#include<stdio.h>
#include<algorithm>

const int LIMIT=200001;
int Rs[LIMIT],mins[LIMIT];

int main(){
int n,ans,vMin;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&Rs[i]);
if(i==0){
vMin=Rs[0];
}else{
vMin=std::min(Rs[i],vMin);
}
mins[i]=vMin;
}
int vMax=Rs[n-1];
ans=Rs[n-1]-mins[n-2];
for(int i=n-2;i>=0;i--){
ans=std::max(ans,vMax-mins[i]);
vMax=std::max(Rs[i],vMax);
}
printf("%d\n",ans);
}

会津大学オンラインジャッジ 問8

Sum of 4 Integers

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008
ｎが与えられるのでa+b+c+dで何通りの方法でｎが作れるか答える問題。
0<=a,b,c,d<=9


解法
Ｊａｖａといふものを一つ初めて見よふと思ひておもむろにエクリープスなるものをダウソロードし右も左もわからぬまま気の赴くままにＡＯＪの問題などをといてみゆ。

計算量は19*19+10*10となかりしけるが、Ｊａｖａ言語事体の重さの前には全く意味がないといふことに気付く。


C++で書き直してみたら計算量27*4回になった。
ちなみにこの問題数式で書き表してもよいが数式を具体的に計算する計算量はもう少し小さくなるはず。
多分。


import java.util.Scanner;

class Main{
static final Scanner stdin=new Scanner(System.in);
//javaの手習い

public static void main(String[] args){
int[] memo=new int[37];
int[] memo2=new int[37];
for(int i=0;i<37;i++){
memo[i]=0;
memo2[i]=0;
}
for(int a=0;a<10;a++)
for(int b=0;b<10;b++)
memo[a+b]++;
for(int u1=0;u1<=18;u1++){
for(int u2=0;u2<=18;u2++){
memo2[u1+u2]+=memo[u1]*memo[u2];
}
}

while(stdin.hasNext()){
int n=stdin.nextInt();
if(n<0||n>36){
System.out.println(0);
}else{
System.out.println(memo2[n]);
}
}
}
}



ｃ++版

#include<stdio.h>

int main(){
int dp[37]={1,0},n,a;
for(int i=0;i<4;i++){
int sum=0,p=0,old=0;
for(int s=18;s>=-8;s--){
if(s>=9){
sum+=dp[s];
}else{
sum=sum-old+(s>=0?dp[s]:0);
}
old= s>9?0:dp[s+9];
dp[s+9]=sum;
p=(p+1)%10;
}
}
while(scanf("%d",&n)!=EOF){
if(n>36||n<0)a=0;
else a=dp[n>18?36-n:n];
printf("%d\n",a);
}
}