ICPC2026国内予選参加記

チーム

YuuuT
筆者。AtCoder水、ここ2年ほどはほとんどratedに出ておらずヒューリスティックに隠居しています。チーム内で唯一主言語がPythonです（ヒュのおかげで最低限のC++は書けます）。

primesosu
AtCoder水、半年前くらいからちゃんと競プロやってるらしいですが成長速度が早くてすごいです。参加コンテスト数が足りていないだけでほんとの実力は青あると思います。国内予選の翌日が院試なのに参加してくれて感謝。

saya_38_t
AtCoder茶、法学部でちゃんと法律を勉強しながら競プロもやっていて尊敬します。キャンパスが違うのでチーム練のときは毎回理系キャンパスに来てもらっていて感謝。

チームの戦略としては、A,B,Cはprimeさんが考察してsayaさんに実装を投げて、そのあいだに僕がD,Eを読みできそうな1問を詰める方針でした。
僕はグラフ文字列DP構文解析重実装あたりができ、primeさんは貪欲数学パズルなどが得意なので、お互いの得意分野の問題を担当するようにしました。
確実に5完+F,Gのどちらかを通すためにはこの戦略が結構よかった気がします。

模擬国内を含めて4回ほどチーム練をしました。
練習ではギリギリ予選通過圏内な順位のことが多く微妙でした。
僕はアルゴの問題を最近まともに解いていなかったので、典型をざっと復習したり、ICPCの過去問をやったり、昔の模擬国内を1人で何回か走ったりしました。

コンテスト

A,B,Cをチームメイトに任せてD,Eを読みます。
Dはなんかの周期性がありそうですが、ダブリングでは無理ということしかわかりません。
Eを読むと自分ができそうな形なのでこっちを考えることにします。
dp[i]=ジェルがi個で最小コスト、とかを考えたりしますがうまくいきません。
プリンターに印刷した問題文の残りを取りに行くと紙の量が多くて驚きます。末尾に英語問題文がついていたようでそれも印刷してしまっていたようです。
Aがまだ通っていないようで少し心配ですが2人に任せておきます。
Eをいろいろ考えていますが一向に解ける気配がせず焦り始めます。
そうこうしてるとCまで通ったようです (A:0:14, B:0:21, C:0:29)。

primeさんにDは周期性がありそうでそこからいけそうと無の考察を言って頼みます。
sayaさんにはEのサンプルの3つ目のケースでどのように買えばその答えになるのか考えてほしいと頼みます。
もう少しEを考えると、すべての瓶でジェル>=1の場合は1つだけ瓶を買えばすべて取得できることに気づきます。
また、最低でも買わないといけない瓶の個数 m = max(1, N - sum(b_i)) であることに気づきます。
そこで、ジェル>=1の瓶を1つ以上含むように安い順に m 個買う貪欲を思いつきますが、あまり自信が持てません。
思いついたタイミングでsayaさんがサンプルの3つ目のケースを解読してくれ、貪欲方針と矛盾しないことが確認できました。
ただ貪欲が正しい確信が得られず、Eでこんな簡単な貪欲がでるか？という気持ちがあり悩みます。
Dを実装していたprimeさんが少し詰まっているようでパソコンがあいたので、とりあえず貪欲方針を実装してランテスを書くことにします。
貪欲自体はすぐに実装ができサンプルもあいました。
ランテスを書き始めますが、愚直解の書き方がわからなくなり一旦パソコンを離れます。
愚直解を修正してランテスを走らせるとと100ケース経過してもあっているようでした。
なかなか信じられませんがこれ以上考えてもわかる気がしないので、とりあえず提出します。
するとまさかのACで盛り上がります (E:1:33)。
Dは実装がバグっているようで確実に通したいので一旦僕も見ることにします。sayaさんにはFを読んでもらいます。
解法を聞きながら2人で見ていると一か所変数名が間違っていることに気づき、直して提出するとACしました (D:1:40)。

