square869120Contest #1-C お金の街 (The Money Town)
躓いたのでメモ
問題概要
各頂点にお金が割り振られた無向グラフが与えられる
始点は自由で、より多くのお金を獲得したい、ただし同じ頂点は1回しか通れない
考察・解法
各頂点からそれぞれDFSして最大値更新すればOK~~~と考えたが、入力例1で不可能と判断
入力例1は以下の様なグラフになる
隣接リストで辺を管理する場合、頂点1の次は頂点2に到達してしまい、頂点3には到達できず最大値を取れなくなってしまう
なので、ある頂点から再帰的にDFSを行うとき、新しく到達した頂点の訪問の有無を記録する配列をfalseにしてあげることで1つの頂点からの最大値を取りうる経路の探索が可能となる
説明下手くそすぎるので図にかいた
入力例1の場合を考える
・経路例1
・経路例2
辺自体にコストがあるわけではなく、頂点自体にコスト（しかも大きい方が良しとされる）ので単純なDFSをしてしまうとある頂点Aから別のある頂点までの経路は最短経路の更新がなされないため、1通りとなってしまい題意通りの答えを出力できない
なので、以下の様にする
コード
エイシングプログラミングコンテスト2019-C Alternating Path
以前解説ACしたものを自力で解いた
問題概要
#, .のみで構成されるグリッドにおいて、#と.を交互に渡る経路はいくつあるか
ただし始点は#, 終点は.とする
解法
DFSとUnion Findで.と#で交互に渡ることのできるエリアをグループにする
以下は入力例1の場合
#からいける.の数の総和が答えなので連想配列を使ってグループにおける#の個数を記録
↓
(グループの大きさ - #の数) * (#の数)でグループの#が到達することのできる.の数が算出できる
コード
TPC追いコン-A 不完全迷路
一日溶かした
問題概要
スタートとゴールそれぞれのマスを含んだ迷路が与えられる
入力例5
7 8 .#...... S#.#.### ...#.#.# ###.#.G. .....#.. ..##.#.# ........
入力のままだとSからGには到達できない
一つの#を.に変えることでSからGに到達が可能になる最短経路のうち、最大のものを答えよ
考察・解法
何を言ってるんだ…？ 最短経路のうち最大…？？！？！？？！？
とりあえず最短経路なのでBFSだ
全ての
#を.に変えたときを一つずつ見ていき、SからGの最短経路を求める
→ TLE (H, W <= 298でほぼ毎時BFSを行なったらヤバい)SとGからそれぞれBFSし、お互いの領域から
#を一つ挟んでいる箇所を探す
→ 半分WA (???????????)
長考の末、落ちるケースを発見した
以下の入力の場合を考えます
5 5 S.... .##.# ##.#. ..... #.#.G
BFSで求めた各マスの最短経路は以下の様になる
以下では縦軸をx, 横軸をyとする
x = 2, y = 3の#を外す場合を考える (図の赤丸)
このときx = 2, y = 2 (赤丸の左)に移動すればSからGまでの経路は最大になるが、最短経路にはならない
ここさえ注意できればすぐできると思う
コード
学会に行ってきた
はじめに
唐突だが私は携帯を変えるごとにバックアップは取らず、写真は全部消去するタイプだ
そろそろ携帯を変えよう考えていたところ、自分にとって一大イベントがあったことを思い出した
写真を消去してしまうのはもったいないと思い、ブログに写真を残すことを選んだ
この記事は昨年の秋に参加した学会の備忘録である
経緯
研究室の先生がアメリカで学会あるけど行くか？と提案してくれたので二つ返事で行くことに
2018年で1番のラッキーボーイだったに違いない
学会当日まで
そもそも何で自分が学会いけるんだ？感があった。B3で研究の'け'の字も知らなかったその時期に
先生に聞いたところ，他大学とデモの共同発表だった
共同といっても、他大学の方が100%実装済みで先生同士のご縁あって連れてってもらえることになったそうだ
デモ発表のサポートメンバー的な位置付けでの参加でノー勉で行くのまずいと思い、結構勉強してから行くことに（それはそう）
無線通信におけるデータ転送の国際標準規格の実装デモで、無線通信について無知だったので1から勉強した
勉強を始めたが自分の研究室は新しく、先輩がいなかったので質問が先生にしかできなかった
先生は忙しいのでほぼ一人で勉強した
結構時間がかかった
勉強がひと段落したところで、既に完成していたデモ発表の実装を自分で再現しようと思い、奮い立った
実装の50%ぐらいまでは順調だったが、自分が高熱を出してしまい中断
先生に休めと言われたので出発まで一週間ぐらい引きこもってた（お荷物スギィ！）
学会期間中
飛行機で隣の方がロシアの方で少しお話したがよく聞き取れず適当に会話をしてしまった
優しい方で楽しかった
そんなこんなでアメリカに着いた
地下鉄に乗り会場へ向かった
ホームが暗すぎてちょっと怖かった
会場到着
大きいホテルだった
トートバッグ貰った
めっちゃ人いた
開催期間は3日間
自分達はデモ発表だったが、スライド発表の部門もあったので空き時間に見て回った
質疑応答の時、英語聞き取り能力は本当に大事だなと感じた
スライド発表の分野は様々で色々な分野の発表を見て回った
ロボット工学系の発表を見て人間の生活を支える具体性に面白みを感じた
ロボットって何の言語で書かれてるんだろう Cかな？
日本人は全体の10%で日本語だけでも結構過ごせた
三日間もあったので観光もした
会場近くの動物園のゴリラ
おわりに
近々学会で同じ発表を前回より少人数で行うらしく（一人の可能性もあるらしい）、路頭に迷っている
学生が自分だけ疑惑あるので頑張りたい
166A. Rank List
負数にする系（主語がでかい）
問題リンク
問題概要
チームの解答問題数、ペナルティ数が与えられる
上から番目にはいくつのチームが当てはまる可能性があるか
考えたこと
※以下出てくる用語はC++の用語として記載します
連想配列mapを用意する
- key: 解答問題数とペナルティのpair型
- value: keyをカウントするint型
降順にソート*1し，始めからチーム目に含まれるチームの総数が答え
keyの型がpairであるmapはpairのfirst優先のfirst, second昇順で格納されている
たとえば以下のようなpairの場合，
2 10 2 9 1 55
ソートすると以下の様になる
1 55 2 9 2 10
今回の問題では解決問題数が同じ場合，ペナルティが少ないほうが優位である
つまり，解決問題数は昇順，ペナルティ数は降順でソートする必要がある
これはペナルティ数に-1を掛け負数として扱う事でこれは解決する
コード
#include <bits/stdc++.h> using namespace std; int main(){ cin.tie(0); ios::sync_with_stdio(false); int n, k; cin >> n >> k; map<pair<int, int>, int> mp; for(int i = 0; i < n; i++){ int a, b; cin >> a >> b; mp[{a, -b}]++; } int cnt = n - k; for(auto x : mp){ cnt -= x.second; if(cnt < 0){ cout << x.second << endl; return 0; } } return 0; }
最近読んだ本・最近のこと
最近読んだ本
「優しい死神の飼い方」を読んだ
以下公式サイト*1より抜粋
犬の姿を借り、地上のホスピスに左遷……もとい派遣された死神のレオ。戦時中の悲恋。洋館で起きた殺人事件。色彩を失った画家。死に直面する人間を未練から救うため、患者たちの過去の謎を解き明かしていくレオ。しかし、彼の行動は、現在のホスピスに思わぬ危機を引き起こしていた――。天然キャラの死神の奮闘と人間との交流に、心温まるハートフルミステリー。
犬（死神）の一人称視点で物語が描かれていて面白かった
可愛いなあ、犬
最近のこと
今日は新しいバイト先の初出勤日だった
社員の方々に優しくして頂いたのでそれほど疲れなかった
だが新しい環境に身を置くのは緊張した
これから多くのことを学んでいきたい
それと、人と喋るときはまず結論から言うということを大事にしていく
