令和6年春期試験 午後問3(プログラミング)についての投稿を受け付けるスレッドです。

コメント0(笑)
もう応用文系マネジメントにこんな誰も選ばない科目なんて要らん

ダイクストラ法の文字が見えた瞬間捨てました。
解いたところで、付け焼き刃じゃ時間が足りない...

ア 17
イ dist[k]がminDistより小さい
ウ dist[k]
エ dist[curNode]+edge[curNode, k]
オ 25, viaNode[k] <- curNode
カ ア
キ 更新起点ノード
ク N^2

自信はありませんが，どなたか意見をください...

ryuさんと本当に全て同じでびっくりしました！
僕も自信が無いのでなんとも言えませんが、同じ回答の方がいて安心しました。

ア 17
イ dist[k] < minDist
ウ dist[k]
エ edge[curNode, k] + dist[curNode]
オ 26(25でもいけそう) viaNode[k] <- curNode
カ ア
キ 更新起点ノード
ク N^2

当方初受験なので条件式系は問題冊子先頭にある疑似言語の形式で書くのかなと思って演算子を使って答えてしまったのですが、改めて過去問を見ると「dist[k]がminDistより小さい」と表記するのがお約束なのかな？  解釈の範疇ということで正解にしてもらえる可能性も十分ある気がしますがやや不安です

26にした気がしますが、あとは私も概ね同じです。

Masaさん，泣きそうです．一緒でありがとうございます(合っているとは限らない...)
25か26は最小にしなければいけないので25ではないかと思います．

ryuさん一緒に泣きましょう(？)
最後ギリギリで26から25に書き換えました！

競技プログラミングではお馴染みのダイクストラ

競プロ勢にとっては大喜びのボーナス問題
競プロやってない勢にとってはかなり難しいアルゴリズムなので捨て問ではないかと

オのコード、”<-“ではなくて’=‘で書いてしまった…

solさん
一緒です。イコールで書いちゃいました。

Temさん
うっかりしちゃいましたよね…！バツにされちゃうだろうなあ

エの足し算を見逃してたぁ…。

ア 17
イ dist[k]がminDistより小さい
ウ dist[k]
エ edge[curNode, k]
オ viaNode[k] <- curNode、25
カ ア
キ 更新起点ノード
ク N^2

クも自信ないですが、皆さんと同じで少しホッとしてきてます。

”エ”はminDist+edge[curNode, k]でも大丈夫ですかね……

”オ”の代入演算子は僕も多分イコールで書いちゃいました！
大目に見てくれないかな……

設問3-1で、25か26は最小を選ばないといけないというのはどこに書いてありましたか？？
問題文に「各ノードの始点ノード距離を更新するたびに、」とあったので、始点ノード距離を更新した後→つまり26行目の後なのかなと思いました。

kurage4さん
私も同じ答えです！
dist[curNode]も同じ意味だけどminDistをわざわざ用意してるならここに使うんだろうなと思って書きました。

ねこさん
ですよね！少し安心しました！

ア 17
イ dist[k] < minDist
ウ dist[k]
エ minDist + edge[curNode, k]
オ viaNode[k] <- curNode、25
カ ア
キ 更新起点ノード
ク N^2

>たーとるさん
設問3 (1) の問題文に「行の番号については、最も小さい番号を答えること」とありますね。

クはN^2にしたけど、プログラムをよく見たら、
for文の中にもう1つのfor文が入っているわけではないので、
Nが正解な気がしてきました。

オーダーのNって小文字じゃダメですか？

計算量は大文字でNにしましたがどうでしょうか…！

for文がNのオーダーで、whileを抜けるためには(curNodeがGOALにいくには)そのfor文を抜けるループを最大N回繰り返すからN^2だと思います。

forが入れ子になっていない、定数倍はオーダーに影響しない、を考えてNにしました…

計算量
N  ＋  N-1  ＋  N-2…
＝N^2  -  N（N-1）/2
＝（N^2＋N）/2
みたいにけいさんしちゃったんですが、シンプルに最大値Nと最大値NでN^2にしたほうがよかったですかね…？  

ああそうか。
while文が最大でN回繰り返されて、while文の中のfor文がNのオーダーなので、
全体のオーダーはN^2ということですね。

ただただ難しかった。

問題分からどのようなアルゴリムか全然想定ができない。
プログラム見た時にwhile(true)とか書いてあって「は？」って言いそうになった…。

これ解けた人は素直にすごい…

始点ノードを更新するたびにってとこから更新した後なのかなと思って26にしたけど、たしかに25ともとれるなー
ダイクストラ法を知らないとなかなか厳しい問題な気がしますね

26にしたや
更新するたびにって書き方がやらしい

不合格っぽい人の投稿を見ると一番心が落ち着くんですよねぇ。

競技プログラミングで常に出るような内容をろくに解けない人が掲示板でいるけど、基礎情報技術者試験を合格してきた人レベルだから、俺の世界ランクがとてつもなく上昇するぅ

(基礎情報技術者試験ってなんだろう…)

エ edge[curNode, k]+dist[curNode]
みたいに順序違うくても正解ですよね...？