https://www.fe-siken.com/kakomon/24_aki/pm08.html

笑わずに聞いてください。


私はこの問題の【設問】a,bを解くのに２時間ほどかかりました。
結果は正解でしたが、解法が解らずに、すべてトレースました。


Ｖｉａ＝１  Ｆｒｏｍ＝１  Ｔｏ＝１  ←開始
Ｖｉａ＝１  Ｆｒｏｍ＝１  Ｔｏ＝２
Ｖｉａ＝１  Ｆｒｏｍ＝１  Ｔｏ＝３
Ｖｉａ＝１  Ｆｒｏｍ＝１  Ｔｏ＝４
Ｖｉａ＝１  Ｆｒｏｍ＝１  Ｔｏ＝５
Ｖｉａ＝１  Ｆｒｏｍ＝２  Ｔｏ＝１
Ｖｉａ＝１  Ｆｒｏｍ＝２  Ｔｏ＝２
Ｖｉａ＝１  Ｆｒｏｍ＝２  Ｔｏ＝３
Ｖｉａ＝１  Ｆｒｏｍ＝２  Ｔｏ＝４
Ｖｉａ＝１  Ｆｒｏｍ＝２  Ｔｏ＝５
Ｖｉａ＝１  Ｆｒｏｍ＝３  Ｔｏ＝１
Ｖｉａ＝１  Ｆｒｏｍ＝３  Ｔｏ＝２
Ｖｉａ＝１  Ｆｒｏｍ＝３  Ｔｏ＝３
Ｖｉａ＝１  Ｆｒｏｍ＝３  Ｔｏ＝４
Ｖｉａ＝１  Ｆｒｏｍ＝３  Ｔｏ＝５
Ｖｉａ＝１  Ｆｒｏｍ＝４  Ｔｏ＝１
Ｖｉａ＝１  Ｆｒｏｍ＝４  Ｔｏ＝２
Ｖｉａ＝１  Ｆｒｏｍ＝４  Ｔｏ＝３
Ｖｉａ＝１  Ｆｒｏｍ＝４  Ｔｏ＝４
Ｖｉａ＝１  Ｆｒｏｍ＝４  Ｔｏ＝５
Ｖｉａ＝１  Ｆｒｏｍ＝５  Ｔｏ＝１
Ｖｉａ＝１  Ｆｒｏｍ＝５  Ｔｏ＝２
Ｖｉａ＝１  Ｆｒｏｍ＝５  Ｔｏ＝３
Ｖｉａ＝１  Ｆｒｏｍ＝５  Ｔｏ＝４
Ｖｉａ＝１  Ｆｒｏｍ＝５  Ｔｏ＝５
Ｖｉａ＝２  Ｆｒｏｍ＝１  Ｔｏ＝１
Ｖｉａ＝２  Ｆｒｏｍ＝１  Ｔｏ＝２
Ｖｉａ＝２  Ｆｒｏｍ＝１  Ｔｏ＝３
Ｖｉａ＝２  Ｆｒｏｍ＝１  Ｔｏ＝４
Ｖｉａ＝２  Ｆｒｏｍ＝１  Ｔｏ＝５
Ｖｉａ＝２  Ｆｒｏｍ＝２  Ｔｏ＝１
Ｖｉａ＝２  Ｆｒｏｍ＝２  Ｔｏ＝２
Ｖｉａ＝２  Ｆｒｏｍ＝２  Ｔｏ＝３
Ｖｉａ＝２  Ｆｒｏｍ＝２  Ｔｏ＝４
Ｖｉａ＝２  Ｆｒｏｍ＝２  Ｔｏ＝５
Ｖｉａ＝２  Ｆｒｏｍ＝３  Ｔｏ＝１  ←ａを解く
Ｖｉａ＝２  Ｆｒｏｍ＝３  Ｔｏ＝２
Ｖｉａ＝２  Ｆｒｏｍ＝３  Ｔｏ＝３
Ｖｉａ＝２  Ｆｒｏｍ＝３  Ｔｏ＝４
Ｖｉａ＝２  Ｆｒｏｍ＝３  Ｔｏ＝５  ←ｂを解く


です。
途中、間違えたりで何度もやって、ある時点で法則性に気付いて…それで２時間です。
以降の設問は着手できていません。


アドバイス頂きたいのは、この問題は、そもそも論として「どうやって解くべきもの」
なのか…です。

うまく言えないのですが、一体「何に気付けば良かったのか」というか…。
あるいは、上記のようなトレースを高速で行うべきものなのか…。


この問題(とりあえず設問a,bだけについてで構いません)を解ける、解法が解る！という方のご意見を聞きたいのです。
どうぞよろしくお願い致します。

問題文をよく読んでプログラムではなく図2の表と図1の動きを追えば5分も掛からないですね。
プログラムのイメージを掴ませるための導入問題だと思います。

＞＞＞うまく言えないのですが、一体「何に気付けば良かったのか」というか…。