この時点では53位で、確実に予選突破するにはあと一問解きたいところです。
順位表を見ると15位くらいまでが5完で、F,Gを通しているチームが思ったより少なく驚きました。
いったん分担して僕がFを読むことにします。
Fは障害物に隣接するマスだけを考えればいい気がしますが、実装がやばそうで解ける気がしません。
順位表を見てもFを飛ばしてGを通しているチームが多く、ペナをつけているチームも多いので魔境そうです。
Gが8割解けたといわれ、時間的にもF,Gのどちらかに集中したほうがいいのでGを全員で考えることにします。
N/2行目でしか衝突しなくて、N/2行目j列目で初めて衝突する通り数はDPで計算できると言われ、賢いとなります。
衝突する場所からゴール地点までの通り数の高速な求め方がわからないと言われますが、それはゴール側から1回DPしたらいいと助言し、実装することにします。
実装はなんだかんだで僕がすることになりました（チーム練の際もprimeさんが解法を考え、僕が見守られながら実装することが何度かあったので僕が書いた方がいいと思いました）。
mintで.val()だるいとかセミコロンは自動で補完してくれよとC++の文句を言いながら実装します。
少しバグりますがすぐに解決し、提出するとAC (G:2:37)。
35位まで順位があがり横浜ほぼ確定となり大盛り上がり！
もう残り20分程度しかないので、あとは順位表を眺めたりお互いが見てない問題を共有したりしました。

振り返り

結果は38位でした。

結果

同校制限おこぼれではなく50位以内に入って横浜に行けて嬉しいです。
早解きではなく問題数で順位を上げられたのも嬉しいです。Gの考察が早くてほんとに感謝。
Eの考察がもっと早ければ順位上がったかなと思いましたが、1つ上のチームとは時間差が結構あるのでそんな変わらなさそうです。
もっと順位を上げるにはもう1問解く必要がありそうで厳しいです。
弊学から横浜行くのは4年振りぽいです。
自分以外のチームメンバー2人は来年も弊学に残るぽいので、弊学にICPC文化の種をまけたという意味でも嬉しいです。
チームメンバーの実力はまだまだ上がると思うので、横浜ではPlayoffの夢が見れるようにがんばりたいです。

AHC066 15位解法メモ

AHC066で15位になりました。
自分のメモもかねて解法を記事にしました。
提出コード：Submission #76524677 - AtCoder Heuristic Contest 066

解法

マクロは原則1つで固定し、固定するマクロを探索しました。
おおまかな解法は、マクロ探索→ボール回収順改善の山登り→後処理 です。

マクロの探索

まずseed0000~3000を解き、使用したマクロを埋め込んでおきます。
埋め込むマクロはNとT/2MN^2<=0.2かどうかで分類し、入力に合うものを初期のマクロ候補とします。
マクロの評価は後述のビームサーチによっておこないます。
埋め込んだマクロだけではいまいちなので、評価済みマクロのうち評価値が高いものに対して変更を加えて新たなマクロ候補を作っていきます。
新たなマクロ候補を作る際に加える変更は以下の通りです。

  • F/FFをL/Rの前後に挿入
  • L/Rの挿入
  • 1文字変更
  • 1文字削除

変更を加えた結果、LRやRL、LLL、RRRがマクロ中に発生する場合はその変更を棄却しています。
また、マクロのすべての文字に対して1文字変更/削除をすると候補数が多くなるので、これらの変更は1つのマクロに対して最大3回ずつに制限しています。
評価済みマクロの集合から評価値で重みづけしてマクロを取り出し、取り出したマクロに上記の変更のうち1つを加え新たなマクロ候補とすることを繰り返します。
マクロの評価順序は、埋め込みマクロと変更を加えたマクロを交互に評価するようにしています。

埋め込んだマクロ候補が最終的な解に採用されている割合は20%程度だったので、変更を加えるのが結構効いているようでした。

マクロの評価のビームサーチ

