ABC387個人的備忘録

2025年点数配分に翻弄された男の備忘録です

コンテスト概要

AtCoder Beginner Contest 387（Promotion of AtCoderJobs）

開催日:2025年1月4日 21:00-22:40

A-Happy New Year 2025

考察

さすがに言われた通りにする以上のことはない。シンプルに足して。シンプルに2回かける。もう少しきれいに出来そうだが安全をとったコードに。

提出

A.cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin >> n >> m;

    n += m;
    n *= n;

    cout << n << endl;
}

B-9x9 Sum

考察

九九の盤面の合計が2025であることを利用して、nが含まれる回数だけnを引く。
どうせ二重ループを回すなら愚直に足してもよかった気がする。

提出

B.cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;

    int ans = 2025;
    for(int i=1;i<10;i++){
        for(int j=1;j<10;j++){
            if(i*j == n) ans -= n;
        }

    }

    cout << ans << endl;
    
}

C-Snake Numbers

考察

問題を見た瞬間沼を確信しいったん遁走。D問題を終わらせ取り掛かるも微妙にケースが合わず、無念のリタイア。
方針としては$i*10^j(1≦i≦9,j≦17)$と$10^{18} $の場合の数を計算し、lとrの場合を出すという方針にしたが駄目だった。やりたかったことは公式解説だったんだが...

D-Snaky Walk

考察

絶対にこっちのほうが簡単だと思う。と言ってる割に適当な考察をかまし30分ほど無駄にする。
結局「縦横縦横縦横...」か「横縦横縦横縦...」のどちらかしかありえないのだから2パターンで幅優先探索。両方のうちより良いものを採用、両方だめなら不可能。

提出

D.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    int h,w;
    cin >> h >> w;
    int lim = (1<<30);
    vector<vector<int>>od (h,vector<int>(w,lim)),ev (h,vector<int>(w,lim));
    //最初縦に進むパターンと、横に進むパターンを用意

    pair<int,int>st,gl;
    int wall = -1;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        char x;
        cin >> x;

        if(x == 'S') st = {i,j};
        if(x == 'G') gl = {i,j};
        if(x == '#'){
            od[i][j] = wall;
            ev[i][j] = wall;
        }
      }
    }
    od[st.first][st.second] = 0;
    ev[st.first][st.second] = 0; 

    queue<pair<int,int>>que;    
    que.push(st);

    while(!que.empty()){
        auto[x,y] = que.front();
        que.pop();
        for(int i=-1;i<2;i+=2){
            if(od[x][y]%2 == 0){
            //偶数ステップ目は縦に進む
                if(x+i < h && x+i > -1){
                    if(od[x+i][y] == lim){
                        od[x+i][y] = od[x][y] + 1;
                        que.push({x+i,y});
                    }
                }
            }else{
            //奇数ステップ目は横に進む
                if(y+i < w && y+i > -1){
                    if(od[x][y+i] == lim){
                        od[x][y+i] = od[x][y] + 1;
                        que.push({x,y+i});
                    }
                }
            }
        }
    }

    que.push(st);
    while(!que.empty()){
        auto[x,y] = que.front();
        que.pop();

        for(int i=-1;i<2;i+=2){
            if(ev[x][y]%2 == 1){
            //奇数ステップ目は縦に進む
                if(x+i < h && x+i > -1){
                    if(ev[x+i][y] == lim){
                        ev[x+i][y] = ev[x][y] + 1;
                        que.push({x+i,y});
                    }
                }
            }else{
            //偶数ステップ目は横に進む
                if(y+i < w && y+i > -1){
                    if(ev[x][y+i] == lim){
                        ev[x][y+i] = ev[x][y] + 1;
                        que.push({x,y+i});
                    }
                }
            }
        }
    }
    
    int ans = min(ev[gl.first][gl.second],od[gl.first][gl.second]);
    if(ans == lim) ans = -1;
    cout << ans << endl;
    
}

結果

結果　ABD　3完 53:14

順位　2363位相当
パフォーマンス 1063相当

感想

久々の3完。新年早々出鼻をくじかれてしまった。12月精進できなかったのが顕著に出てしまっている。
1月中に入水を目標にしてしまったが大丈夫か？