→「そのプログラムが再現しようとしているのはどんな"動き"か?」
をいかに早くイメージできるかがアルゴリズムの解法力かと思います。
本問の場合には、
「隣り合っていない駅同士の距離を、他の駅を経由して計った場合に最も短い距離はどれか、
片っ端から調べていく」
といった"動き"を再現しようとしていることに気づければ良かったのではと思います。
  
私は下記のような思考回路で気づきました。
================================================

【1】まず「初期値」表と「Via=1」表を見比べてみると、
  Dist[2][4]が999から32に更新されている、なぜだろう?
  ↓

【2】駅②と駅④は隣り合っていないから「初期値」表では999とされていたが、
  ①を経由すると
  ・②→①=18
  ・①→④=14
  なので18+14=32に更新されたのではないか?
  ↓

【3】この仮説を「Via=2」表のaに当てはめてみると、
  駅①と駅③は隣り合っていないから「初期値」表では999とされていたが、
  ②を経由すると
  ・①→②=18
  ・②→③=17
  なので18+17=35に更新されたのではないか?    
  ↓

【4】実際にプログラムにあてはめてトレースしてみると、
  Ｖｉａ＝２  Ｆｒｏｍ＝１  Ｔｏ＝１
  Ｖｉａ＝２  Ｆｒｏｍ＝１  Ｔｏ＝２
  Ｖｉａ＝２  Ｆｒｏｍ＝１  Ｔｏ＝３  ←確かにa=35になるのを確認
  ↓

【5】bについても【3】の考え方で計算(トレースはしない)

================================================

※ちなみに【2】については、
  英語「Via」の日本語訳が「～を通って」といった意味であるのを知っている人は
  より気づきやすかったのではと思います。

＞＞＞あるいは、上記のようなトレースを高速で行うべきものなのか…。
→上記のような"動き"であることをイメージできていれば、
  【4】のようにトレースが必要な最小限の箇所を絞り込むことができたかと思います。


落ち込む必要など全くないですし、ましてや笑う人などいません。
こういったアルゴリズム力を養う唯一の方法は、
何時間かかっても自力でトレースし考えることだからです。
ぜひそのまま続けてみてください。

合格を心からお祈りしております。

ちょっと言葉足りませんでした。
トレースの必要な箇所に気づけばいいんです。
via=1のトレース結果が与えられているのでそのデータを使って
via=2の時のトレースを
aなら
from=1
to =3
で行うだけです。

チンプンさん(No.2)
room710さん(No.3)


スレ主です。
レスありがとうございます！
大変理解が深まりました。

先日トレースの重要性を痛感して、取り組んでおりましたが、
ヤミクモにやるだけではなくて、「プログラムの動きをイメージする」
という言わばイメトレも大切ですね･･･。

色々と気付きが多いです。
感謝いたします!!

引き続きがんばります･･･

viaは簡単にいえばtoにいくまでの経由地点です。
例えば2から４までは、(via=)1を経由したほうが早いのか、3を経由したほうが早いのか、5経由したほうが早いのかを調べています。経由地点が存在しなかったら、toまでの距離がそのまま入ります。

問題文やソースコードをよく読んで、そのプログラム何をしたいのかを頭の中で思い浮かべることができればいいんですが、これはトレースしまくって練習しないとなかなかできないんですよね。
自分はH29の最短経路の問題を一番最初に取り組んだんですが、本当に何時間もかかりました。なので最初はそれでいいと思います。同じ問題でもいいので何回もトレースするのがいいと思います。(自分は日を開けて何回もやっています)

私もぱるむさんと同意見です。

がむしゃらにトレースをすることによってでしか養われない感覚が確実に存在していると思います。
いまだにアルゴの短期修得法が編み出されていないのもそう言うことなんだと思います。

落ち込み中さんのおっしゃる「ヤミクモ」は必要な過程だと思いますし、その「ヤミクモ」を実行できる人は、しばらく耐えれば攻略できる人です。

ぱるむさん(No.6)
チンプンさん(No.7)

スレ主です。
ありがとうございます。

毎回のようにアルゴリズム問題に対しての不安というか、自身の至らなさを吐露してしまっており、申し訳なく思います･･･。

とにかくあれこれ考えずに、トレース、トレース、トレース･･･その先にある世界を見てみたい･･･。
午後試験まで1ヶ月、出来ることを出来るだけやってみます。
ダメでも再トライするのみです！

おそらくプログラム未経験の人のほとんどはそうだと思いますよ。
私は２０問ぐらい何周かやりましたけど、満点取れるようになった問題ですら、毎回読み始めるのが苦痛でしたよ。

アルゴはたぶん、やり続けさえすれば誰でもできるようになると思います。
ただ、この「やり続ける」という部分が最大の難所なんだと思います。
多くの人が、目先に光が見えてこない不安と、間違えては最初からやり直しになりがちなトレースのめんどくささに心が折れてしまう結果、難問扱いになっているのでしょう。
しかしやり続ければ「お？アルゴいけるんちゃう？」な瞬間が必ず訪れますので、それまで少し我慢して頑張ってください。

私の主観では、落ち込み中さんはホントにあと一歩で、ダムの決壊のようにドバーっと色んなことが見えるようになるところまで来ていると思いますよ。