マクロの評価は、マクロを固定したときの操作列をビームサーチで求めたものを用います。
ビームサーチは1つのボールを取ってかごに入れるのを1手とします。
1つのマクロの評価にあまり時間を取らないようにビーム幅は30にしています。
ボールを取ってかごに入れる経路はBFSで求めたマクロの使用を含む最短経路を使っています。
評価関数は「ここまでの操作列長 + 未回収のボール→かごの最短経路の和+ 展開長のペナルティ」としています。
展開長のペナルティは (展開長)/T > 0.85 の場合のみ、展開長に応じて最大15のペナルティを与えています。
M<=7のときはbitDPでも高速に動くのでビームサーチではなくDPを使っています。
ビームサーチは状態をコピーする素朴な実装にしています。
状態が50バイトくらいで軽いので差分更新にしても変わらないと思い差分更新にはしませんでした。
NextBeam（評価済みノードを入れとくやつ）はビーム幅の二倍のサイズになるたびにソート+resizeしています。
また、NextBeam内の（ソートされたノードの）最も悪い評価値より良い評価が見込めない親ノードからの遷移は枝刈りしています*1。

ビームサーチで操作列を求めたあとにマクロ定義部分のみの後処理をおこなっています。
例えばLFFFFFLFFFFFLFFFFFのようなマクロは、MFFFFFMMLPLPLPMとすることで定義部分を圧縮できます。
このような後処理をおこなった後の操作列の長さをマクロの評価値としています。

山登りパート

上記のマクロ候補生成と評価を1800~1880ms程度おこなったあと、評価が高いいくつかのマクロに対して山登り法でボールの回収順の改善をおこないます。
ビームサーチをしたときの回収順を初期解として、swap,insert,2-optなどの近傍で山登りをします。
回収順を固定したときの操作列長はDPで出せるのでそれを評価関数にしています。
全く改善しないケースもありますが、平均で3~5手程度改善している気がします。
山登りの結果最も操作列が最も短くなったものを最終的な解とします。

後処理パート

最終的な解に対して後処理をおこないさらに短縮します。
ビームサーチの後にもおこなっていたものに加えて、以下の2点をおこなっています。

  • 操作列の終わりが...PPSLPPSRPPSみたいな場合はMPPSMLPRPとマクロを再定義することで短縮できるので、操作列を後ろから見ていきマクロを再定義することで短縮できればそうする
  • マクロ再生中に壁に当たったりする関係で、操作列から1,2つ操作を削除してもすべてのボールを回収できる場合があるので、そのように削除できる操作があれば削除する

やらなかったこと

マクロ探索の焼きなましは、探索空間をなだらかにできずすぐ局所解にはまる気がしたのでやりませんでした。
壁に当たったらその場にとどまるため、マクロを少し変えるだけで壁に当たるタイミングが変わり、経路が大きく変わる可能性があるので探索空間がガタガタになりそうだと判断しました。
埋め込みの数を増やしたり、使う埋め込みをM基準にしたりしましたが、スコアが下がったのでやめました。
順序探索の山登りを焼きなましにしてみましたがこれもスコアが下がりました。

AIについて

内容によって以下のようにモデルを使い分けていました。

  • 解法の実装：codexからchatGPT5.5-medium/high
  • データの集計やちょっとした実験スクリプトの作成など：Gemini Flash 3.5（antigravity CLI経由）
  • 考察の壁打ち、高速化アイデアの提案、解法の改善案の提案：chatGPTのチャットとcodexからchatGPT5.5-xhigh

解法の実装以外にcodexを使わないことで、chatGPTのplusプランでもcodexの使用量制限に余裕をもってコンテスト期間を過ごすことができました。

