tabatak

北海道コンサドーレ札幌が好きです。

tabatak

北海道コンサドーレ札幌が好きです。

最近の記事

AtCoder ABC050 C - Lining Up

AtCoderに取り組んだ記録です。 AtCoder ProblemsのRecommendationsからピックアップして解いています。 問題ページ https://atcoder.jp/contests/abc050/tasks/arc066_a Point: 300 Difficulty: 928 考えたこと 証言が正しく一列に並ぶことができるならば ・N/2番目までの人と、それ以降の人で同じ絶対値の人がだだ一人存在する ・ただし、Nが奇数の場合はN/2番目の人はた

    • AtCoder ABC084 C - Special Trains

      AtCoderに取り組んだ記録です。 AtCoder ProblemsのRecommendationsからピックアップして解いています。 問題ページ https://atcoder.jp/contests/abc084/tasks/abc084_c Point: 300 Difficulty: 893 考えたことt秒後に駅xにいる場合の次の駅までの最短時間は、以下で計算できる ・駅xの始発時間を経過していない場合  -> (始発までの時間 - t) + 次の駅までの移動

      • AtCoder ABC079 D - Wall

        AtCoderに取り組んだ記録です。 AtCoder ProblemsのRecommendationsからピックアップして解いています。 問題ページはこちらです。 Point: 400 Difficulty: 948 考えたこと後半のグリッドに書かれた数字については、個別に扱ってもよさそうです。グリッドであることは気にせずに、書かれた数字を1にすることだけを考えれば大丈夫。 ということで、0~9を1に変換するためのコストがわかっていればよさそう。 前半のグリッドから、

        • AtCoder ABC161 D - Lunlun Number

          AtCoderに取り組んだ際のメモです。 問題ページはこちらです。 Point: 400 Difficulty: 982 ABC161は3完でした。レートは少し下がりました。 コンテスト中に考えたこと・1桁の場合は、隣の桁がないのですべてOK (1,2,3,4,5,6,7,8,9 の9個) ・2桁の場合は、10の位の数に対して選択可能な1の位の数が決まる  -> 10の位が1ならば、1の位に選べるのは 0, 1, 2 のいずれか ・3桁の場合も、同様に10の位の数に対し

        AtCoder ABC050 C - Lining Up

          AtCoder ABC148 E -Double Factorial

          AtCoderに取り組んだ記録です。 AtCoder ProblemsのRecommendationsからピックアップして解いています。 問題ページはこちらです。 Point: 500 Difficulty: 825 解説を読む前に考えたこと自力ではACに至りませんでした。解説読むまでに考えていたのは以下のようなことです。 ・末尾に10が何個つくか = 10で何回割り切れるかだと思う ・10で何回割り切れるかは、Nを構成する数( N, (N-2), ... 1)の中に存

          AtCoder ABC148 E -Double Factorial

          AtCoder diverta 2019 Programming Contest C - AB Substrings

          AtCoderに取り組んだ記録です。 AtCoder ProblemsのRecommendationsからピックアップして解いています。 問題ページはこちらです。 Point: 400 Difficulty: 848 考えたことN <= 10の4乗なので、すべての順序を確認するのは間に合わないと思います。 連結することでつくれる"AB"の個数 A->Bと連続する場合のみが関心の対象であるため、連結について考慮すべき文字列は以下の3つのパターンに分かれます。 1. 末尾が

          AtCoder diverta 2019 Programming Contest C - AB Substrings

          AtCoder ABC054 B - Template Matching

          AtCoderに取り組んだ記録です。 AtCoder ProblemsのRecommendationsからピックアップして解いています。 問題ページはこちらです。 Point: 200 Difficulty: 828 考えたこと左上から始点の画素を固定して、画像Bと全画素が一致するかをチェックすれば行けそうな気がします。制約もN, Mともに50以下なので間に合いそうです。 ・画像Aの全画素について、左上から始点となる画素を決める ・決めた画素から、画像Bと同じ画像の面積

          AtCoder ABC054 B - Template Matching

          AtCoder ABC051 C - Back and Forth

          AtCoderに取り組んだ際のメモです。 問題ページはこちらです。 Point: 300 Difficulty: 852 考えたこと・同じ座標を踏まずに始点と終点間を2回往復する必要がある ・sx < tx、sy < ty の制約があるので、(原則として)往路は"R"と"U"を、復路は"L"と"D"を選ぶことで最短経路を目指せる ・1回目の往復を最短にしようとすると、必ず (sx+1, sy+1)と(tx-1, ty-1) を踏んでしまう ・そのため、2回目を最短にしよ

          AtCoder ABC051 C - Back and Forth

          AtCoder ABC043 B - バイナリハックイージー

          AtCoderに取り組んだ際のメモです。 問題ページはこちらです。 Point: 200 Difficulty: 470 考えたこと・'B' が入力された場合でも、削除するのは末尾からのみ ・スタックにどんどん詰めて、'B'の場合にポップしていけばよさそう 提出したコード提出ページ package mainimport ( "bufio" "fmt" "os" "strings")func main() { r := bufio.NewReader(os.Stdin)

          AtCoder ABC043 B - バイナリハックイージー

          AtCoder ABC160 E - Red and Green Apples

          AtCoderに取り組んだ際のメモです。 問題ページはこちらです。 Point: 400 Difficulty: 1012 考えたこと結果としては、コンテスト中(そもそもDが解けず本問にたどり着けず)、復習中ともに、自力でのACには至りませんでした。以下は、WA、TLEを繰り返していた間に考えていたことになります。 最初に思いついた方法 ・赤、緑、無色を大きい順に並べて、X+Yに至るまで最も大きいものを取っていけばいけそう ・例えば、各々の最も大きいものが、赤=10、緑

          AtCoder ABC160 E - Red and Green Apples

          AtCoder ABC160 D - Line++

          AtCoderに取り組んだ際のメモです。 問題ページはこちらです。 Point: 400 Difficulty: 843 コンテスト中に考えたことコンテスト中はACに至らないどころか、実装もできない状態でした。わからないながら考えていたのは以下のような内容でした。 ・各ノードを始点にして最短経路を求めればよさそう ・最短経路なのでBFSを使えばよさそう ・ショートカットされるノードの場合は、ショートカット先をキューに入れるだけで解決できそう ・でも、各ノードを始点にし

          AtCoder ABC160 D - Line++

          AtCoder ABC064 D - Insertion

          AtCoderに取り組んだ際のメモです。 問題ページはこちらです。 Point: 400 Difficulty: 944 考えたこと・"("が続く限りは、特に挿入操作は必要なし ・"("が連続した回数を保持してておく ・")"が来た場合は、")"が連続する回数を数える ・直前の連続する"("に対応する")"については、対応が必要なし  ->"("が不足する")"については、文字列の先頭に"("を挿入する ・上記の作業をSの末尾まで繰り返す ・"("が開いたままで残ってい

          AtCoder ABC064 D - Insertion

          AtCoder ABC085 D - Katana Thrower

          AtCoderに取り組んだ際のメモです。 問題ページはこちらです。 Point: 400 Difficulty: 929 考えたこと・刀を投げることでHを0にできるならそれが最小と思われるので、貪欲に投げてダメージを与えたい ・投げて削り切れないHについては、振った場合に最も大きなダメージを与えられる刀を使って攻撃すればよさそう 方針 ・刀をHが0以下になるまで投げてみる(ソートしてダメージの大きいものから投げる) ・全部投げてもHが0以下にならない場合は、振って最強

          AtCoder ABC085 D - Katana Thrower

          AtCoder ABC088 D - Grid Repainting

          AtCoderに取り組んだ際のメモです。 問題ページはこちらです。 Point: 400 Difficulty: 994 考えたこと・白マス->黒マスに変更できるマスをできるだけ増やしたい ・白マスのみを通ってゴールにたどり着く必要がある ・変更可能な白マスを増やすには最短経路を求めて、通過しないマスの色をすべて変更すればよさそう ・"すべての白マスの数 - 最短経路で通過したマスの数 - 2" でよさそう(-2はスタートとゴールのマス分) ・制約も縦横ともに50以下なの

          AtCoder ABC088 D - Grid Repainting

          [Go] ビット全探索(AtCoder ABC147-C)

          AtCoderの過去問をコツコツ解いています。 AtCoder Problemsを使って、Difficultyが茶色と緑色の問題を一問ずつ。コツコツと。 今日解いたABC147-C がビット全探索で解ける問題で、久しぶりにビット全探索を書くことになったので復習を兼ねてこちらにも記載。 ビット全探索スイッチのON/OFFや、今回の問題のような正直者/不親切のような0/1で表せる状態を複数の対象に対して網羅的にチェックしたい時に使える方法です。 正直者/不親切な人間がN人いた

          [Go] ビット全探索(AtCoder ABC147-C)

          [Go] container/heap を使った優先度付きキュー

          AtCoderへの参加言語をGoに戻すことにした。他で使う機会があったので、その練習も兼ねて。 優先度付きキューを使う問題があって、実装の方法がわからなかったので調べてみた。(Scalaで解答した際には、scala.collection.mutable.PriorityQueueを使用したのであんまり考えることはなかった) heapパッケージの例をもとに実装heapパッケージのExampleに記載のある、IntHeapをそのまま実装して試してみた。type intHeap

          [Go] container/heap を使った優先度付きキュー