会津大学のサイトにはプログラマ向け練習問題が掲載されており、高校生から大学２年生くらいまで向け問題が掲載されています。
私はsinapusu2002という名前で登録。
２０１１/７/２時点で333問解きました。
さすがにこれだけ解くと残り問題は苦手問題か難問ばかり。
とりあえず私でも解けそうな問題がないか、残っている問題の挑戦状態を記録することにしました。
一般のプログラマには簡単な問題だと思いますが、３流高卒独学の私には難しい問題ばかり。
全く手も足も出ていません。
2200番台
2200番台は緻密な計算量が求められる問題ばかり。
計算量を気にしなければ解ける問題も多いがそれだとコードが遅いと不正解になってしまう。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2200
郵便局員の集配問題。
船さえなければ単なるワーシャルフロイド法なのだが、船の存在が問題の難易度を引き上げている。
解法思いつかず。
最低限確実に言えることは、船を利用する場合、スタート地点から船まで最短経路を取る、船は一度の移動で２度以上使わない、船から降りたら目的地まで最短経路しか使わない。
ということですね。
問題点は目標点ＡからＢ、ＢからＣへ向かう時、Ａ～Ｂを最短で結ぶ経路を取りそこに海路が含まれる時、船の係留所はＡ～Ｂの最短コースの途中でいいのか？
それとも、Ｃを考慮に入れた少し遠回りなＡ～Ｂへのルートを選び、船の運用をＣへ行く時のことも考えた場所に止めるべきか？
という問題が生まれる。
この問題は最短経路を通っていいなら簡単な問題になるけれど？
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2202
運河のシミュレート問題。
丁寧にシミュレートしていけばいいのだろうが、シミュレートの方式が精密に組み上がっているか自信が持てず挑戦できない。
多分、船が前の船に追いつく、船が運河の水門で足止めを喰らう、等のイベントをsetに入れて、イベントが起こるたびに無効化されるイベント消す？
それともターン制で処理する？
あるタイムから次のイベントが起こるタイムを求め一番すぐにおこるイベントを求め、その時刻までターンを進め船の状態を動かしていく？
一つ確実なことがある。
ある地点にいる船は、その前にいる船の状態にしか影響を受けない。
だから処理は必ず、前にいる船から後ろにいる船へとなされていく連鎖で考えるとよい？
正答率は下げたくないなあ。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2207
解決済み
単位系の関係が与えられるので、与えられたデータに矛盾がないか調べる問題。
この問題はグラフで解けばいい。
でてきた単位系をエッジとして保存、単位系を連想配列に入れて番号をつけこの番号を基準にグラフを作る。
ある点から初めて、単位変換をしながらグラフの探索をする。
移動した先の点を一度も訪れてないなら、その点に今の単位変換の数を書きこむ。
一度でも訪れているなら、今の単位変換の数と、訪れた点に記録してある単位変換の数が同じか調べる。
同じならそこはＯＫなので１点戻って次の探索。
同じでないならエラーデータとして×を出す。
ここで気になるのは計算量の低減。
一つの点を出発点に無矛盾なら全点が無矛盾とみなしてよいのか。
それとも全部の点から出発しないと見落としが出るのか？
そこが難しいところ。
多分一点から出発して全点無矛盾ならどの点から始めても無矛盾という結果になると思うのだけど？
グラフがつながってない場合と考えると意外と落とし穴があるのかもしれない？
解決コード。
ある単位から別の単位に変換する過程で無矛盾なら、その途中にある単位も無矛盾である。
という発想で問題を解いてみたところ高速に問題が解けた。
コードをもう少しブラッシュアップすれば1位の人と処理速度を競えるレベルで解けた。
2207ConsistetUnitSystem1.cpp
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2208
表の中に○の書かれている数が行と列ごとに与えられる。
行列の条件を満たしながら表を埋める時、表は一通りの埋め方ができるか答えよ。
単なる全探索で一つで収まるか、２つ以上になるかを求めればいいのだろうか？
しかしＮ＝10000という数字は全探索を拒否しているような気がする。
すると何か賢い計算のような方法が必要になるのか、それともあるマスと他のマスを交換するような場合があるかないかを調べるのか？
トンチ一つの可能性もあるがかなり難しそう。
何か、一通りに定まる場合の条件のようなものが見つかればいいのだけど？
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2209
うーん？
文字コードUTF-8データとして解釈できるデータの解釈問題。
これは、２進数を読み込んだ時ｎバイトの文字として評価できるか？
ということだよな。しかもそのバイト数読んだ時で何通りのパタンで読めるかということ？
バイト数が1000バイトというのが難問。
組み合わせ量が凄いことになる。
4バイトですら、(4)、(1,3),(3,1),(2,2),(2,1,1,),(1,2,1),(1,1,2),(1,1,1,1)の解釈で分岐してしまう。
別の考え方をしてもｍバイト目まで読んだ後次を、４バイトで読む、３バイトで読む、２バイトで読む、１バイトで読む。
という恐ろしい組み合わせ量になる？
するとメモ化探索の出番か？
最初memo[1001]を用意する。
最初スタートの１バイト目から4,3,2,1バイトで読むことを試し、そのバイト数ｍで読めたら、そのバイト数で何通りの解釈ができるかを計算し、メモ化のｍ番目に保存する。
4バイトと２バイトで読めることが判明したら、2バイト目を先に計算する、３バイト目から6バイト目までを何バイトで読めるかを求めbとする。
もし次が2バイトで読めるとしたらmemo[4]にmemo[2]*bを足しこむ。
次にmemo[4]に保存されている数値でも同様の計算を行う。
こうすれば計算量を抑えつつ問題を細切れにして解ける。
問題は何バイトで読めるかの判断関数と、そのバイト数で読んだ時何パターンで読めるかを求める関数の作成。
これがなんだか難しそう？
テストデータほしいなあ。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2211
うーん？
猫のえさやり問題。
Ｙ座標は多分単なるこけおどし。
餌場Ａ0、Ａ2が2分している時にその間にある餌場Ａ1に餌を置くと、Ａ0、Ａ２両方の猫がＡ1に集まり猫の数がＡ1で増えてしまう可能性がある。
これを奇麗に避けて餌を置く場所を決めないといけないわけで？
何も考えず全探索すると２^1000、全探索は駄目となるとうーん難しそう。
仮説。
最初全ての餌場に餌を入れて猫の数を数える。
一番猫が集まっている餌場から餌を取り上げて数え直す。
一番猫が集まっている餌場の数を調べて、これが改善されているなら取り上げを許可する。
駄目なら取り上げを戻って、それを答えとする。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2212
禁止された移動パタンを取らずに宝まで行きつけるか、升目の問題。
一応過去に通ったルートを保存すればいい。
一マス進むごとに、禁止パタンを犯してないか調べればいいわけだけど、単純に深さ優先探索でやると計算量が爆発するのが目に見えている？
するとメモ化探索なのかな？
うーん計算量を抑える方法を思いつかない。
幅優先探索でも大差ないよな？
同じ升目に到達しても過去に通ったルートで結果が違う。
うーん逆に考える？
あるマスにいる時、過去に通ったルートと、未来に通るルートの組で禁止パタンになる移動を全て列挙するとか？
うーん、全然思いつかないな。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2213
多項式の計算の結果をｐで割った余りが0になるｚの数を求めよという問題。
ｚの範囲が大きいので、全探索は駄目。
するとｚと答えの規則性に着目しないとだめ？
うーん？
long long intを使わないとだめな。
とりあえずホーナーの方法を使うべきか？
((a0z+a1)z+a2)z
ホーナーの方法と累乗とモード演算の間の関係だな？
何か賢い方法がありそう。
例えば？
an((z+1)^n)%p+an-1((z+1)^n-1)%p+,,,+a0(z+1)%p
と
an(z^n)%p+an-1(z^n-1)%p+,,,+a0(z+1)%p
の間の関係とか？
最終更新：2011年07月05日 16:15