AIに渡す問題文はh,ul,li以外の不要なhtmlタグを除去しています。
基本的に解法は自分で考えて、実装をAIに投げるスタイルでやりました。
AIに改善案を考えさせてもいまいちなものしか考えてくれないので、自分の考察がつきたときに参考程度に考えさせていました。
高速化もAIにやらせるとデータ構造系の高速化しかやってくれず、問題や解法の特性を活かした枝刈りなど本質的なものは提案してくれないので、その辺は自分で考える必要がありました。

感想

これ系の問題は苦手意識があったのですが、短期含めて最高順位が取れてうれしいです。
かなりがんばったのでやり切った感はありますが、ビムサの評価関数や埋め込み候補数、ビムサと山登りの時間配分などはちゃんと調整したほうがよかったなというのが反省点です。
上位の解法を見ているとまだまだ自分ではたどりつけないものが多いので、いろんな解法を読んで勉強していきたいです。
個人的にはM挿入の過去改変ビームサーチが賢いなと思いました。
入力別の順位を見ると壁なしのケースで順位が低くなっていました。
ここまで顕著に差がつく心当たりがないのでよくわからないです。

システスの入力別順位

最近は貪欲やビームサーチが強い問題が多いので、そろそろ焼きなまし高速化バトルがきてほしいです。
次の長期はあまり取り組む時間をとれなさそうなので、まずは6月7月の短期をがんばりつつ、今年中の銅冠を目指して引き続きがんばっていきます。

*1:これなんかで見た気がするんですが、汎用的なテクなんですかね

KSDUPC 開催記

2024 年 9 月 15 日に KSDUPC (京都産業大学・同志社大学プログラミングコンテスト) を開催しました。
mofecoder.com

せっかくなので開催記を書くことにしました。
開催経緯や作問について、感想などを書いています。

開催経緯

KSDUPCの開催は僕が言い始めました。
そんな大した開催理由はなく、単にオンサイト楽しそうだし行きたいけど関西はあんまないし自分で作るか、という感じで開催しようと思いました。
詳しくは書きませんがバイトで競プロ作問のようなこともしているので、自分の作った問題でコンテストを開催してみたいという思いもありました。
あとは、自分の周りに競プロerがいなくて寂しかったので競プロerと交流したかったのもあります。
競プロを続けるにはモチベの維持がかなり大切だと思っているので、このオンサイトが誰かの競プロモチベにつながっていれば1番嬉しいです。

とはいっても、僕の大学には競プロサークルどころか競プロerがほとんどいないため、オンサイト開催は前例のなくかなりハードルの高いことでした。
そこで、IOOR (京都産業大学の競プロサークル) の方に声をかけたところご協力していただくことができ、開催できることになりました。
IOOR に声をかけたのは、同じ京都の大学だったのと最近できた競プロサークルだとTwitterで見たことがあったからです。

運営メンバーは自分含めて 4 人で準備を進めました。
全員協力的で会場の手配などはすべて任せました、助かりました。
オンサイトにかかった費用は、主に WiFi のレンタルと当日のお菓子や名札で数千円程度でした。
参加費を 100 円いただいたのでだいたい賄えました、ありがとうございます。*1

作問

作問は、全員が原案を出し、そこから僕が問題文やテストケースを作りました。
問題セットは、僕が原案の問題 6 問 + 他のメンバーの原案を僕が手を加えたもの 3 問 だったので少し僕の色が強すぎたかもしれません。
問題数も多く大変でしたが、自分で問題を作ってそれがコンテストページに表示されているのを見るのは嬉しかったです。
作問で1番大変だったのは、Pythonが落ちないようにすることでした。
ちょっと制約をキツくするだけでもPythonが落ちてしまって、制約をうまく調整するのが難しかったです。
PythonでACできることの確認はなるべく高速化テクを使わないコードで行いましたが、入力は高速化しないと厳しい問題があったのでコンテスト概要で入力高速化をアナウンスすることにしました。

