ゆるふわブログ

プログラミング,大学の勉強,日常生活で感じたことをゆるふわに書いていけたらなと思います.技術的に拙いところがあっても温かい目で見守っていただければ幸いです.

AtCoder Beginner Contest 106 敗戦記 (Haskell/C++)

はい…

A Garden

やるだけ

import Control.Applicative ((<$>))

main :: IO ()
main = do
  [a,b] <- map read . words <$> getLine :: IO [Int]
  print $ a*b-a-b+1
B 105

やるだけ。約数列挙 O(N) でも間に合いますね。

main :: IO ()
main = do
  n <- readLn :: IO Int
  print $ length $ filter odd8 [1..n]

factors :: Int -> [Int]
factors n = filter ((==0).(n`mod`)) [1..n]

odd8 :: Int -> Bool
odd8 n
  | even n    = False
  | otherwise = length (factors n) == 8
C To Infinity

1 でないなら 5000 兆乗するので指数関数的に爆発していきます。
よって、先頭から見ていって最初に現れる 1 でないものが基本的には答えです。
k 文字 1 が続くなら 1 です。(ここら辺のコーナーケースで何回か失敗した記憶) (水色失格)

import Data.List
import Data.Maybe

main :: IO ()
main = do
  s <- getLine
  k <- readLn :: IO Integer
  let none = filter (/='1') s
      noneId = findIndex (/='1') s

  putChar $ if null none
    then '1'
    else if fromJust (noneId) < fromIntegral k 
      then head none
      else '1'

  putStrLn ""
D AtCoder Express 2

できませんでした()
まあ結論をいうと区間を 2 次元座標と捉えて 2 次元累積和をします (この発想がなかった)
[p, q] のクエリがきた時は座標が (p,p), (p,p+1), ..., (p, q), (p+1, p), (p+1, p+1), ... (q,q) のところ ([(p,p),(q,q)] の矩形) の和がわかれば良いです。

#include <cstdio>
#include <algorithm>
#include <vector>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

int N, M, Q;
int I[510][510], S[510][510];

int main()
{
  scanf( "%d%d%d", &N, &M, &Q );
  rep( i, M )
  {
    int L, R;
    scanf( "%d%d", &L, &R );

    ++S[L][R];
  }

  rep( i, N+1 ) rep( j, N+1 )
    S[i][j+1] += S[i][j];

  rep( j, N+1 ) rep( i, N+1 )
    S[i+1][j] += S[i][j];

  rep( t, Q )
  {
    int p, q;
    scanf( "%d%d", &p, &q );

    printf( "%d\n", S[q][q]-S[q][p-1]-S[p-1][q]+S[p-1][p-1] );
  }
  
  return 0;
}
おわりに

言い訳を述べますが、競技プログラミングにおいてこういう瞬間はあるんだと思います。
自分の中にそのアイデアというか概念がなければ、それが即わからない・解けないにつながってしまうのです。
〜色といっても(知らんですが)〜点問題を〜%の正答率で解けるみたいな感じだと思うので、それを 100% に近づけるのは点数低めであっても難しいものなのだろうと。
"自分がいかにわかっていないか" を思い知る瞬間というのは何を勉強していてもあると思うし、それが非常に重要であると思うので、こういう瞬間に巡り会う機会を増やす (コンテストになるべく出る)、巡り合った時に確実に潰す、この 2 つを大事にしていきたいと思いました。
水色といってもまだまだ ABC を確実に全完できるレベルには達していないことが今回わかったし、初心者を早く脱っさなければならないとお尻に火がつきました。
これからも ABC といっても油断せず参加したいと思います。