すべて自分が関わった問題なのでどれも思い入れがありますが、中でもG,H,I問題が好きな問題でした。
G,H,Iはどれも僕の原案でした。
G,Hは高度なアルゴリズムやデータ構造は必要なく、レートが低い人でも時間をかければ解ける問題だと思います。
このオンサイトのコンセプトにもあっていて、題材も個人的に好きでした。
Iはかなり前から温めていた原案だったので、問題にできて嬉しかったです。
逆にDは典型すぎて面白くなかったかなと思います。

コンテスト後のアンケートでも G 問題が好評で嬉しかったです。
H 問題は出力形式の説明が十分でなく、すみませんでした。
問題文には出力形式を書かずに必ず出力の説明欄を読むようにして太字にしていたのと、サンプルにも出力形式が適切でないと落ちる問題をいれていたので大丈夫かと思っていたのですが、出力形式を間違えてる提出が多かったです。
コンテスト中に出力形式でWAになってる人が多かったので追加でアナウンスをしましたが、アナウンスのタイミングも遅かったかもしれません。

コンテスト時間についても短すぎたと思います。
テスターと自分の感触的に100分でも全完が 5~10 人くらいでると思っていましたが、実際はオンサイトでは 2 人しか全完がでませんでした。
時間があればもっと解けたという声が多かったので120分や150分でもよかったと思います。
とはいえ、難易度は適切だったという声が多く、問題ごとの難易度想定はそんなにずれていなくてよかったです。

コンテスト中はほぼずっと順位表と提出を見ていました。
苦労して作った handmade ケースで落ちているコードを見ると嬉しかったです。
自分で作った問題を多くの人に解いてもらえて嬉しかったです。
特に、AtCoder の Writer や解説で見たことがある人にも解いてもらえて嬉しかったです。

その他いろいろ

当日は机が足りなくなるほど多くの人に参加していただけて良かったです。

オンサイト当日の様子

いろいろな競プロerの方と交流できて競プロモチベがまた上がりました。
特に、コンテストの問題について自分が想定していなかった解法についてもいろいろ聞けて良かったです。
Twitter にもありがたい感想がたくさんあって嬉しかったです！
言葉や文字にして感想とかを伝えてもらうのが嬉しかったので、自分も積極的に発信しようと思いました。
このオンサイトをきっかけに競プロer同士の交流が深まり、サークルの設立につながったという話も聞き、とても嬉しいです。
このイベントが誰かの競プロライフにいい影響を与えることができたていたら嬉しいです。

来年の開催はまだなにも考えてないですが、いまのところは あり：なし = 30：70 くらいでちょっとなし寄りです。
というのも、今回は作問作業の大部分と運営の主導を僕が行ったのですが、来年は僕が忙しいかもしれないというのが大きな理由です。
僕は来年は文系の3回生になるのですが、文系の3回生ということは就活をしなくてはいけないので、そうなると来年はインターンとかで忙しくてオンサイトを開く余裕はないかなという感じです。
とはいっても、まだ自分の進路を決めかねている部分もあるので、もしかしたら予定が変わって開催できる可能性もあります。
もちろん、運営・作問を中心になってやってくれる人が他にいれば開催される可能性は十分あります。
もし、来年も開きたいな〜という関西の学生がいたらなんとかして欲しいですね。
関西オンサイトもっと欲しいのでお願いします！！
アンケートの感想でも関西オンサイトをお願いします！という声が多かったので関西オンサイトの需要は高いと思います！
作問さえなんとかなればあとは何とでもなるので、オンサイトを開催を迷ってる人はぜひお願いします

作問は楽しかったので、yukicoder などでまた問題だせたらいいなと思います。

最後になりましたが、参加していただいたみなさん、運営に協力してくれた IOOR の方、ありがとうございました！！
0 から自分でイベントを企画して開催できたことはかけがえのない経験になりました。
これからも競プロ界隈になにか協力できることがあれば積極的にしていきたいです。
とりあえずは年内に AtCoder 青色を目指してこれからも競プロを続けていきたいと思います！

*1:上記の費用の他に、テスターへのお礼や運営への差し入れがありますがそれに参加費は使っていません

ICPC2024国内予選 参加記

ICPC2024国内予選に参加しました。
結果は106位、4完でした。

おそらく予選突破のボーダーは80~90位くらいになりそうなので横浜には行けなさそうですが、せっかくなので参加記を書いてみます。

自己紹介

同志社大学の2回生です。
競プロを始めたのは去年の5月とかなので、ICPCに参加するのは今年が初めてでした。

当日までの流れ

初めはメンバーが集まらなかったりしたため今年はICPCやめとこうかな～と思ったりしていましたが、いろいろあって僕が所属していないサークルで結成されていたチームに入れてもらえることになりました。
メンバーはM1とB4の方で、AtCoderだと緑~水くらいとのことでした。
チームメンバーとは通っているキャンパスが違ったりしたので予選の日に初対面でした。

せっかくなら横浜行ってみたいなと思い、ICPCの過去問を10~15問解きました。
（従来の）A,B問題は解けそうで、C,D問題は時間をかけたら50%くらい解ける感覚でした。
重実装で自分が苦手な問題が多くなかなか苦戦しました。

ICPC前最後のABCでは入水しました。

予選は普段通っている今出川キャンパスではなく、理系学部がある京田辺キャンパスでやることになっていたので行くのめんどくさいなーと思っていました。
当日行ってみると、駅からも遠くキャンパスも広いためちゃくちゃ歩きました。普段運動しないので翌日足が筋肉痛になりました。
こんなキャンパスに毎日通っている人はすごいなと感心します。

当日　本番まで

これはICPCに関係ありませんが前日から京都に住んでいる友達の家に泊まっていました。僕の家からだと京田辺キャンパスまでは2時間くらいかかりそうだったので、友達の家からだとまだ近く助かりました。
二度寝を重ねていたら11時になっていました。
14時までには着いておきたかったので12時くらいに出発しました。

地下鉄とバスを乗り継いでキャンパスに到着します。
サークルの方にリハーサルを行う学生会館に案内していただきました。
京田辺の学生会館には初めて行きましたが、壁の落書きに驚きました。私立大学なのにこんなに汚くていいのかといいたくなります。

リハーサルでは提出方法などを確認しました。
提出ファイルが.txtだと提出できなかったり、answerとprogramを逆に提出していて10分くらい悩みました。出力ファイルはanswerではなくoutputとかの方がよくないですか
リハーサルの部屋では他のチームやサークルのことも話しました。

その後本番の部屋に移動します。これも結構歩きました。
本番は理工学部？の研究室みたいなところにでやりました。理系の研究室に来るのは初めてだったのでわくわくしました。僕は文系なのでゼミはありますが部屋は与えられないんですよね

本番はチームメンバーのパソコンを利用することになったのでいろいろ調整していました。
一番問題だったのは、僕のパソコンはキーボードがJIS配列なのですが本番で利用するパソコンはUS配列だったことでした。
配列の変換などを試みましたが、結局僕が本番でUS配列のままがんばることになりました。

当日　本番

いよいよ始まりました。
最初にコーチの方に問題文の印刷をお願いしましたがうまくいきません。
その間に僕がA問題を解きます。
普段とは違うキーボード配列と実行環境だったため、+= を =+ とタイポしているのに気づけずかなり提出が遅れました。反省です。

まだ問題文が印刷できていなかったので、続くB,C問題も3人で考えます。
他のメンバーの方が問題文の理解が早かったので2問とも他のメンバーに任せました。

メンバーがCを実装している間に問題文が印刷できたので僕はDの考察に入ります。
簡単だと思ったのですぐに紙にコードを書き、Cが通ったあとにパソコンでコードを書き始めます。
ところがサンプルを入力すると実行が終わりません。
なんと同じところをループする場合の考察が抜けていました。
メンバーに一旦パソコンを譲り紙で考え直します。
その後もなかなか合わなかったりしましたが、開始から1:40でようやく提出できました。

その後は僕がF、他の2人はEを考えます。
Fは最終的に考察は完成しましたが実装する時間(とパソコン)がありませんでした。
Eはメンバーがあとちょっとのところまでいきますが時間内には通せませんでした。

当日　本番後

コンテストが終了します。
Eを実装していたメンバーは終了10分後に正解のコードがかけたらしくかなり悔しがられていました。
順位表を見るとSPJやAMATSUKAZEが上位でさすがだなとなりました。

後片付けをした後、メンバーはサークルの部屋に戻るとのことだったので僕は先に解散しました。
帰りはいい時間にバスがなかったのでキャンパスから駅まで歩きました。下り坂がきつくこれが筋肉痛の原因だと思います。
最寄り駅に着きましたが全然電車が来なくて困りました。

振り返り・来年に向けて

Dをもう少し早く解けていたら横浜に行けたかもしれないのでそう思うと悔しいです。
コンテスト後に気づきましたが、Dは x, y の制約を読み間違えていて必要のない高速化をしていたので制約をしっかり読んでいればもう少し早く実装できたかもしれません。
Fも途中まで制約を読み間違えていて考察が遅れたので、もし制約を正しく理解していれば通せたかもしれません。
とはいえ、チーム練習をしていなかったりCが解けるまで問題文が印刷できなかったり実行がうまくできなかったりといろいろ問題があった割に、いいところまではいけたので十分かなと思います。

今年チームを引っ張ってくださった方はM1なので来年はチームを組みなおす必要がありますが、そもそも弊学に競プロerが少ないため来年もICPCに出られるかはわかりません...
いま高校生で競プロやってる方はぜひ同志社大学に来てください～
ICPCの校内争いはほぼないのでその点ではかなりいい環境だと思います。

思ったより楽しかったので来年を出られるといいな～と思います。
それまでに実力をあげれるように、まずはAtCoder青色を目指して頑張ります！

ABC271 E Subsequence Path 【AtCoder】

問題はこちらです。
atcoder.jp

想定解はDPのようですが、ダイクストラ＋二分探索でも解くことができます。

通る道の番号を通った順番に並べた列が E の部分列になるには、辺 E_i を通ったあとは辺 E_{i+1}, ... , E_K しか通ることができません。
使用する辺がこの条件を満たす場合のみ移動するようにします。
条件を満たすかどうかの判定は、あらかじめ数列 E の中で辺 e が何番目に登場するかを記録しておき、 辺 e が E の i 番目以降に登場するのは最小で何番目かを二分探索すればよいです。（ i 番目以降に辺 e が登場しなければ辺 e を使って移動できません。）
したがって、 (現在の通る道の長さの合計, 現在の頂点, E の何番目の辺を使ったか) を管理しながらダイクストラをすればよいです。

# oj t -c "python3 main.py"
import sys,math
from collections import defaultdict,deque
from itertools import combinations,permutations,accumulate,product
from bisect import bisect_left,bisect_right
from heapq import heappop,heappush,heapify
#from sortedcontainers import SortedList,SortedSet
def input():return sys.stdin.readline().rstrip()
def ii(): return int(input())
def ms(): return map(int, input().split())
def li(): return list(map(int,input().split()))
inf = pow(10,18)
mod = 998244353
#//////////////////////////////////
N,M,K = ms()
G = [set() for _ in range(N+1)]
for i in range(M):
  u,v,c = ms()
  G[u].add((v,c,i+1))
E = li()
# E の中に辺 e が何番目に登場するかを記録
cnt = defaultdict(list)
for i in range(K):
  cnt[E[i]].append(i+1)

H = []
heappush(H,(0,1,0))
ans = inf
while H:
  c,v,ind = heappop(H)
  if c>=ans: continue
  for v2,c2,i in G[v]:
    # E の ind 番目以降に辺 i2 が登場する場所を求める
    if len(cnt[i])==0: continue
    nex = bisect_right(cnt[i],ind)
    if nex==len(cnt[i]): continue
    
    if v2==N:
      ans = min(ans,c+c2)
    else: heappush(H,(c+c2,v2,cnt[i][nex]))

if ans==inf: print(-1)
else: print(ans)

ABC179 E Sequence Sum をPythonで解く【AtCoder】

問題はこちらです

atcoder.jp

周期性を使った解説が多いので、ダブリングを使って解いていきます。 自力でACできなかったのでこちらの記事を参考にしました。

drken1215.hatenablog.com

遷移後の値を管理する配列と、操作後の総和を管理する配列の2つを用意するところが通常のダブリングとは違うところです。

N,X,M = map(int,input().split())
SUM = [[0]*M for _ in range(35)]
nex = [[0]*M for _ in range(35)]
for j in range(1,M):
  SUM[0][j] = j
  nex[0][j] = pow(j,2)%M

for i in range(1,35):
  for j in range(1,M):
    SUM[i][j] = SUM[i-1][j] + SUM[i-1][nex[i-1][j]]
    nex[i][j] = nex[i-1][nex[i-1][j]]

ans = 0
ind = X
i = 0
while N:
  if N&1: 
    ans += SUM[i][ind]
    ind = nex[i][ind]
  N >>= 1
  i += 1

print(ans)

ABC180 E Traveling Salesman among Aerial Cities をPythonで解く【Atcoder】

問題はこちらです

atcoder.jp

この問題は典型的なbitDPで解けます。
以下の解説は都市を0-indexで扱うため、例えば都市１->都市０としています。
ここで、S := 訪れた都市の集合。2進数に変換したとき 1 の都市を訪れている　と定義します。
例えば、S = 3_{10} = 0011_2のときは下から0番目と1番目が 1 なので、都市０と都市１を訪れたことになります。
この集合Sを使って、dpテーブルは以下のように定義できます。
dp[S][v] := 訪れた都市の集合が S で最後に訪れた都市が v であるときの最小コスト
遷移は集合 S に対し、まだ訪れていない都市 v と最後に訪れた都市 u を決めると、以下のようになります。
dp[S|(1<<v)][v] = min(dp[S|(1<<v)][v], dp[S][u]+都市 u から都市 v へのコスト)
S|(1<<v) はSに新たに下から v 番目を 1 にしたものを表します。
例えば、S = 4 = 0100_2のとき v = 1 とすると、4|(1<<1) は 0110_2 となり、新たに都市 １ を訪れたことになります。
この遷移を適切な v と u を選んで行うと、都市０ から全ての都市を１度通って各都市へ移動する最小コストが求められます。
最終的に、（都市０ から各都市へ移動する最小コスト + 最後に各都市から都市０へ戻るコスト）の最小値が答えになります。
わかりにくい解説になってしまいましたが、コードを見て少しでも理解していただけると嬉しいです。

N = int(input())
P = list()
for _ in range(N):
  x,y,z = map(int, input().split())
  P.append((x,y,z))
POW = pow(2,N)
dp = [[inf]*(N+1) for _ in range(POW)]
dp[1][0] = 0 # 都市1からスタート
for S in range(POW):
  for v in range(N): # 次訪れる点
    if (S>>v)&1==1: continue # v を既に訪れている場合
    for u in range(N): # 最後に訪れた点
      if (S>>u)&1==0 and S!=0: continue # u をまだ訪れていない場合（まだ訪れていない頂点からは遷移できない）
      dp[S|(1<<v)][v] = min(dp[S|(1<<v)][v], dp[S][u]+abs(P[v][0]-P[u][0])+abs(P[v][1]-P[u][1])+max(0,P[v][2]-P[u][2]))

ans = inf
for v in range(N):
  ans = min(ans, dp[POW-1][v]+abs(P[0][0]-P[v][0])+abs(P[0][1]-P[v][1])+max(0,P[0][2]-P[v][2]))
print(ans)